22 citations · 87 across the 27 of their papers we have counts for
31 papers
A remark on the majorizing measures theorem for general processes
Reese Pathak, Nikita Zhivotovskiy
We show that the lower bound in the majorizing measures theorem holds for a large class of random vectors. Specifically, suppose is a centered random vector in $\mathbf{…
High-Probability Risk Bounds via Sequential Predictors
Dirk van der Hoeven, Nikita Zhivotovskiy, Nicolò Cesa-Bianchi
Online learning methods yield sequential regret bounds under minimal assumptions and provide in-expectation risk bounds for statistical learning. However, despite the apparent adva…
Local Risk Bounds for Statistical Aggregation
Jaouad Mourtada, Tomas Vaškevičius, Nikita Zhivotovskiy
In the problem of aggregation, the aim is to combine a given class of base predictors to achieve predictions nearly as accurate as the best one. In this flexible framework, no assu…
Optimal PAC Bounds Without Uniform Convergence
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty +1
In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hann…
Exploring Local Norms in Exp-concave Statistical Learning
Nikita Puchkin, Nikita Zhivotovskiy
We consider the problem of stochastic convex optimization with exp-concave losses using Empirical Risk Minimization in a convex class. Answering a question raised in several prior…
Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians
Arshak Minasyan, Nikita Zhivotovskiy
Assume that is an -contaminated sample of independent Gaussian vectors in with mean and covariance . In the strong $\v…
Robustifying Markowitz
Wolfgang Karl Härdle, Yegor Klochkov, Alla Petukhina +1
Markowitz mean-variance portfolios with sample mean and covariance as input parameters feature numerous issues in practice. They perform poorly out of sample due to estimation erro…
The One-Inclusion Graph Algorithm is not Always Optimal
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty +1
The one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth achieves an optimal in-expectation risk bound in the standard PAC classification setup. In one of the first…
A Regret-Variance Trade-Off in Online Learning
Dirk van der Hoeven, Nikita Zhivotovskiy, Nicolò Cesa-Bianchi
We consider prediction with expert advice for strongly convex and bounded losses, and investigate trade-offs between regret and "variance" (i.e., squared difference of learner's pr…
A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture
Afonso S. Bandeira, Antoine Maillard, Nikita Zhivotovskiy
In this expository note, we discuss an early partial coloring result of B. Kashin [C. R. Acad. Bulgare Sci., 1985]. Although this result only implies Spencer's six standard deviati…
Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails
Pedro Abdalla, Nikita Zhivotovskiy
We provide an estimator of the covariance matrix that achieves the optimal rate of convergence (up to constant factors) in the operator norm under two standard notions of data cont…
Dimension-free Bounds for Sums of Independent Matrices and Simple Tensors via the Variational Principle
Nikita Zhivotovskiy
We consider the deviation inequalities for the sums of independent by random matrices, as well as rank one random tensors. Our focus is on the non-isotropic case and the bo…
Stability and Deviation Optimal Risk Bounds with Convergence Rate
Yegor Klochkov, Nikita Zhivotovskiy
The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondrák, 2018, 2019), (Bousquet, Klochkov, Zhivotovskiy, 2020) contain a general…
Distribution-Free Robust Linear Regression
Jaouad Mourtada, Tomas Vaškevičius, Nikita Zhivotovskiy
We study random design linear regression with no assumptions on the distribution of the covariates and with a heavy-tailed response variable. In this distribution-free regression s…
Exponential Savings in Agnostic Active Learning through Abstention
Nikita Puchkin, Nikita Zhivotovskiy
We show that in pool-based active classification without assumptions on the underlying distribution, if the learner is given the power to abstain from some predictions by paying th…
On Mean Estimation for Heteroscedastic Random Variables
Luc Devroye, Silvio Lattanzi, Gabor Lugosi +1
We study the problem of estimating the common mean of independent symmetric random variables with different and unknown standard deviations .…
Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors
Tomas Vaškevičius, Nikita Zhivotovskiy
We study the problem of predicting as well as the best linear predictor in a bounded Euclidean ball with respect to the squared loss. When only boundedness of the data generating d…
Proper Learning, Helly Number, and an Optimal SVM Bound
Olivier Bousquet, Steve Hanneke, Shay Moran +1
The classical PAC sample complexity bounds are stated for any Empirical Risk Minimizer (ERM) and contain an extra logarithmic factor which is known to be necessary for…
Robust -means Clustering for Distributions with Two Moments
Yegor Klochkov, Alexey Kroshnin, Nikita Zhivotovskiy
We consider the robust algorithms for the -means clustering problem where a quantizer is constructed based on independent observations. Our main results are median of means…
Fast Rates for Online Prediction with Abstention
Gergely Neu, Nikita Zhivotovskiy
In the setting of sequential prediction of individual -sequences with expert advice, we show that by allowing the learner to abstain from the prediction by paying a cost…
Fast classification rates without standard margin assumptions
Olivier Bousquet, Nikita Zhivotovskiy
We consider the classical problem of learning rates for classes with finite VC dimension. It is well known that fast learning rates up to are achievable…
Sharper bounds for uniformly stable algorithms
Olivier Bousquet, Yegor Klochkov, Nikita Zhivotovskiy
Deriving generalization bounds for stable algorithms is a classical question in learning theory taking its roots in the early works by Vapnik and Chervonenkis (1974) and Rogers and…
Noise sensitivity of the top eigenvector of a Wigner matrix
Charles Bordenave, Gábor Lugosi, Nikita Zhivotovskiy
We investigate the noise sensitivity of the top eigenvector of a Wigner matrix in the following sense. Let be the top eigenvector of an Wigner matrix. Suppose that…
Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method
Yegor Klochkov, Nikita Zhivotovskiy
This paper is devoted to uniform versions of the Hanson-Wright inequality for a random vector with independent subgaussian components. The core technique of th…