Cover Image

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hanneke, Steve, Meng, Qinglin, Moran, Shay, Shaeiri, Amirreza
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Data Structures and Algorithms Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Is Transductive Learning Equivalent to PAC Learning?
by: Dughmi, Shaddin, et al.
Published: (2024)

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

Adversarial Resilience in Sequential Prediction via Abstention
by: Goel, Surbhi, et al.
Published: (2023)

Private List Learnability vs. Online List Learnability
by: Hanneke, Steve, et al.
Published: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

Complexity of Non-Log-Concave Sampling in Fisher Information
by: Chewi, Sinho, et al.
Published: (2026)

Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination
by: Diakonikolas, Ilias, et al.
Published: (2026)

High-Dimensional Gaussian Mean Estimation under Realizable Contamination
by: Diakonikolas, Ilias, et al.
Published: (2026)

On the Statistical Complexity of Sample Amplification
by: Axelrod, Brian, et al.
Published: (2022)

Smoothed Analysis of Learning from Positive Samples
by: Lee, Jane H., et al.
Published: (2025)

Sample-Efficient Private Learning of Mixtures of Gaussians
by: Ashtiani, Hassan, et al.
Published: (2024)

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
by: Fioravanti, Simone, et al.
Published: (2024)

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
by: Blanca, Antonio, et al.
Published: (2022)

Computing High-dimensional Confidence Sets for Arbitrary Distributions
by: Gao, Chao, et al.
Published: (2025)

The Geometry of Efficient Nonconvex Sampling
by: Vempala, Santosh S., et al.
Published: (2026)

Robustly Learning Single-Index Models via Alignment Sharpness
by: Zarifis, Nikos, et al.
Published: (2024)

In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
by: Kook, Yunbum, et al.
Published: (2024)

Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
by: Kook, Yunbum, et al.
Published: (2024)

Sampling and Identity-Testing Without Approximate Tensorization of Entropy
by: Gay, William, et al.
Published: (2025)

Sample-Efficient Linear Regression with Self-Selection Bias
by: Gaitonde, Jason, et al.
Published: (2024)

Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel
by: Gupta, Shivam, et al.
Published: (2024)

Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation
by: Compton, Spencer, et al.
Published: (2025)

Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
by: Gomez-Leos, Alejandro, et al.
Published: (2024)

An Optimal Sauer Lemma Over $k$-ary Alphabets
by: Hanneke, Steve, et al.
Published: (2026)

One-Shot Learning for k-SAT
by: Galanis, Andreas, et al.
Published: (2025)

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

DDPM Score Matching and Distribution Learning
by: Chewi, Sinho, et al.
Published: (2025)

Transfer Learning Beyond Bounded Density Ratios
by: Kalavasis, Alkis, et al.
Published: (2024)

On Learning Parallel Pancakes with Mostly Uniform Weights
by: Diakonikolas, Ilias, et al.
Published: (2025)

Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
by: Gao, Chao, et al.
Published: (2025)

Statistical Query Lower Bounds for Learning Truncated Gaussians
by: Diakonikolas, Ilias, et al.
Published: (2024)

Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Learning Multinomial Logits in $O(n \log n)$ time
by: Chierichetti, Flavio, et al.
Published: (2026)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
by: Attias, Idan, et al.
Published: (2025)

Robust Learning of Multi-index Models via Iterative Subspace Approximation
by: Diakonikolas, Ilias, et al.
Published: (2025)

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

Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
by: Diakonikolas, Ilias, et al.
Published: (2024)

Query Lower Bounds for Diffusion Sampling
by: Xun, Zhiyang, et al.
Published: (2026)