Agnostic Learning

Follow this topic Ask about this topic

Latest papers

19 papers3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Self-Directed Apple Tasting
Nov 4, 2026Tanmay Devale, Reed Phillips, Arvind RamaswamiOnline Learning Statistical Learning Theory
Department of Computer Science, Purdue University
Agnostic Learning by Imitating
Nov 3, 2026Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade +3Agnostic Learning Statistical Learning Theory
Stanford University · Apple · Oxford University +2
Gaussian Partitioning for Reliable Learning of Multi-Index Models
Nov 3, 2026Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1Learning with Distribution Shift Agnostic Learning
University of Wisconsin-Madison · University of California, San Diego
Privacy for Free in Efficient Agnostic Halfspace Learning
Nov 3, 2026Giorgio Racca, Amartya Sanyal, Vikrant SinghalHalfspace Learning Agnostic Learning
Department of Computer Science, University of Copenhagen
PAC Learning with Multiple Correct Answers
Nov 3, 2026Steve Hanneke, Farnam Mansouri, Alireza F. Pour +2PAC Learning Statistical Learning Theory
Department of Computer Sciences, Purdue University, USA. · University of Waterloo and Vector Institute, Canada.
Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners
Oct 30, 2026Ilias Diakonikolas, Daniel M. Kane, Mingchen MaStatistical Learning Theory Classification
University of Wisconsin-Madison · University of California, San Diego
Self-normalized Bernstein Inequalities for Regenerative Processes and Applications to Learning Without Independence
Oct 21, 2026Imon Banerjee, Pierre AlquierGeneralization Bounds Agnostic Learning
University of Chicago, Booth School of Business · ESSEC Business School, Asia-Pacific campus, Singapore
The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
Oct 18, 2026Guangjian ZhangAgnostic Learning Sample Complexity
An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension
Aug 31, 2026Guangjian Zhang, Zhengyi Yang, Xiaoyang WangAgnostic Learning Sample Compression
Two Dimensions Govern Agnostic Multiclass Transductive Learning
Aug 26, 2026Pahan DewasurendraAgnostic Learning Multiclass Classification
Johns Hopkins University
Robust Regression of General ReLUs with Queries
Jun 9, 2026Ilias Diakonikolas, Daniel M. Kane, Mingchen MaReLU Neural Networks Active Learning
University of Wisconsin-Madison · University of California, San Diego
Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals
May 26, 2026Sergei Tikhonov, Arsen VasilyanAgnostic Learning Boolean Function Learning
UT Austin
Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals
May 20, 2026Ilias Diakonikolas, Giannis Iakovidis, Mingchen MaAgnostic Learning Multiclass Classification
University of Wisconsin-Madison
Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
May 13, 2026Shashaank Aiyer, Yishay Mansour, Shay Moran +2Agnostic Learning Statistical Learning Theory
University of Maryland · Tel Aviv University and Google Research · Technion and Google Research +1
Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
Apr 29, 2026Jizhou Huang, Brendan JubaAgnostic Learning Statistical Learning Theory
Meta · Washington Universtiy in St. Louis
Robust Learning with Optimal Error
Apr 2, 2026Guy BlancAgnostic Learning Robust Classification
Stanford
Agnostic learning in (almost) optimal time via Gaussian surface area
Mar 6, 2026Lucas Pesenti, Lucas Slot, Manuel WiedmerAgnostic Learning Statistical Learning Theory
ETH Zurich · University of Amsterdam
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Jul 1, 2024Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis +2Agnostic Learning Margin-Based Learning
a University of Texas at Austin · b University of California, Los Angeles
A Competitive Algorithm for Agnostic Active Learning
Oct 28, 2023Eric Price, Yihan ZhouActive Learning Agnostic Learning
Department of Computer Science, University of Texas at Austin

Nov 4, 2026J/K move · Enter open · S save

Self-Directed Apple Tasting

Tanmay Devale, Reed Phillips, Arvind Ramaswami

Department of Computer Science, Purdue University

Online Learning Statistical Learning Theory Minimax Regret Agnostic Learning

Open paper AskPDF arXiv

We study the classical apple-tasting setting, a partial feedback model in which the learner observes the true label only when it predicts

1

. A combinatorial characterization for the rates of this problem in the online adversarial setting has been studied by Raman et al. (2024). We study the self-directed setting, in which the learner can adaptively choose the order of the points it predicts on. In the realizable setting, we establish a tetrachotomy on the expected minimax number of mistakes made by any learner. Depending on the VC dimension, the

\emptyset

-centered star number, and the self-directed dimension, we show that the rates could possibly be

Θ(1)

O(\log n) \cap ω(1)

\tilde Θ(\sqrt{n})

, or

Θ(n)

. In the agnostic setting, the minimax regret is

\tilde Θ(\sqrt{n})

Θ(n)

, depending on the VC dimension.