Publications

* indicates alphabetical ordering of author names.

Surveys

  1. Stochastic Gradient Descent and Its Variants in Machine Learning
    P. Netrapalli
    Journal of the Indian Institute of Science

Research articles

  1. TheoPhysEval: Assessing AI agents at autonomous theoretical physics problem solving
    A. R. Chandra, A. Mahajan, A. Sanyal, M. Wang, S. Chakraborty, S. Chakraborty, S. Chandrasekharan, R. Govindarajan, A. Goyal, J. J. Heckman, Y. Iqbal, D. Jaganathan, S. Kapoor, A. Karch, P. Khandare, S. Krishna, A. Kundu, A. Laddha, T. Lin, S. Maity, N. Mathur, S. N. Meynet, A. Mininno, A. Mishra, V. Niranjan, A. Prakash, P. Rath, D. Roy, D. Sarkar, S. Sastry, G. Shiu, A. Sinha, T. Van Riet, P. Netrapalli and S. Raju
    arXiv preprint, 2026

  2. A Faster Generalized Two-Stage Approximate Top-K
    Y. Samaga, V. Yerram, S. R. Babbula, P. Jain and P. Netrapalli
    Transactions on Machine Learning Research (TMLR) 2026

  3. Period spacings and global seismic parameters for K2 red giants using deep learning
    N. Ghanghas, S. Dhanpal, S. Hanasoge, P. Netrapalli and K. Shanmugam
    arXiv preprint, 2026

  4. A model of errors in transformers
    S. Raju and P. Netrapalli
    ICML 2026

  5. Compressing Many-Shots in In-Context Learning
    D. Khatri, P. Kulkarni, N. Gupta, V. Yerram, L. Peng, J. Yagnik, P. Netrapalli, C.-J. Hsieh, A. Go, I. S. Dhillon, A. Kusupati and P. Jain
    ICLR 2026

  6. Spark Transformer: Reactivating Sparsity in FFN and Attention
    C. You, K. Wu, Z. Jia, L. Chen, S. Bhojanapalli, J. Guo, U. Evci, J. Wassenberg, P. Netrapalli, J. J. Willcock, S. Subramanian, F. Chern, A. Andreev, S. Pathak, F. Yu, P. Jain, D. E. Culler, H. M. Levy and S. Kumar
    NeurIPS 2025

  7. Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities
    Gemini Team, Google
    Technical Report, 2025

  8. FoodLens: Fine-Grained and Multi-label Classification of Indian Food Images
    J. Alla, Y. Samaga, A. Vaswani, P. Netrapalli, S. Kapania, P. Kumar and N. Hegde
    IMPROVE 2025

  9. The Feature Speed Formula: a flexible approach to scale hyper-parameters of deep neural networks [*]
    L. Chizat and P. Netrapalli
    NeurIPS 2024

  10. All Mistakes Are Not Equal: Comprehensive Hierarchy Aware Multi-label Predictions (CHAMP)
    A. Vaswani, G. Aggarwal, P. Netrapalli and N. G. Hegde
    ICPR 2024

  11. Tandem Transformers for Inference Efficient LLMs
    Aishwarya P S, P. A. Nair, Y. Samaga, T. Boyd, S. Kumar, P. Jain and P. Netrapalli
    ICML 2024

  12. Transformer Designs for In-Context Learning in Foundation Models for Time Series Forecasting with Covariates
    A. Dange, V. Raj, P. Netrapalli and S. Sarawagi
    ICML 2024 Workshop on Theoretical Foundations of Foundation Models (TF2M)

  13. Second Order Methods for Bandit Optimization and Control
    A. Suggala, Y. J. Sun, P. Netrapalli and E. Hazan
    COLT 2024

  14. Consistent Multiclass Algorithms for Complex Metrics and Constraints
    H. Narasimhan, H. G. Ramaswamy, S. K. Tavker, D. Khurana, P. Netrapalli and S. Agarwal
    Journal of Machine Learning Research (JMLR) 2024, Vol. 25

  15. HiRE: High Recall Approximate Top-k Estimation for Efficient LLM Inference
    Y. Samaga B L, V. Yerram, C. You, S. Bhojanapalli, S. Kumar, P. Jain and P. Netrapalli
    arXiv preprint, 2024

  16. Simplicity Bias in 1-Hidden Layer Neural Networks
    D. Morwani, J. Batra, P. Jain and P. Netrapalli
    NeurIPS 2023

  17. Multi-User Reinforcement Learning with Low Rank Rewards [*]
    N. Agarwal, P. Jain, S. Kowshik, D. Nagaraj and P. Netrapalli
    ICML 2023

  18. Near Optimal Heteroscedastic Regression with Symbiotic Learning [*]
    D. Baby, A. Das, D. Nagaraj and P. Netrapalli
    COLT 2023

  19. Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making
    Q. Liu, P. Netrapalli, C. Szepesvári and C. Jin
    STOC 2023

  20. Learning an Invertible Output Mapping Can Mitigate Simplicity Bias in Neural Networks
    S. Addepalli, A. Nasery, R. V. Babu, P. Netrapalli and P. Jain
    ICLR 2023

  21. Reproducibility in Optimization: Theoretical Framework and Limits [*]
    K. Ahn, P. Jain, Z. Ji, S. Kale, P. Netrapalli and G. I. Shamir
    NeurIPS 2022

  22. DAFT: Distilling Adversarially Fine-tuned Models for Better OOD Generalization
    A. Nasery, S. Addepalli, P. Netrapalli and P. Jain
    arXiv preprint, 2022

  23. MET: Masked Encoding for Tabular Data
    K. Majmundar, S. Goyal, P. Netrapalli and P. Jain
    arXiv preprint, 2022

  24. Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs [*]
    N. Agarwal, S. Chaudhuri, P. Jain, D. Nagaraj and P. Netrapalli
    ICLR 2022

  25. Focus on the Common Good: Group Distributional Robustness Follows
    V. Piratla, P. Netrapalli and S. Sarawagi
    ICLR 2022

  26. Minimax Optimization with Smooth Algorithmic Adversaries [*]
    T. Fiez, C. Jin, P. Netrapalli and L. Ratliff
    ICLR 2022

  27. Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness [*]
    A. Garg, R. Kothari, P. Netrapalli and S. Sherif
    NeurIPS 2021 (Spotlight) & QIP 2022

  28. Sample Efficient Linear Meta-Learning by Alternating Minimization
    K. K. Thekumparampil, P. Jain, P. Netrapalli and S. Oh
    NeurIPS 2021

  29. Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems [*]
    P. Jain, S. S. Kowshik, D. Nagaraj and P. Netrapalli
    NeurIPS 2021 (Spotlight)

  30. Streaming Linear System Identification with Reverse Experience Replay [*]
    P. Jain, S. S. Kowshik, D. Nagaraj and P. Netrapalli
    NeurIPS 2021

  31. Do Input Gradients Highlight Discriminative Features?
    H. Shah, P. Jain and P. Netrapalli
    NeurIPS 2021

  32. Efficient Bandit Convex Optimization: Beyond Linear Losses
    A. S. Suggala, P. Ravikumar and P. Netrapalli
    COLT 2021

  33. Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization
    A. Saha, N. Natarajan, P. Netrapalli and P. Jain
    ICML 2021

  34. No quantum speedup over gradient descent for non-smooth convex optimization [*]
    A. Garg, R. Kothari, P. Netrapalli and S. Sherif
    ITCS 2021 & QIP 2021

  35. The Pitfalls of Simplicity Bias in Neural Networks
    H. Shah, K. Tamuly, A. Raghunathan, P. Jain and P. Netrapalli
    NeurIPS 2020

  36. Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
    K. K. Thekumparampil, P. Jain, P. Netrapalli and S. Oh
    NeurIPS 2020 (Spotlight)

  37. Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [*]
    G. Bresler, P. Jain, D. Nagaraj, P. Netrapalli and X. Wu
    NeurIPS 2020 (Spotlight)

  38. MOReL : Model-Based Offline Reinforcement Learning
    R. Kidambi, A. Rajeswaran, P. Netrapalli and T. Joachims
    NeurIPS 2020

  39. Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games
    A. S. Suggala and P. Netrapalli
    NeurIPS 2020

  40. On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
    C. Jin, P. Netrapalli, R. Ge, S. M. Kakade and M. I. Jordan
    Journal of the ACM (JACM) 2021, Vol. 68, Issue 2, Article 11

  41. Efficient Domain Generalization via Common-Specific Low-Rank Decomposition
    V. Piratla, P. Netrapalli and S. Sarawagi
    ICML 2020

  42. What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
    C. Jin, P. Netrapalli and M. I. Jordan
    ICML 2020

  43. Online Non-Convex Learning: Following the Perturbed Leader is Optimal
    A. S. Suggala and P. Netrapalli
    ALT 2020 Best student paper award

  44. Leverage Score Sampling for Faster Accelerated Regression and ERM [*]
    N. Agarwal, S. M. Kakade, R. Kidambi, Y. T. Lee, P. Netrapalli and A. Sidford
    ALT 2020

  45. P-SIF: Document Embeddings Using Partition Averaging
    V. Gupta, A. Saw, P. Nokhiz, P. Netrapalli, P. Rai and P. Talukdar
    AAAI 2020

  46. Efficient Algorithms for Smooth Minimax Optimization
    K. K. Thekumparampil, P. Jain, P. Netrapalli and S. Oh
    NeurIPS 2019

  47. SGD for Least Squares Regression: Towards Minimax Optimality with the Final Iterate [*]
    R. Ge, S. M. Kakade, R. Kidambi and P. Netrapalli
    NeurIPS 2019

  48. Making the Last Iterate of SGD Information Theoretically Optimal [*]
    P. Jain, D. Nagaraj and P. Netrapalli
    COLT 2019

  49. SGD without Replacement: Sharper Rates for General Smooth Convex Functions [*]
    P. Jain, D. Nagaraj and P. Netrapalli
    ICML 2019

  50. A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
    C. Jin, P. Netrapalli, R. Ge, S. M. Kakade and M. I. Jordan
    Manuscript

  51. Support Recovery for Orthogonal Matching Pursuit: Upper and Lower Bounds
    R. Somani, C. Gupta, P. Jain and P. Netrapalli
    NeurIPS 2018 (Spotlight)

  52. Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form [*]
    S. Bhojanapalli, N. Boumal, P. Jain and P. Netrapalli
    COLT 2018
    See Nicolas’ and Srinadh's interview about this paper on Dustin Mixon's blog

  53. On the insufficiency of existing momentum schemes for Stochastic Optimization
    R. Kidambi, P. Netrapalli, P. Jain and S. M. Kakade
    ICLR 2018 (Oral)

  54. Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
    C. Jin, P. Netrapalli and M. I. Jordan
    COLT 2018

  55. Accelerating Stochastic Gradient Descent For Least Squares Regression [*]
    P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli and A. Sidford
    COLT 2018

  56. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness [*]
    C. Musco, P. Netrapalli, A. Sidford, S. Ubaru and D. P. Woodruff
    ITCS 2018

  57. A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares) [*]
    P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli, V. K. Pillutla and A. Sidford
    FSTTCS 2017 (Invited)

  58. How to Escape Saddle Points Efficiently
    C. Jin, R. Ge, P. Netrapalli, S. M. Kakade and M. I. Jordan
    ICML 2017

  59. Thresholding based Efficient Outlier Robust PCA [*]
    Y. Cherapanamjeri, P. Jain and P. Netrapalli
    COLT 2017

  60. Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification [*]
    P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli and A. Sidford
    Journal of Machine Learning Research (JMLR) 18(223)

  61. Computing Matrix Squareroot via Non Convex Local Search [*]
    P. Jain, C. Jin, S. M. Kakade and P. Netrapalli
    AISTATS 2017

  62. Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
    C. Jin, S. M. Kakade and P. Netrapalli
    NIPS 2016

  63. Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm [*]
    P. Jain, C. Jin, S. M. Kakade, P. Netrapalli and A. Sidford
    COLT 2016

  64. Information-theoretic thresholds for community detection in sparse networks [*]
    J. Banks, C. Moore, J. Neeman and P. Netrapalli
    COLT 2016

    This paper was a merge of the following two papers
    Non-Reconstructability in the Stochastic Block Model [*]    J. Neeman and P. Netrapalli
    and
    Information-theoretic thresholds for community detection in sparse networks    J. Banks and C. Moore

  65. Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis [*]
    R. Ge, C. Jin, S. M. Kakade, P. Netrapalli and A. Sidford
    ICML 2016

  66. Faster Eigenvector Computation via Shift-and-Invert Preconditioning [*]
    D. Garber, E. Hazan, C. Jin, S. M. Kakade, C. Musco, P. Netrapalli and A. Sidford
    ICML 2016

    This paper was a merge of the following two papers
    Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation [*]
    C. Jin, S. M. Kakade, C. Musco, P. Netrapalli and A. Sidford
    and
    Fast and Simple PCA via Convex Optimization    D. Garber and E. Hazan

  67. Learning Planar Ising Models
    J. K. Johnson, D. Oyen, M. Chertkov and P. Netrapalli
    Journal of Machine Learning Research (JMLR) 2016, Volume 17, Issue 15

  68. Convergence Rates of Active Learning for Maximum Likelihood Estimation [*]
    K. Chaudhuri, S. M. Kakade, P. Netrapalli and S. Sanghavi
    NIPS 2015

  69. Fast Exact Matrix Completion with Finite Samples [*]
    P. Jain and P. Netrapalli
    COLT 2015

  70. Non-convex Robust PCA
    P. Netrapalli, U. N. Niranjan, S. Sanghavi, A. Anandkumar and P. Jain
    NIPS 2014 (Spotlight)

  71. Learning Structure of Power-Law Markov Networks
    A. K. Das, P. Netrapalli, S. Sanghavi and S. Vishwanath
    ISIT 2014

  72. Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization [*]
    A. Agarwal, A. Anandkumar, P. Jain and P. Netrapalli
    SIAM Journal on Optimization 2016, Vol. 26, Issue 4, Pages 2775–2799

  73. A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries [*]
    A. Agarwal, A. Anandkumar and P. Netrapalli
    IEEE Transactions on Information Theory 2017, Vol. 63, Issue 1, Pages 575–592

    An extended abstract of the above two papers appeared as
    Learning Sparsely Used Overcomplete Dictionaries [*]
    A. Agarwal, A. Anandkumar, P. Jain, P. Netrapalli and R. Tandon
    COLT 2014

    See also this paper by Arora, Ge and Moitra.

  74. Phase Retrieval using Alternating Minimization
    P. Netrapalli, P. Jain and S. Sanghavi
    IEEE Transactions on Signal Processing 2015, Vol. 63, Issue 18, Pages 4814–4826
    An extended abstract appeared in NIPS 2013
    IEEE Signal Processing Society Best Paper Award 2019 (awarded annually to up to six papers published during the previous five years)

  75. One-Bit Compressed Sensing: Provable Support and Vector Recovery
    S. Gopi, P. Netrapalli, P. Jain and A. Nori
    ICML 2013

  76. Low-rank Matrix Completion using Alternating Minimization [*]
    P. Jain, P. Netrapalli and S. Sanghavi
    STOC 2013

  77. Learning Markov Graphs Up To Edit Distance
    A. K. Das, P. Netrapalli, S. Sanghavi and S. Vishwanath
    ISIT 2012

  78. Finding the Graph of Epidemic Cascades
    P. Netrapalli and S. Sanghavi
    SIGMETRICS/Performance 2012

  79. Greedy Learning of Markov Network Structure
    P. Netrapalli, S. Banerjee, S. Sanghavi and S. Shakkottai
    Allerton 2010 (Invited)