Sham M. Kakade

Risk Comparisons in Linear Regression: Implicit Regularization Dominates Explicit Regularization (Extended Abstract) COLT 2026 A New Perspective on Shampoo's Preconditioner ICLR 2025 Deconstructing What Makes a Good Optimizer for Autoregressive Language Models ICLR 2025 Eliminating Position Bias of Language Models: A Mechanistic Approach ICLR 2025 Flash Inference: Near Linear Time Inference for Long Convolution Sequence Models and Beyond ICLR 2025 Follow My Instruction and Spill the Beans: Scalable Data Extraction from Retrieval-Augmented Generation Systems ICLR 2025 How Does Critical Batch Size Scale in Pre-training? ICLR 2025 Mind the Gap: Examining the Self-Improvement Capabilities of Large Language Models ICLR 2025 Mixture of Parrots: Experts improve memorization more than reasoning ICLR 2025 SOAP: Improving and Stabilizing Shampoo using Adam for Language Modeling ICLR 2025 The Role of Sparsity for Length Generalization in LLMs ICML 2025 Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions ICML 2025 Universal Length Generalization with Turing Programs ICML 2025 Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning ICML 2024 Feature emergence via margin maximization: case studies in algebraic tasks ICLR 2024 Matching the Statistical Query Lower Bound for k-Sparse Parity Problems with Sign Stochastic Gradient Descent NeurIPS 2024 Q-Probe: A Lightweight Approach to Reward Maximization for Language Models ICML 2024 Repeat After Me: Transformers are Better than State Space Models at Copying ICML 2024 Scaling Laws in Linear Regression: Compute, Parameters, and Data NeurIPS 2024 Benign Overfitting of Constant-Stepsize SGD for Linear Regression JMLR 2023 Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron ICML 2023 Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games ICML 2023 Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity JMLR 2023 On Provable Copyright Protection for Generative Models ICML 2023 The Role of Coverage in Online Reinforcement Learning ICLR 2023 Anti-Concentrated Confidence Bonuses For Scalable Exploration ICLR 2022 Multi-Stage Episodic Control for Strategic Exploration in Text Games ICLR 2022 Few-Shot Learning via Learning the Representation, Provably ICLR 2021 On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift JMLR 2021 Optimal Regularization can Mitigate Double Descent ICLR 2021 What are the Statistical Limits of Offline RL with Linear Function Approximation? ICLR 2021 Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? ICLR 2020 Meta-Learning with Implicit Gradients NeurIPS 2019 Open Problem: Do Good Algorithms Necessarily Query Bad Points? COLT 2019 The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares NeurIPS 2019 Accelerating Stochastic Gradient Descent for Least Squares Regression COLT 2018 A Smoother Way to Train Structured Prediction Models NeurIPS 2018 On the insufficiency of existing momentum schemes for Stochastic Optimization ICLR 2018 Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification JMLR 2018 Provably Correct Automatic Sub-Differentiation for Qualified Programs NeurIPS 2018 How to Escape Saddle Points Efficiently ICML 2017 Learning Overcomplete HMMs NeurIPS 2017 Towards Generalization and Simplicity in Continuous Control NeurIPS 2017 Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent NeurIPS 2016 Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja’s Algorithm COLT 2016 Competing with the Empirical Risk Minimizer in a Single Pass COLT 2015 Convergence Rates of Active Learning for Maximum Likelihood Estimation NeurIPS 2015 Super-Resolution Off the Grid NeurIPS 2015 A Tensor Approach to Learning Mixed Membership Community Models JMLR 2014 Tensor Decompositions for Learning Latent Variable Models JMLR 2014 A Risk Comparison of Ordinary Least Squares vs Ridge Regression JMLR 2013 When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity NeurIPS 2013 A Method of Moments for Mixture Models and Hidden Markov Models COLT 2012 A Spectral Algorithm for Latent Dirichlet Allocation NeurIPS 2012 Identifiability and Unmixing of Latent Parse Trees NeurIPS 2012 Learning Mixtures of Tree Graphical Models NeurIPS 2012 Random Design Analysis of Ridge Regression COLT 2012 Regularization Techniques for Learning with Matrices JMLR 2012 Towards Minimax Policies for Online Linear Optimization with Bandit Feedback COLT 2012 (weak) Calibration is Computationally Hard COLT 2012 Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression NeurIPS 2011 Spectral Methods for Learning Multivariate Latent Tree Structure NeurIPS 2011 Stochastic convex optimization with bandit feedback NeurIPS 2011 Learning from Logged Implicit Exploration Data NeurIPS 2010 Multi-Label Prediction via Compressed Sensing NeurIPS 2009 Mind the Duality Gap: Logarithmic regret algorithms for online optimization NeurIPS 2008 On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization NeurIPS 2008 On the Generalization Ability of Online Strongly Convex Programming Algorithms NeurIPS 2008 The Price of Bandit Information for Online Optimization NeurIPS 2007 Maximum Entropy Correlated Equilibria AISTATS 1999