Publications

* indicates alphabetical ordering of author names.

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

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

  3. Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
    C. Jin, P. Netrapalli and M. I. Jordan
    Manuscript

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

  5. Accelerating Stochastic Gradient Descent [*]
    P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli and A. Sidford
    Manuscript

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

  7. 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)

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

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

  10. Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging [*]
    P. Jain, S. M. Kakade, R. Kidambi, P. Netrapalli and A. Sidford
    Accepted for publication in JMLR

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

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

  13. 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

  14. 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

  15. 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

  16. 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

  17. 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

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

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

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

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

  22. 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

  23. 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 appears 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.

  24. 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

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

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

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

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

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