12 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…
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…
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(…