An Optimal Agnostic PAC Algorithm

2026-08-06 · Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy arxiv

Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<δ\le 1/2$, with probability at least $1-δ$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). \] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

📄 PDF Abstract BibTeX arXiv:2608.06363

Code (0)

등록된 구현이 없습니다.

Sample-Near-Optimal Agnostic Boosting with Improved Running Time

2026-01-16 · Arthur da Cunha, Mikael Møller Høgsgaard, Andrea Paudice arxiv

Boosting is a powerful method that turns weak learners, which perform only slightly better than random guessing, into strong learners with high accuracy. While boosting is well understood in the classic setting, it is le…

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals

2021-02-08 · Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis

We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP duality. For Boolean-valued concept classes, w…

regression

Agnostic $Q$-learning with Function Approximation in Deterministic Systems: Near-Optimal Bounds on Approximation Error and Sample Complexity

2020-12-01 · NeurIPS 2020 12 · Simon S. Du, Jason D. Lee, Gaurav Mahajan, Ruosong Wang

The current paper studies the problem of agnostic $Q$-learning with function approximation in deterministic systems where the optimal $Q$-function is approximable by a function in the class $\mathcal{F}$ with approximati…

Q-Learning

Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning

2023-04-14 · Gen Li, Yuling Yan, Yuxin Chen, Jianqing Fan

This paper studies reward-agnostic exploration in reinforcement learning (RL) -- a scenario where the learner is unware of the reward functions during the exploration stage -- and designs an algorithm that improves over …

Offline RL reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

2026-02-18 · Oran Ridel, Alon Cohen arxiv

We study reward-free and reward-agnostic exploration in episodic finite-horizon Markov decision processes (MDPs), where an agent explores an unknown environment without observing external rewards. Reward-free exploration…