3 citations · 4 across the 16 of their papers we have counts for
16 papers
An Optimal Agnostic PAC Algorithm
Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
Let be a class of finite VC dimension . Writing for the binary risk and , we construct a learner achieving the statistical…
Beyond Modern Asymptotics for Log-Likelihood Ratios in Logistic Regression
Hugo Chardon, Reese Pathak, Nikita Zhivotovskiy
We characterize the finite sample behavior of the log-likelihood ratio statistic in binary logistic regression, uniformly over both the design and the target parameter. For $n\geq…
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…
Efficient Logistic Regression with Mixture of Sigmoids
Federico Di Gennaro, Saptarshi Chakraborty, Nikita Zhivotovskiy
This paper studies the Exponential Weights (EW) algorithm with an isotropic Gaussian prior for online logistic regression. We show that the near-optimal worst-case regret bound $O(…
Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
Spencer Compton, Gábor Lugosi, Jaouad Mourtada +2
We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density , the goal is to construct an estimator such that…
Gaussian Width of Convex Sets via Integral Decompositions, Projections, and the Distribution of Intrinsic Volumes
Reese Pathak, Nikita Zhivotovskiy
We revisit the problem of bounding the expected supremum of a canonical Gaussian process indexed by a convex set . We develop two decompositions for the Gau…
Early science acceleration experiments with GPT-5
Sébastien Bubeck, Christian Coester, Ronen Eldan +11
AI models like GPT-5 are an increasingly valuable tool for scientists, but many remain unaware of the capabilities of frontier AI. We present a collection of short case studies in…
Consistency and inconsistency in -means clustering
Moïse Blanchard, Adam Quinn Jaffe, Nikita Zhivotovskiy
A celebrated result of Pollard proves asymptotic consistency for -means clustering when the population distribution has finite variance. In this work, we point out that the popu…
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…
Dimension-free Private Mean Estimation for Anisotropic Distributions
Yuval Dagan, Michael I. Jordan, Xuelin Yang +2
We present differentially private algorithms for high-dimensional mean estimation. Previous private estimators on distributions over suffer from a curse of dimension…
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…
Derandomizing Multi-Distribution Learning
Kasper Green Larsen, Omar Montasser, Nikita Zhivotovskiy
Multi-distribution or collaborative learning involves learning a single predictor that works well across multiple data distributions, using samples from each during training. Recen…
Revisiting Agnostic PAC Learning
Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
PAC learning, dating back to Valiant'84 and Vapnik and Chervonenkis'64,'74, is a classic model for studying supervised learning. In the agnostic setting, we have access to a hypoth…
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…