Cover Image

Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zeng, Shiwei, Shen, Jie
Format:	Preprint
Published:	2025
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
by: Zeng, Shiwei, et al.
Published: (2023)

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers
by: Adhikari, Rita, et al.
Published: (2026)

Towards Efficient Contrastive PAC Learning
by: Shen, Jie
Published: (2025)

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

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

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

Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach
by: Li, Yinan, et al.
Published: (2023)

Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
by: Bressan, Marco, et al.
Published: (2024)

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

Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise
by: Hanashiro, Rafael, et al.
Published: (2026)

Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
by: Bressan, Marco, et al.
Published: (2025)

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

Efficient Optimal PAC Learning
by: Høgsgaard, Mikael Møller
Published: (2025)

Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
by: Blondal, Ari, et al.
Published: (2025)

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

Smoothed Agnostic Learning of Halfspaces over the Hypercube
by: Kou, Yiwen, et al.
Published: (2025)

HyPAC: Cost-Efficient LLMs-Human Hybrid Annotation with PAC Error Guarantees
by: Zeng, Hao, et al.
Published: (2026)

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)

Tuning Learning Rates with the Cumulative-Learning Constant
by: Faraj, Nathan
Published: (2025)

Active Learning of General Halfspaces: Label Queries vs Membership Queries
by: Diakonikolas, Ilias, et al.
Published: (2024)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution
by: Huang, Jizhou, et al.
Published: (2025)

Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
by: Huang, Jizhou, et al.
Published: (2026)

On the Vulnerability of Fairness Constrained Learning to Malicious Noise
by: Blum, Avrim, et al.
Published: (2023)

Fast Rates for Bandit PAC Multiclass Classification
by: Erez, Liad, et al.
Published: (2024)

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

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
by: Sinen, Tim
Published: (2026)

Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?
by: Daskalakis, Constantinos, et al.
Published: (2024)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
by: Huang, Jizhou, et al.
Published: (2025)

Tight Generalization Bounds for Large-Margin Halfspaces
by: Larsen, Kasper Green, et al.
Published: (2025)

Bayes meets Bernstein at the Meta Level: an Analysis of Fast Rates in Meta-Learning with PAC-Bayes
by: Riou, Charles, et al.
Published: (2023)

Symmetries in PAC-Bayesian Learning
by: Beck, Armin, et al.
Published: (2025)

On the Computability of Multiclass PAC Learning
by: Gourdeau, Pascale, et al.
Published: (2025)

On the Computability of Robust PAC Learning
by: Gourdeau, Pascale, et al.
Published: (2024)

Noise-Adaptive Layerwise Learning Rates: Accelerating Geometry-Aware Optimization for Deep Neural Network Training
by: Hao, Jie, et al.
Published: (2025)

Sparse, Efficient and Explainable Data Attribution with DualXDA
by: Yolcu, Galip Ümit, et al.
Published: (2024)

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

Error Exponent in Agnostic PAC Learning
by: Hendel, Adi, et al.
Published: (2024)