Permutational Rademacher Complexity - A New Complexity Measure for Transductive Learning. - Ilya O. Tolstikhin; Nikita Zhivotovskiy; Gilles Blanchard (ALT, 2015)

Optimal learning via local entropies and sample compression. - Nikita Zhivotovskiy (COLT, 2017)

Localization of VC classes: Beyond local Rademacher complexities. - Nikita Zhivotovskiy; Steve Hanneke (Theor. Comput. Sci., 2018)

Fast classification rates without standard margin assumptions. - Olivier Bousquet; Nikita Zhivotovskiy (CoRR, 2019)

Proper Learning, Helly Number, and an Optimal SVM Bound. - Olivier Bousquet; Steve Hanneke; Shay Moran; Nikita Zhivotovskiy (COLT, 2020)

Sharper Bounds for Uniformly Stable Algorithms. - Olivier Bousquet; Yegor Klochkov; Nikita Zhivotovskiy (COLT, 2020)

Fast Rates for Online Prediction with Abstention. - Gergely Neu; Nikita Zhivotovskiy (COLT, 2020)

Robust k-means Clustering for Distributions with Two Moments. - Yegor Klochkov; Alexey Kroshnin; Nikita Zhivotovskiy (CoRR, 2020)

Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors. - Tomas Vaskevicius; Nikita Zhivotovskiy (CoRR, 2020)

On Mean Estimation for Heteroscedastic Random Variables. - Luc Devroye; Silvio Lattanzi; Gábor Lugosi; Nikita Zhivotovskiy (CoRR, 2020)

When are epsilon-nets small? - Andrey Kupavskii; Nikita Zhivotovskiy (J. Comput. Syst. Sci., 2020)

Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$. - Yegor Klochkov; Nikita Zhivotovskiy (NeurIPS, 2021)

Distribution-Free Robust Linear Regression. - Jaouad Mourtada; Tomas Vaskevicius; Nikita Zhivotovskiy (CoRR, 2021)

A Regret-Variance Trade-Off in Online Learning. - Dirk van der Hoeven; Nikita Zhivotovskiy; Nicolò Cesa-Bianchi (NeurIPS, 2022)

Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails. - Pedro Abdalla; Nikita Zhivotovskiy (CoRR, 2022)

A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture. - Afonso S. Bandeira; Antoine Maillard; Nikita Zhivotovskiy (CoRR, 2022)

Robustifying Markowitz. - Wolfgang Karl Härdle; Yegor Klochkov; Alla Petukhina; Nikita Zhivotovskiy (CoRR, 2022)

Exponential Savings in Agnostic Active Learning Through Abstention. - Nikita Puchkin; Nikita Zhivotovskiy (IEEE Trans. Inf. Theory, 2022)

The One-Inclusion Graph Algorithm is not Always Optimal. - Ishaq Aden-Ali; Yeshwanth Cherapanamjeri; Abhishek Shetty; Nikita Zhivotovskiy (COLT, 2023)

Local Risk Bounds for Statistical Aggregation. - Jaouad Mourtada; Tomas Vaskevicius; Nikita Zhivotovskiy (COLT, 2023)

Exploring Local Norms in Exp-concave Statistical Learning. - Nikita Puchkin; Nikita Zhivotovskiy (COLT, 2023)

Optimal PAC Bounds without Uniform Convergence. - Ishaq Aden-Ali; Yeshwanth Cherapanamjeri; Abhishek Shetty; Nikita Zhivotovskiy (FOCS, 2023)

Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians. - Arshak Minasyan; Nikita Zhivotovskiy (CoRR, 2023)

High-Probability Risk Bounds via Sequential Predictors. - Dirk van der Hoeven; Nikita Zhivotovskiy; Nicolò Cesa-Bianchi (CoRR, 2023)

Majority-of-Three: The Simplest Optimal Learner? - Ishaq Aden-Ali; Mikael Møller Høandgsgaard; Kasper Green Larsen; Nikita Zhivotovskiy (COLT, 2024)

Revisiting Agnostic PAC Learning. - Steve Hanneke; Kasper Green Larsen; Nikita Zhivotovskiy (FOCS, 2024)

Dimension-free Private Mean Estimation for Anisotropic Distributions. - Yuval Dagan; Michael I. Jordan; Xuelin Yang; Lydia Zakynthinou; Nikita Zhivotovskiy (NeurIPS, 2024)

Derandomizing Multi-Distribution Learning. - Kasper Green Larsen; Omar Montasser; Nikita Zhivotovskiy (NeurIPS, 2024)

Majority-of-Three: The Simplest Optimal Learner? - Ishaq Aden-Ali; Mikael Møller Høgsgaard; Kasper Green Larsen; Nikita Zhivotovskiy (CoRR, 2024)

Refined Risk Bounds for Unbounded Losses via Transductive Priors. - Jian Qian; Alexander Rakhlin; Nikita Zhivotovskiy (CoRR, 2024)

Lower Bounds for Greedy Teaching Set Constructions. - Spencer Compton; Chirag Pabbaraju; Nikita Zhivotovskiy (COLT, 2025)

Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks. - Omar Montasser; Abhishek Shetty; Nikita Zhivotovskiy (COLT, 2025)