Cover Image

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chandrasekaran, Gautam, Kontonis, Vasilis, Stavropoulos, Konstantinos, Tian, Kevin
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
by: Chandrasekaran, Gautam, et al.
Published: (2025)

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

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

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

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

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

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

Active Learning with Simple Questions
by: Kontonis, Vasilis, et al.
Published: (2024)

Learning general Gaussian mixtures with efficient score matching
by: Chen, Sitan, et al.
Published: (2024)

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

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

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

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

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

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

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

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

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

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, 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 the Sherrington-Kirkpatrick Model Even at Low Temperature
by: Chandrasekaran, Gautam, et al.
Published: (2024)

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

Private PAC Learning May be Harder than Online Learning
by: Bun, Mark, et al.
Published: (2024)

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)

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)

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

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
by: Golowich, Noah, et al.
Published: (2024)

Tight Bounds for Learning Polyhedra with a Margin
by: Patel, Shyamal, et al.
Published: (2026)

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
by: Guo, Anxin, et al.
Published: (2024)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

Online Learning in the Random Order Model
by: Bernasconi, Martino, et al.
Published: (2025)

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
by: Hu, Lunjia, et al.
Published: (2026)

Learning Functions of Halfspaces
by: Alman, Josh, et al.
Published: (2026)

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, et al.
Published: (2025)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
by: Kamath, Gautam, et al.
Published: (2025)