Cover Image

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chandrasekaran, Gautam, Klivans, Adam R., Stavropoulos, Konstantinos, Vasilyan, Arsen
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

Efficient Discrepancy Testing for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Iterative Chow Filtering for Learning with Distribution Shift
by: Chandrasekaran, Gautam, et al.
Published: (2026)

Testable Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2023)

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, et al.
Published: (2025)

Learning Constant-Depth Circuits in Malicious Noise Models
by: Klivans, Adam R., et al.
Published: (2024)

The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
by: Klivans, Adam R., et al.
Published: (2025)

Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2026)

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Tolerant Algorithms for Learning with Arbitrary Covariate Shift
by: Goel, Surbhi, et al.
Published: (2024)

Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Learning Juntas under Markov Random Fields
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Learning $\mathsf{AC}^0$ Under Graphical Models
by: Chandrasekaran, Gautam, et al.
Published: (2026)

Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Robust learning of halfspaces under log-concave marginals
by: Lange, Jane, et al.
Published: (2025)

Sparse Linear Regression is Easy on Random Supports
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
by: Klivans, Adam R., et al.
Published: (2026)

Replicable Learning of Large-Margin Halfspaces
by: Kalavasis, Alkis, et al.
Published: (2024)

Actively Learning Halfspaces without Synthetic Data
by: Black, Hadley, et al.
Published: (2025)

Reliable Learning of Halfspaces under Gaussian Marginals
by: Diakonikolas, Ilias, et al.
Published: (2024)

Testable Learning of General Halfspaces under Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2026)

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2025)

Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
by: Diakonikolas, Ilias, et al.
Published: (2025)

Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate
by: Shen, Jie
Published: (2024)

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
by: Diakonikolas, Ilias, et al.
Published: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

Efficient Calibration for Decision Making
by: Gopalan, Parikshit, et al.
Published: (2025)

The Importance of Being Smoothly Calibrated
by: Gopalan, Parikshit, et al.
Published: (2026)

Online Learning of Halfspaces with Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2024)

Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
by: Lechowicz, Adam, et al.
Published: (2023)

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions
by: Lange, Jane, et al.
Published: (2023)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
by: Braverman, Vladimir, et al.
Published: (2024)

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
by: McMahan, Jeremy
Published: (2024)

Fully Dynamic Submodular Maximization over Matroids
by: Dütting, Paul, et al.
Published: (2023)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
by: Diakonikolas, Ilias, et al.
Published: (2024)

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
by: Hsieh, Wen-Han, et al.
Published: (2026)

Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
by: Diakonikolas, Ilias, et al.
Published: (2025)

Polynomial-Time Approximability of Constrained Reinforcement Learning
by: McMahan, Jeremy
Published: (2025)