3 citations · 4 across the 16 of their papers we have counts for
6 papers · 1 filter
Majority-of-Three is Optimal
Divit Rawal, Nikita Zhivotovskiy
We give a short proof that the majority vote of three independent consistent classifiers is an optimal learner in the realizable PAC setting. This proves optimality for the simples…
Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression
Fan Chen, Jian Qian, Alexander Rakhlin +1
Self-normalized martingale inequalities lie at the heart of confidence ellipsoids for online least squares and, more broadly, many bandit and reinforcement-learning results. Yet ex…
Lower Bounds for Greedy Teaching Set Constructions
Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy
A fundamental open problem in learning theory is to characterize the best-case teaching dimension of a concept class with finite VC dimensi…
Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
Omar Montasser, Abhishek Shetty, Nikita Zhivotovskiy
We revisit online binary classification by shifting the focus from competing with the best-in-class binary loss to competing against relaxed benchmarks that capture smoothed notion…
Refined Risk Bounds for Unbounded Losses via Transductive Priors
Jian Qian, Alexander Rakhlin, Nikita Zhivotovskiy
We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression, all characterized by unbounded loss…
Majority-of-Three: The Simplest Optimal Learner?
Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen +1
Developing an optimal PAC learning algorithm in the realizable setting, where empirical risk minimization (ERM) is suboptimal, was a major open problem in learning theory for decad…