Alexander Rakhlin

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness COLT 2026 High-Accuracy Log-Concave Sampling with Stochastic Queries COLT 2026 Learning with Simulators: No Regret in a Computationally Bounded World COLT 2026 Refined Risk Bounds for Unbounded Losses via Transductive Priors JMLR 2026 Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression COLT 2026 The Sample Complexity of Multiclass and Sparse Contextual Bandits COLT 2026 Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy COLT 2025 Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective ICML 2025 Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF ICLR 2025 GaussMark: A Practical Approach for Structural Watermarking of Language Models ICML 2025 On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy COLT 2025 Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability NeurIPS 2024 How Does Variance Shape the Regret in Contextual Bandits? NeurIPS 2024 How Far Is Too Far? Studying the Effects of Domain Discrepancy on Masked Language Models COLING 2024 Near-Optimal Learning and Planning in Separated Latent MDPs COLT 2024 Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data COLT 2024 Online Estimation via Offline Estimation: An Information-Theoretic Framework NeurIPS 2024 On the Performance of Empirical Risk Minimization with Smoothed Data COLT 2024 Random Latent Exploration for Deep Reinforcement Learning ICML 2024 The Non-linear F-Design and Applications to Interactive Learning ICML 2024 The Power of Resets in Online Reinforcement Learning NeurIPS 2024 Convergence of Adam Under Relaxed Assumptions NeurIPS 2023 Convex and Non-convex Optimization Under Generalized Smoothness NeurIPS 2023 Efficient Model-Free Exploration in Low-Rank MDPs NeurIPS 2023 Model-Free Reinforcement Learning with the Decision-Estimation Coefficient NeurIPS 2023 On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring COLT 2023 On the Variance, Admissibility, and Stability of Empirical Risk Minimization NeurIPS 2023 Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making COLT 2023 Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL ICML 2023 When is Agnostic Reinforcement Learning Statistically Tractable? NeurIPS 2023 Damped Online Newton Step for Portfolio Selection COLT 2022 Intrinsic Dimension Estimation Using Wasserstein Distance JMLR 2022 On the Complexity of Adversarial Decision Making NeurIPS 2022 Smoothed Online Learning is as Easy as Statistical Learning COLT 2022 Finite Time LTI System Identification JMLR 2021 Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective COLT 2021 Majorizing Measures, Sequential Complexities, and Online Learning COLT 2021 On the Minimal Error of Empirical Risk Minimization COLT 2021 Top-k eXtreme Contextual Bandits with Arm Hierarchy ICML 2021 Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles ICML 2020 Learning nonlinear dynamical systems from a single trajectory L4DC 2020 Learning the Linear Quadratic Regulator from Nonlinear Observations NeurIPS 2020 On Suboptimality of Least Squares with Application to Estimation of Convex Bodies COLT 2020 On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels COLT 2020 Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information JMLR 2020 Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon COLT 2019 Does data interpolation contradict statistical optimality? AISTATS 2019 Fisher-Rao Metric, Geometry, and Complexity of Neural Networks AISTATS 2019 Near optimal finite time identification of arbitrary linear dynamical systems ICML 2019 Online Learning: Sufficient Statistics and the Burkholder Method COLT 2018 Size-Independent Sample Complexity of Neural Networks COLT 2018 Efficient Online Multiclass Prediction on Graphs via Surrogate Losses AISTATS 2017 Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis COLT 2017 On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities COLT 2017 ZigZag: A New Approach to Adaptive Online Learning COLT 2017 BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits ICML 2016 Conference on Learning Theory 2016: Preface COLT 2016 Adaptive Online Learning NeurIPS 2015 Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions COLT 2015 Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints COLT 2015 Learning with Square Loss: Localization through Offset Rademacher Complexity COLT 2015 Online Learning via Sequential Complexities JMLR 2015 Online Optimization : Competing with Dynamic Comparators AISTATS 2015 Online Non-Parametric Regression COLT 2014 Competing With Strategies COLT 2013 Localization and Adaptation in Online Learning AISTATS 2013 Online Learning with Predictable Sequences COLT 2013 No Internal Regret via Neighborhood Watch AISTATS 2012 Complexity-Based Approach to Calibration with Checking Rules COLT 2011 Lower Bounds for Passive and Active Learning NeurIPS 2011 Online Learning: Beyond Regret COLT 2011 Online Learning: Stochastic, Constrained, and Smoothed Adversaries NeurIPS 2011 Stochastic convex optimization with bandit feedback NeurIPS 2011 Online Learning: Random Averages, Combinatorial Parameters, and Learnability NeurIPS 2010 Random Walk Approach to Regret Minimization NeurIPS 2010 Adaptive Online Gradient Descent NeurIPS 2007 Stability of K-Means Clustering NeurIPS 2006 Stability Properties of Empirical Risk Minimization over Donsker Classes JMLR 2006