Copertina

The Sample Complexity of Replicable Realizable PAC Learning

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Larsen, Kasper Green, Mathiasen, Markus Engelund, Pabbaraju, Chirag, Svendsen, Clement
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Machine Learning Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Learning with Monotone Adversarial Corruptions
di: Larsen, Kasper Green, et al.
Pubblicazione: (2026)

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

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
di: Garg, Sumegha, et al.
Pubblicazione: (2026)

Derandomizing Multi-Distribution Learning
di: Larsen, Kasper Green, et al.
Pubblicazione: (2024)

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
di: Grønlund, Allan, et al.
Pubblicazione: (2024)

A Distributional-Lifting Theorem for PAC Learning
di: Blanc, Guy, et al.
Pubblicazione: (2025)

Improved Replicable Boosting with Majority-of-Majorities
di: Larsen, Kasper Green, et al.
Pubblicazione: (2025)

Revisiting Agnostic PAC Learning
di: Hanneke, Steve, et al.
Pubblicazione: (2024)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
di: Blanc, Guy, et al.
Pubblicazione: (2024)

A Characterization of List Regression
di: Pabbaraju, Chirag, et al.
Pubblicazione: (2024)

Rate-optimal community detection near the KS threshold via node-robust algorithms
di: Ding, Jingqiu, et al.
Pubblicazione: (2025)

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

The Computational Complexity of Almost Stable Clustering with Penalties
di: Khodamoradi, Kamyar, et al.
Pubblicazione: (2025)

Exploring Facets of Language Generation in the Limit
di: Charikar, Moses, et al.
Pubblicazione: (2024)

Pareto-optimal Non-uniform Language Generation
di: Charikar, Moses, et al.
Pubblicazione: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
di: Bringmann, Karl, et al.
Pubblicazione: (2024)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
di: Leake, Jonathan, et al.
Pubblicazione: (2025)

InstaHide's Sample Complexity When Mixing Two Private Images
di: Huang, Baihe, et al.
Pubblicazione: (2020)

On the Power of Interactive Proofs for Learning
di: Gur, Tom, et al.
Pubblicazione: (2024)

Exact and Approximate Algorithms for Polytree Learning
di: Harviainen, Juha, et al.
Pubblicazione: (2026)

Superconstant Inapproximability of Decision Tree Learning
di: Koch, Caleb, et al.
Pubblicazione: (2024)

Learning-Augmented Algorithms for Boolean Satisfiability
di: Attias, Idan, et al.
Pubblicazione: (2025)

Hardness of Maximum Likelihood Learning of DPPs
di: Grigorescu, Elena, et al.
Pubblicazione: (2022)

Replicability in High Dimensional Statistics
di: Hopkins, Max, et al.
Pubblicazione: (2024)

Active Learning for Decision Trees with Provable Guarantees
di: Moakhar, Arshia Soltani, et al.
Pubblicazione: (2026)

Hardness of Learning Boolean Functions from Label Proportions
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
di: Hanneke, Steve, et al.
Pubblicazione: (2026)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
di: Sato, Atsuki, et al.
Pubblicazione: (2025)

Testing with Non-identically Distributed Samples
di: Garg, Shivam, et al.
Pubblicazione: (2023)

Lower Bounds for Greedy Teaching Set Constructions
di: Compton, Spencer, et al.
Pubblicazione: (2025)

A Characterization of List Language Identification in the Limit
di: Charikar, Moses, et al.
Pubblicazione: (2025)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
di: Alman, Josh, et al.
Pubblicazione: (2024)

Differentially Private Verification of Distribution Properties
di: Du, Elbert, et al.
Pubblicazione: (2026)

Low-Degree Method Fails to Predict Robust Subspace Recovery
di: Jia, He, et al.
Pubblicazione: (2026)

On the Hardness of Approximation of the Fair k-Center Problem
di: Thejaswi, Suhas
Pubblicazione: (2026)

Efficient and Private Property Testing via Indistinguishability
di: Dwork, Cynthia, et al.
Pubblicazione: (2025)

Fast decision tree learning solves hard coding-theoretic problems
di: Koch, Caleb, et al.
Pubblicazione: (2024)

Adaptive and oblivious statistical adversaries are equivalent
di: Blanc, Guy, et al.
Pubblicazione: (2024)

Private graphon estimation via sum-of-squares
di: Chen, Hongjie, et al.
Pubblicazione: (2024)