Cover Image

On Agnostic PAC Learning in the Small Error Regime

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Asilis, Julian, Høgsgaard, Mikael Møller, Velegkas, Grigoris
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

Understanding Aggregations of Proper Learners in Multiclass Classification
by: Asilis, Julian, et al.
Published: (2024)

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

Agnostic Language Identification and Generation
by: Høgsgaard, Mikael Møller, et al.
Published: (2026)

Sample-Near-Optimal Agnostic Boosting with Improved Running Time
by: da Cunha, Arthur, et al.
Published: (2026)

Optimal Learners for Realizable Regression: PAC Learning and Online Learning
by: Attias, Idan, et al.
Published: (2023)

Revisiting Agnostic Boosting
by: da Cunha, Arthur, et al.
Published: (2025)

The Optimal Sample Complexity of Linear Contracts
by: Høgsgaard, Mikael Møller
Published: (2026)

Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
by: Høgsgaard, Mikael Møller, et al.
Published: (2025)

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

Improved Margin Generalization Bounds for Voting Classifiers
by: Høgsgaard, Mikael Møller, et al.
Published: (2025)

On the Computational Landscape of Replicable Learning
by: Kalavasis, Alkis, et al.
Published: (2024)

The Many Faces of Optimal Weak-to-Strong Learning
by: Høgsgaard, Mikael Møller, et al.
Published: (2024)

Optimal Parallelization of Boosting
by: da Cunha, Arthur, et al.
Published: (2024)

The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity
by: Høgsgaard, Mikael Møller, et al.
Published: (2026)

On Union-Closedness of Language Generation
by: Hanneke, Steve, et al.
Published: (2025)

On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability
by: Kalavasis, Alkis, et al.
Published: (2024)

On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
by: Kalavasis, Alkis, et al.
Published: (2024)

AdaBoost is not an Optimal Weak to Strong Learner
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

Randomized Truthful Auctions with Learning Agents
by: Aggarwal, Gagan, et al.
Published: (2024)

On the Learning Curves of Revenue Maximization
by: Hanneke, Steve, et al.
Published: (2026)

(Im)possibility of Automated Hallucination Detection in Large Language Models
by: Karbasi, Amin, et al.
Published: (2025)

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

Majority-of-Three: The Simplest Optimal Learner?
by: Aden-Ali, Ishaq, et al.
Published: (2024)

What is Learnable in Valiant's Theory of the Learnable?
by: Hanneke, Steve, et al.
Published: (2026)

Language Generation with Infinite Contamination
by: Mehrotra, Anay, et al.
Published: (2025)

On Language Generation in the Limit with Bounded Memory
by: Kleinberg, Jon, et al.
Published: (2026)

Differentially Private Language Generation and Identification in the Limit
by: Mehrotra, Anay, et al.
Published: (2026)

Revisiting Agnostic PAC Learning
by: Hanneke, Steve, et al.
Published: (2024)

Local Regularizers Are Not Transductive Learners
by: Jafar, Sky, et al.
Published: (2025)

Replicable Clustering
by: Esfandiari, Hossein, et al.
Published: (2023)

User Response in Ad Auctions: An MDP Formulation of Long-Term Revenue Optimization
by: Cai, Yang, et al.
Published: (2023)

Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models
by: Kalavasis, Alkis, et al.
Published: (2024)

Regularization and Optimal Multiclass Learning
by: Asilis, Julian, et al.
Published: (2023)

Refined PAC-Bayes Bounds for Offline Bandits
by: Gouverneur, Amaury, et al.
Published: (2025)

PAC-Chernoff Bounds: Understanding Generalization in the Interpolation Regime
by: Masegosa, Andrés R., et al.
Published: (2023)

Proper Learnability and the Role of Unlabeled Data
by: Asilis, Julian, et al.
Published: (2025)

Procurement Auctions via Approximately Optimal Submodular Optimization
by: Deng, Yuan, et al.
Published: (2024)

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

More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity
by: Rodríguez-Gálvez, Borja, et al.
Published: (2023)

Transductive Learning Is Compact
by: Asilis, Julian, et al.
Published: (2024)