Journal Publications

  • Partial Hard Thresholding
    Prateek Jain, Ambuj Tewari and Inderjit S. Dhillon,
    IEEE Trans. Information Theory, vol. 63, no. 5, pp. 3029-3038, 2017.
    [BibTeX] [URL]
    @article{JainTD17,
      author = {Prateek Jain and Ambuj Tewari and Inderjit S. Dhillon},
      title = {Partial Hard Thresholding},
      journal = {IEEE Trans. Information Theory},
      year = {2017},
      volume = {63},
      number = {5},
      pages = {3029--3038},
      url = {https://doi.org/10.1109/TIT.2017.2686880},
      doi = {http://doi.org/10.1109/TIT.2017.2686880}
    }
    
  • Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization
    Alekh Agarwal, Animashree Anandkumar, Prateek Jain and Praneeth Netrapalli,
    SIAM Journal on Optimization, vol. 26, no. 4, pp. 2775-2799, 2016.
    [BibTeX] [URL]
    @article{AgarwalAJN16,
      author = {Alekh Agarwal and Animashree Anandkumar and Prateek Jain and Praneeth Netrapalli},
      title = {Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization},
      journal = {SIAM Journal on Optimization},
      year = {2016},
      volume = {26},
      number = {4},
      pages = {2775--2799},
      url = {https://doi.org/10.1137/140979861},
      doi = {http://doi.org/10.1137/140979861}
    }
    
  • Phase Retrieval Using Alternating Minimization
    Praneeth Netrapalli, Prateek Jain and Sujay Sanghavi,
    IEEE Transactions on Signal Processing (ITSP), vol. 63, no. 18, pp. 4814-4826, 2015.
    [BibTeX] [URL]
    @article{NetrapalliJS15,
      author = {Praneeth Netrapalli and Prateek Jain and Sujay Sanghavi},
      title = {Phase Retrieval Using Alternating Minimization},
      journal = {IEEE Transactions on Signal Processing (ITSP)},
      year = {2015},
      volume = {63},
      number = {18},
      pages = {4814--4826},
      url = {http://dx.doi.org/10.1109/TSP.2015.2448516},
      doi = {http://doi.org/10.1109/TSP.2015.2448516}
    }
    
  • Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning
    Sudheendra Vijayanarasimhan, Prateek Jain and Kristen Grauman,
    IEEE Trans. Pattern Anal. Mach. Intell., vol. 36, no. 2, pp. 276-288, 2014.
    [BibTeX] [URL]
    @article{Vijayanarasimhan0G14,
      author = {Sudheendra Vijayanarasimhan and Prateek Jain and Kristen Grauman},
      title = {Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning},
      journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
      year = {2014},
      volume = {36},
      number = {2},
      pages = {276--288},
      url = {http://doi.ieeecomputersociety.org/10.1109/TPAMI.2013.121},
      doi = {http://doi.org/10.1109/TPAMI.2013.121}
    }
    
  • Improved Multiple Sequence Alignments Using Coupled Pattern Mining
    K. S. M. Tozammel Hossain, Debprakash Patnaik, Srivatsan Laxman, Prateek Jain, Chris Bailey-Kellogg and Naren Ramakrishnan,
    IEEE/ACM Trans. Comput. Biology Bioinform., vol. 10, no. 5, pp. 1098-1112, 2013.
    [BibTeX] [URL]
    @article{HossainPL0BR13,
      author = {K. S. M. Tozammel Hossain and Debprakash Patnaik and Srivatsan Laxman and Prateek Jain and Chris Bailey-Kellogg and Naren Ramakrishnan},
      title = {Improved Multiple Sequence Alignments Using Coupled Pattern Mining},
      journal = {IEEE/ACM Trans. Comput. Biology Bioinform.},
      year = {2013},
      volume = {10},
      number = {5},
      pages = {1098--1112},
      url = {http://dx.doi.org/10.1109/TCBB.2013.36},
      doi = {http://doi.org/10.1109/TCBB.2013.36}
    }
    
  • Metric and Kernel Learning Using a Linear Transformation
    Prateek Jain, Brian Kulis, Jason V. Davis and Inderjit S. Dhillon,
    Journal of Machine Learning Research, vol. 13, pp. 519-547, 2012.
    [BibTeX] [URL]
    @article{JainKDD12,
      author = {Prateek Jain and Brian Kulis and Jason V. Davis and Inderjit S. Dhillon},
      title = {Metric and Kernel Learning Using a Linear Transformation},
      journal = {Journal of Machine Learning Research},
      year = {2012},
      volume = {13},
      pages = {519--547},
      url = {http://dl.acm.org/citation.cfm?id=2188402}
    }
    
  • Fast Similarity Search for Learned Metrics
    Brian Kulis, Prateek Jain and Kristen Grauman,
    IEEE Trans. Pattern Anal. Mach. Intell., vol. 31, no. 12, pp. 2143-2157, 2009.
    [BibTeX] [URL]
    @article{KulisJG09,
      author = {Brian Kulis and Prateek Jain and Kristen Grauman},
      title = {Fast Similarity Search for Learned Metrics},
      journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
      year = {2009},
      volume = {31},
      number = {12},
      pages = {2143--2157},
      url = {http://doi.ieeecomputersociety.org/10.1109/TPAMI.2009.151},
      doi = {http://doi.org/10.1109/TPAMI.2009.151}
    }
    
  • Simultaneous Unsupervised Learning of Disparate Clusterings
    Prateek Jain, Raghu Meka and Inderjit S. Dhillon,
    Statistical Analysis and Data Mining, vol. 1, no. 3, pp. 195-210, 2008.
    [BibTeX] [URL]
    @article{JainMD08b,
      author = {Prateek Jain and Raghu Meka and Inderjit S. Dhillon},
      title = {Simultaneous Unsupervised Learning of Disparate Clusterings},
      journal = {Statistical Analysis and Data Mining},
      year = {2008},
      volume = {1},
      number = {3},
      pages = {195--210},
      url = {http://dx.doi.org/10.1002/sam.10007},
      doi = {http://doi.org/10.1002/sam.10007}
    }
    
  • Conference Publications

  • Programming by Examples: PL meets ML
    Sumit Gulwani and Prateek Jain,
    in Proceedings of the 15th Asian Symposium on Programming Languages and Systems (APLAS), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{GulwaniJ17,
      author = {Sumit Gulwani and Prateek Jain},
      title = {Programming by Examples: PL meets ML},
      booktitle = {Proceedings of the 15th Asian Symposium on Programming Languages and Systems (APLAS)},
      year = {2017},
      url = {all_papers/GulwaniJ17_APLAS.pdf}
    }
    

  • Active Heteroscedastic Regression
    Kamalika Chaudhuri, Prateek Jain and Nagarajan Natarajan,
    in Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{ChaudhuriJN17,
      author = {Kamalika Chaudhuri and Prateek Jain and Nagarajan Natarajan},
      title = {Active Heteroscedastic Regression},
      booktitle = {Proceedings of the 34th International Conference on Machine Learning (ICML)},
      year = {2017},
      pages = {694--702},
      note = {slides/test.pdf},
      url = {http://proceedings.mlr.press/v70/chaudhuri17a.html}
    }
    

  • Nearly Optimal Robust Matrix Completion
    Yeshwanth Cherapanamjeri, Kartik Gupta and Prateek Jain,
    in Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{CherapanamjeriGJ17,
      author = {Yeshwanth Cherapanamjeri and Kartik Gupta and Prateek Jain},
      title = {Nearly Optimal Robust Matrix Completion},
      booktitle = {Proceedings of the 34th International Conference on Machine Learning (ICML)},
      year = {2017},
      pages = {797--805},
      url = {http://proceedings.mlr.press/v70/cherapanamjeri17a.html}
    }
    

  • ProtoNN: Compressed and Accurate kNN for Resource-scarce Devices
    Chirag Gupta, Arun Sai Suggala, Ankit Goyal, Harsha Vardhan Simhadri, Bhargavi Paranjape, Ashish Kumar, Saurabh Goyal, Raghavendra Udupa, Manik Varma and Prateek Jain,
    in Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{GuptaSGSPKGUVJ17,
      author = {Chirag Gupta and Arun Sai Suggala and Ankit Goyal and Harsha Vardhan Simhadri and Bhargavi Paranjape and Ashish Kumar and Saurabh Goyal and Raghavendra Udupa and Manik Varma and Prateek Jain},
      title = {ProtoNN: Compressed and Accurate kNN for Resource-scarce Devices},
      booktitle = {Proceedings of the 34th International Conference on Machine Learning (ICML)},
      year = {2017},
      pages = {1331--1340},
      url = {all_papers/GuptaSGSPKGUVJ17_ICML.pdf}
    }
    

  • Recovery Guarantees for One-hidden-layer Neural Networks
    Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett and Inderjit S. Dhillon,
    in Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{ZhongSJBD17,
      author = {Kai Zhong and Zhao Song and Prateek Jain and Peter L. Bartlett and Inderjit S. Dhillon},
      title = {Recovery Guarantees for One-hidden-layer Neural Networks},
      booktitle = {Proceedings of the 34th International Conference on Machine Learning (ICML)},
      year = {2017},
      pages = {4140--4149},
      note = {slides/ZhongSJBD17.pdf},
      url = {all_papers/ZSJBD17_ICML.pdf}
    }
    

  • Thresholding Based Outlier Robust PCA
    Yeshwanth Cherapanamjeri, Prateek Jain and Praneeth Netrapalli,
    in Proceedings of the 30th Conference on Learning Theory (COLT), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{CherapanamjeriJN17,
      author = {Yeshwanth Cherapanamjeri and Prateek Jain and Praneeth Netrapalli},
      title = {Thresholding Based Outlier Robust PCA},
      booktitle = {Proceedings of the 30th Conference on Learning Theory (COLT)},
      year = {2017},
      pages = {593--628},
      url = {http://proceedings.mlr.press/v65/cherapanamjeri17a.html}
    }
    

  • Fast second-order cone programming for safe mission planning
    Kai Zhong, Prateek Jain and Ashish Kapoor,
    in 2017 IEEE International Conference on Robotics and Automation (ICRA), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{ZhongJK17,
      author = {Kai Zhong and Prateek Jain and Ashish Kapoor},
      title = {Fast second-order cone programming for safe mission planning},
      booktitle = {2017 IEEE International Conference on Robotics and Automation (ICRA)},
      year = {2017},
      pages = {79--86},
      url = {https://doi.org/10.1109/ICRA.2017.7989014},
      doi = {http://doi.org/10.1109/ICRA.2017.7989014}
    }
    

  • Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot
    Prateek Jain, Chi Jin, Sham M. Kakade and Praneeth Netrapalli,
    in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JJKN17,
      author = {Prateek Jain and Chi Jin and Sham M. Kakade and Praneeth Netrapalli},
      title = {Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot},
      booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS)},
      year = {2017},
      pages = {479--488},
      url = {http://proceedings.mlr.press/v54/jain17a.html}
    }
    

  • Scalable Optimization of Multivariate Performance Measures in Multi-instance Multi-label Learning
    Apoorv Aggarwal, Sandip Ghoshal, Ankith M. S. Shetty, Suhit Sinha, Ganesh Ramakrishnan, Purushottam Kar and Prateek Jain,
    in Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI), 2017.
    [BibTeX] [Abstract] [URL]
    @inproceedings{AggarwalGSSRKJ17,
      author = {Apoorv Aggarwal and Sandip Ghoshal and Ankith M. S. Shetty and Suhit Sinha and Ganesh Ramakrishnan and Purushottam Kar and Prateek Jain},
      title = {Scalable Optimization of Multivariate Performance Measures in Multi-instance Multi-label Learning},
      booktitle = {Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI)},
      year = {2017},
      pages = {1698--1704},
      url = {all_papers/AggarwalGSSRKJ17.pdf}
    }
    

  • Structured Sparse Regression via Greedy Hard Thresholding
    Prateek Jain, Nikhil Rao and Inderjit S. Dhillon,
    in Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS), 2016.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JRD16,
      author = {Prateek Jain and Nikhil Rao and Inderjit S. Dhillon},
      title = {Structured Sparse Regression via Greedy Hard Thresholding},
      booktitle = {Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2016},
      pages = {1516--1524},
      url = {http://papers.nips.cc/paper/6425-structured-sparse-regression-via-greedy-hard-thresholding}
    }
    

  • Regret Bounds for Non-decomposable Metrics with Missing Labels
    Nagarajan Natarajan and Prateek Jain,
    in Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS), 2016.
    [BibTeX] [Abstract] [URL]
    @inproceedings{NatarajanJ16,
      author = {Nagarajan Natarajan and Prateek Jain},
      title = {Regret Bounds for Non-decomposable Metrics with Missing Labels},
      booktitle = {Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2016},
      pages = {2874--2882},
      url = {http://papers.nips.cc/paper/6178-regret-bounds-for-non-decomposable-metrics-with-missing-labels}
    }
    

  • Selective inference for group-sparse linear models
    Fan Yang, Rina Foygel Barber, Prateek Jain and John D. Lafferty,
    in Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS), 2016.
    [BibTeX] [Abstract] [URL]
    @inproceedings{YangBJL16,
      author = {Fan Yang and Rina Foygel Barber and Prateek Jain and John D. Lafferty},
      title = {Selective inference for group-sparse linear models},
      booktitle = {Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2016},
      pages = {2469--2477},
      url = {http://papers.nips.cc/paper/6437-selective-inference-for-group-sparse-linear-models}
    }
    

  • Mixed Linear Regression with Multiple Components
    Kai Zhong, Prateek Jain and Inderjit S. Dhillon,
    in Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS), 2016.
    [BibTeX] [Abstract] [URL]
    @inproceedings{ZhongJD16,
      author = {Kai Zhong and Prateek Jain and Inderjit S. Dhillon},
      title = {Mixed Linear Regression with Multiple Components},
      booktitle = {Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2016},
      pages = {2190--2198},
      url = {http://papers.nips.cc/paper/6240-mixed-linear-regression-with-multiple-components}
    }
    

  • Diverse Yet Efficient Retrieval using Locality Sensitive Hashing
    Vidyadhar Rao, Prateek Jain and C. V. Jawahar,
    in Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval (ICMR), 2016.
    [BibTeX] [Abstract] [URL]
    @inproceedings{RaoJJ16,
      author = {Vidyadhar Rao and Prateek Jain and C. V. Jawahar},
      title = {Diverse Yet Efficient Retrieval using Locality Sensitive Hashing},
      booktitle = {Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval (ICMR)},
      year = {2016},
      pages = {189--196},
      url = {http://doi.acm.org/10.1145/2911996.2911998},
      doi = {http://doi.org/10.1145/2911996.2911998}
    }
    

  • Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
    Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli and Aaron Sidford,
    in Proceedings of the 29th Conference on Learning Theory (COLT), 2016.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainJKNS16,
      author = {Prateek Jain and Chi Jin and Sham M. Kakade and Praneeth Netrapalli and Aaron Sidford},
      title = {Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm},
      booktitle = {Proceedings of the 29th Conference on Learning Theory (COLT)},
      year = {2016},
      pages = {1147--1164},
      url = {http://jmlr.org/proceedings/papers/v49/jain16.html}
    }
    

  • Tensor vs. Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
    Anima Anandkumar, Prateek Jain, Yang Shi and U. N. Niranjan,
    in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS), 2016.
    [BibTeX] [Abstract] [URL]
    @inproceedings{AnandkumarJSN16,
      author = {Anima Anandkumar and Prateek Jain and Yang Shi and U. N. Niranjan},
      title = {Tensor vs. Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations},
      booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS)},
      year = {2016},
      pages = {268--276},
      url = {http://jmlr.org/proceedings/papers/v51/anandkumar16.html}
    }
    

  • Efficient Matrix Sensing Using Rank-1 Gaussian Measurements
    Kai Zhong, Prateek Jain and Inderjit S. Dhillon,
    in Algorithmic Learning Theory - 26th International Conference (ALT), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{ZhongJD15,
      author = {Kai Zhong and Prateek Jain and Inderjit S. Dhillon},
      title = {Efficient Matrix Sensing Using Rank-1 Gaussian Measurements},
      booktitle = {Algorithmic Learning Theory - 26th International Conference (ALT)},
      year = {2015},
      pages = {3--18},
      url = {https://doi.org/10.1007/978-3-319-24486-0_1},
      doi = {http://doi.org/10.1007/978-3-319-24486-0_1}
    }
    

  • Robust Regression via Hard Thresholding
    Kush Bhatia, Prateek Jain and Purushottam Kar,
    in Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{BhatiaJK15,
      author = {Kush Bhatia and Prateek Jain and Purushottam Kar},
      title = {Robust Regression via Hard Thresholding},
      booktitle = {Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS)},
      year = {2015},
      url = {all_papers/BJK15_NIPS.pdf}
    }
    

  • Sparse Local Embeddings for Extreme Multi-label Classification
    Kush Bhatia, Himanshu Jain, Purushottam Kar, Manik Varma and Prateek Jain,
    in Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{BhatiaJKVJ15,
      author = {Kush Bhatia and Himanshu Jain and Purushottam Kar and Manik Varma and Prateek Jain},
      title = {Sparse Local Embeddings for Extreme Multi-label Classification},
      booktitle = {Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS)},
      year = {2015},
      url = {all_papers/BJKVJ15_NIPS.pdf}
    }
    

  • Predtron: A Family of Online Algorithms for General Prediction Problems
    Prateek Jain, Nagarajan Natarajan and Ambuj Tewari,
    in Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JNT15,
      author = {Prateek Jain and Nagarajan Natarajan and Ambuj Tewari},
      title = {Predtron: A Family of Online Algorithms for General Prediction Problems},
      booktitle = {Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS)},
      year = {2015},
      url = {all_papers/JNT15_NIPS.pdf}
    }
    

  • Alternating Minimization for Regression Problems with Vector-valued Outputs
    Prateek Jain and Ambuj Tewari,
    in Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JT15,
      author = {Prateek Jain and Ambuj Tewari},
      title = {Alternating Minimization for Regression Problems with Vector-valued Outputs},
      booktitle = {Proceedings of the 28th Annual Conference on Advances in Neural Information Processing Systems (NIPS)},
      year = {2015},
      url = {all_papers/JT15_NIPS.pdf}
    }
    

  • Surrogate Functions for Maximizing Precision at the Top
    Purushottam Kar, Harikrishna Narasimhan and Prateek Jain,
    in Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{KarNJ15,
      author = {Purushottam Kar and Harikrishna Narasimhan and Prateek Jain},
      title = {Surrogate Functions for Maximizing Precision at the Top},
      booktitle = {Proceedings of the 32nd International Conference on Machine Learning (ICML)},
      year = {2015},
      pages = {189--198},
      url = {all_papers/KNJ15_ICML.pdf}
    }
    

  • Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
    Harikrishna Narasimhan, Purushottam Kar and Prateek Jain,
    in Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{NarasimhanKJ15,
      author = {Harikrishna Narasimhan and Purushottam Kar and Prateek Jain},
      title = {Optimizing Non-decomposable Performance Measures: A Tale of Two Classes},
      booktitle = {Proceedings of the 32nd International Conference on Machine Learning (ICML)},
      year = {2015},
      pages = {199--208},
      url = {all_papers/NKJ15_ICML.pdf}
    }
    

  • Fast Exact Matrix Completion with Finite Samples
    Prateek Jain and Praneeth Netrapalli,
    in Proceedings of The 28th Conference on Learning Theory (COLT), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JN15,
      author = {Prateek Jain and Praneeth Netrapalli},
      title = {Fast Exact Matrix Completion with Finite Samples},
      booktitle = {Proceedings of The 28th Conference on Learning Theory (COLT)},
      year = {2015},
      pages = {1007--1034},
      url = {all_papers/JN15_COLT.pdf}
    }
    

  • Tighter Low-rank Approximation via Sampling the Leveraged Element
    Srinadh Bhojanapalli, Prateek Jain and Sujay Sanghavi,
    in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
    [BibTeX] [Abstract] [URL]
    @inproceedings{BhojanapalliJS15,
      author = {Srinadh Bhojanapalli and Prateek Jain and Sujay Sanghavi},
      title = {Tighter Low-rank Approximation via Sampling the Leveraged Element},
      booktitle = {Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year = {2015},
      pages = {902--920},
      url = {all_papers/BJS15_SODA.pdf},
      doi = {http://doi.org/10.1137/1.9781611973730.62}
    }
    

  • Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
    Purushottam Kar, Harikrishna Narasimhan and Prateek Jain,
    in Proceedings of the 27th Annual Conference on Advances in Neural Information Processing Systems (NIPS), 2014.
    [BibTeX] [Abstract] [URL]
    @inproceedings{KarNJ14,
      author = {Purushottam Kar and Harikrishna Narasimhan and Prateek Jain},
      title = {Online and Stochastic Gradient Methods for Non-decomposable Loss Functions},
      booktitle = {Proceedings of the 27th Annual Conference on Advances in Neural Information Processing Systems (NIPS)},
      year = {2014},
      pages = {694--702},
      url = {all_papers/NKJ14_NIPS.pdf}
    }
    

  • Non-convex Robust PCA
    Praneeth Netrapalli, U. N. Niranjan, Sujay Sanghavi, Animashree Anandkumar and Prateek Jain,
    in Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems (NIPS), 2014.
    [BibTeX] [Abstract] [URL]
    @inproceedings{NetrapalliNSAJ14,
      author = {Praneeth Netrapalli and U. N. Niranjan and Sujay Sanghavi and Animashree Anandkumar and Prateek Jain},
      title = {Non-convex Robust PCA},
      booktitle = {Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2014},
      pages = {1107--1115},
      url = {http://papers.nips.cc/paper/5430-non-convex-robust-pca}
    }
    

  • Universal Matrix Completion
    Srinadh Bhojanapalli and Prateek Jain,
    in Proceedings of the 31th International Conference on Machine Learning (ICML), 2014.
    [BibTeX] [Abstract] [URL]
    @inproceedings{BhojanapalliJ14,
      author = {Srinadh Bhojanapalli and Prateek Jain},
      title = {Universal Matrix Completion},
      booktitle = {Proceedings of the 31th International Conference on Machine Learning (ICML)},
      year = {2014},
      pages = {1881--1889},
      url = {all_papers/BJ14_ICML.pdf}
    }
    

  • (Near) Dimension Independent Risk Bounds for Differentially Private Learning
    Prateek Jain and Abhradeep Guha Thakurta,
    in Proceedings of the 31th International Conference on Machine Learning (ICML), 2014.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainT14,
      author = {Prateek Jain and Abhradeep Guha Thakurta},
      title = {(Near) Dimension Independent Risk Bounds for Differentially Private Learning},
      booktitle = {Proceedings of the 31th International Conference on Machine Learning (ICML)},
      year = {2014},
      pages = {476--484},
      url = {all_papers/JT14_ICML.pdf}
    }
    

  • Large-scale Multi-label Learning with Missing Labels
    Hsiang-Fu Yu, Prateek Jain, Purushottam Kar and Inderjit S. Dhillon,
    in Proceedings of the 31th International Conference on Machine Learning (ICML), 2014.
    [BibTeX] [Abstract] [URL]
    @inproceedings{YuJKD14,
      author = {Hsiang-Fu Yu and Prateek Jain and Purushottam Kar and Inderjit S. Dhillon},
      title = {Large-scale Multi-label Learning with Missing Labels},
      booktitle = {Proceedings of the 31th International Conference on Machine Learning (ICML)},
      year = {2014},
      pages = {593--601},
      url = {all_papers/YJKD14_ICML.pdf}
    }
    

  • Learning Sparsely Used Overcomplete Dictionaries
    Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli and Rashish Tandon,
    in Proceedings of The 27th Conference on Learning Theory (COLT), 2014.
    [BibTeX] [Abstract] [URL]
    @inproceedings{AgarwalA0NT14,
      author = {Alekh Agarwal and Animashree Anandkumar and Prateek Jain and Praneeth Netrapalli and Rashish Tandon},
      title = {Learning Sparsely Used Overcomplete Dictionaries},
      booktitle = {Proceedings of The 27th Conference on Learning Theory (COLT)},
      year = {2014},
      pages = {123--137},
      url = {all_papers/AAJNT14_COLT.pdf}
    }
    

  • Learning Mixtures of Discrete Product Distributions using Spectral Decompositions
    Prateek Jain and Sewoong Oh,
    in Proceedings of The 27th Conference on Learning Theory (COLT), 2014.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainO14,
      author = {Prateek Jain and Sewoong Oh},
      title = {Learning Mixtures of Discrete Product Distributions using Spectral Decompositions},
      booktitle = {Proceedings of The 27th Conference on Learning Theory (COLT)},
      year = {2014},
      pages = {824--856},
      url = {all_papers/JO14_COLT.pdf}
    }
    

  • Memory Limited, Streaming PCA
    Ioannis Mitliagkas, Constantine Caramanis and Prateek Jain,
    in Proceedings of the 27th Annual Conference on Neural Information Processing Systems (NIPS), 2013.
    [BibTeX] [Abstract] [URL]
    @inproceedings{MitliagkasC013,
      author = {Ioannis Mitliagkas and Constantine Caramanis and Prateek Jain},
      title = {Memory Limited, Streaming PCA},
      booktitle = {Proceedings of the 27th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2013},
      pages = {2886--2894},
      url = {http://papers.nips.cc/paper/5035-memory-limited-streaming-pca}
    }
    

  • Phase Retrieval using Alternating Minimization
    Praneeth Netrapalli, Prateek Jain and Sujay Sanghavi,
    in Proceedings of the 27th Annual Conference on Neural Information Processing Systems (NIPS), 2013.
    [BibTeX] [Abstract] [URL]
    @inproceedings{NetrapalliJS13,
      author = {Praneeth Netrapalli and Prateek Jain and Sujay Sanghavi},
      title = {Phase Retrieval using Alternating Minimization},
      booktitle = {Proceedings of the 27th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2013},
      pages = {2796--2804},
      url = {all_papers/NJS13_NIPS.pdf}
    }
    

  • One-Bit Compressed Sensing: Provable Support and Vector Recovery
    Sivakant Gopi, Praneeth Netrapalli, Prateek Jain and Aditya V. Nori,
    in Proceedings of the 30th International Conference on Machine Learning (ICML), 2013.
    [BibTeX] [Abstract] [URL]
    @inproceedings{GopiN0N13,
      author = {Sivakant Gopi and Praneeth Netrapalli and Prateek Jain and Aditya V. Nori},
      title = {One-Bit Compressed Sensing: Provable Support and Vector Recovery},
      booktitle = {Proceedings of the 30th International Conference on Machine Learning (ICML)},
      year = {2013},
      pages = {154--162},
      url = {http://jmlr.org/proceedings/papers/v28/gopi13.html}
    }
    

  • Differentially Private Learning with Kernels
    Prateek Jain and Abhradeep Thakurta,
    in Proceedings of the 30th International Conference on Machine Learning (ICML), 2013.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainT13,
      author = {Prateek Jain and Abhradeep Thakurta},
      title = {Differentially Private Learning with Kernels},
      booktitle = {Proceedings of the 30th International Conference on Machine Learning (ICML)},
      year = {2013},
      pages = {118--126},
      url = {all_papers/JT13_ICML.pdf}
    }
    

  • On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions
    Purushottam Kar, Bharath K. Sriperumbudur, Prateek Jain and Harish Karnick,
    in Proceedings of the 30th International Conference on Machine Learning (ICML), 2013.
    [BibTeX] [Abstract] [URL]
    @inproceedings{KarS0K13,
      author = {Purushottam Kar and Bharath K. Sriperumbudur and Prateek Jain and Harish Karnick},
      title = {On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions},
      booktitle = {Proceedings of the 30th International Conference on Machine Learning (ICML)},
      year = {2013},
      pages = {441--449},
      url = {all_papers/SKJK13_ICML.pdf}
    }
    

  • Low-rank matrix completion using alternating minimization
    Prateek Jain, Praneeth Netrapalli and Sujay Sanghavi,
    in Proceedings of the Symposium on Theory of Computing Conference (STOC), 2013.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainNS13,
      author = {Prateek Jain and Praneeth Netrapalli and Sujay Sanghavi},
      title = {Low-rank matrix completion using alternating minimization},
      booktitle = {Proceedings of the Symposium on Theory of Computing Conference (STOC)},
      year = {2013},
      pages = {665--674},
      url = {http://doi.acm.org/10.1145/2488608.2488693},
      doi = {http://doi.org/10.1145/2488608.2488693}
    }
    

  • Ad impression forecasting for sponsored search
    Abhirup Nath, Shibnath Mukherjee, Prateek Jain, Navin Goyal and Srivatsan Laxman,
    in Proceedings of the 22nd International World Wide Web Conference (WWW), 2013.
    [BibTeX] [Abstract] [URL]
    @inproceedings{NathMJGL13,
      author = {Abhirup Nath and Shibnath Mukherjee and Prateek Jain and Navin Goyal and Srivatsan Laxman},
      title = {Ad impression forecasting for sponsored search},
      booktitle = {Proceedings of the 22nd International World Wide Web Conference (WWW)},
      year = {2013},
      pages = {943--952},
      url = {all_papers/NMJGL13_WWW.pdf}
    }
    

  • Multilabel Classification using Bayesian Compressed Sensing
    Ashish Kapoor, Raajay Viswanathan and Prateek Jain,
    in Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS), 2012.
    [BibTeX] [Abstract] [URL]
    @inproceedings{KapoorVJ12,
      author = {Ashish Kapoor and Raajay Viswanathan and Prateek Jain},
      title = {Multilabel Classification using Bayesian Compressed Sensing},
      booktitle = {Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2012},
      pages = {2654--2662},
      url = {http://books.nips.cc/papers/files/nips25/NIPS2012_1243.pdf}
    }
    

  • Supervised Learning with Similarity Functions
    Purushottam Kar and Prateek Jain,
    in Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS), 2012.
    [BibTeX] [Abstract] [URL]
    @inproceedings{KarJ12,
      author = {Purushottam Kar and Prateek Jain},
      title = {Supervised Learning with Similarity Functions},
      booktitle = {Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2012},
      pages = {215--223},
      url = {http://books.nips.cc/papers/files/nips25/NIPS2012_0123.pdf}
    }
    

  • Improved multiple sequence alignments using coupled pattern mining
    K. S. M. Tozammel Hossain, Debprakash Patnaik, Srivatsan Laxman, Prateek Jain, Chris Bailey-Kellogg and Naren Ramakrishnan,
    in Proceedings of the ACM International Conference on Bioinformatics, Computational Biology and Biomedicine (BCB), 2012.
    [BibTeX] [Abstract] [URL]
    @inproceedings{HossainPLJBR12,
      author = {K. S. M. Tozammel Hossain and Debprakash Patnaik and Srivatsan Laxman and Prateek Jain and Chris Bailey-Kellogg and Naren Ramakrishnan},
      title = {Improved multiple sequence alignments using coupled pattern mining},
      booktitle = {Proceedings of the ACM International Conference on Bioinformatics, Computational Biology and Biomedicine (BCB)},
      year = {2012},
      pages = {28--35},
      url = {http://doi.acm.org/10.1145/2382936.2382940},
      doi = {http://doi.org/10.1145/2382936.2382940}
    }
    

  • Mirror Descent Based Database Privacy
    Prateek Jain and Abhradeep Thakurta,
    in Proceedings of the 16th International Workshop (RANDOM), 2012.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainT12,
      author = {Prateek Jain and Abhradeep Thakurta},
      title = {Mirror Descent Based Database Privacy},
      booktitle = {Proceedings of the 16th International Workshop (RANDOM)},
      year = {2012},
      pages = {579--590},
      url = {http://dx.doi.org/10.1007/978-3-642-32512-0_49},
      doi = {http://doi.org/10.1007/978-3-642-32512-0_49}
    }
    

  • Differentially Private Online Learning
    Prateek Jain, Pravesh Kothari and Abhradeep Thakurta,
    in Proceedings of the 25th Annual Conference on Learning Theory (COLT), 2012.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainKT12,
      author = {Prateek Jain and Pravesh Kothari and Abhradeep Thakurta},
      title = {Differentially Private Online Learning},
      booktitle = {Proceedings of the 25th Annual Conference on Learning Theory (COLT)},
      year = {2012},
      pages = {24.1--24.34},
      url = {http://www.jmlr.org/proceedings/papers/v23/jain12/jain12.pdf}
    }
    

  • Orthogonal Matching Pursuit with Replacement
    Prateek Jain, Ambuj Tewari and Inderjit S. Dhillon,
    in Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS), 2011.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainTD11,
      author = {Prateek Jain and Ambuj Tewari and Inderjit S. Dhillon},
      title = {Orthogonal Matching Pursuit with Replacement},
      booktitle = {Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2011},
      pages = {1215--1223},
      url = {http://books.nips.cc/papers/files/nips24/NIPS2011_0707.pdf}
    }
    

  • Similarity-based Learning via Data Driven Embeddings
    Purushottam Kar and Prateek Jain,
    in Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS), 2011.
    [BibTeX] [Abstract] [URL]
    @inproceedings{KarJ11,
      author = {Purushottam Kar and Prateek Jain},
      title = {Similarity-based Learning via Data Driven Embeddings},
      booktitle = {Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2011},
      pages = {1998--2006},
      url = {http://books.nips.cc/papers/files/nips24/NIPS2011_1129.pdf}
    }
    

  • Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning
    Prateek Jain, Sudheendra Vijayanarasimhan and Kristen Grauman,
    in Proceedings of the 24th Annual Conference on Neural Information Processing Systems 2010 (NIPS), 2010.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainVG10,
      author = {Prateek Jain and Sudheendra Vijayanarasimhan and Kristen Grauman},
      title = {Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning},
      booktitle = {Proceedings of the 24th Annual Conference on Neural Information Processing Systems 2010 (NIPS)},
      year = {2010},
      pages = {928--936},
      url = {http://books.nips.cc/papers/files/nips23/NIPS2010_0757.pdf}
    }
    

  • Inductive Regularized Learning of Kernel Functions
    Prateek Jain, Brian Kulis and Inderjit S. Dhillon,
    in Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS), 2010.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainKD10,
      author = {Prateek Jain and Brian Kulis and Inderjit S. Dhillon},
      title = {Inductive Regularized Learning of Kernel Functions},
      booktitle = {Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2010},
      pages = {946--954},
      url = {http://books.nips.cc/papers/files/nips23/NIPS2010_0603.pdf}
    }
    

  • Guaranteed Rank Minimization via Singular Value Projection
    Prateek Jain, Raghu Meka and Inderjit S. Dhillon,
    in Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS), 2010.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainMD10,
      author = {Prateek Jain and Raghu Meka and Inderjit S. Dhillon},
      title = {Guaranteed Rank Minimization via Singular Value Projection},
      booktitle = {Proceedings of the 24th Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2010},
      pages = {937--945},
      url = {http://books.nips.cc/papers/files/nips23/NIPS2010_0682.pdf}
    }
    

  • Far-sighted active learning on a budget for image and video recognition
    Sudheendra Vijayanarasimhan, Prateek Jain and Kristen Grauman,
    in Proceedings of the Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010.
    [BibTeX] [Abstract] [URL]
    @inproceedings{VijayanarasimhanJG10,
      author = {Sudheendra Vijayanarasimhan and Prateek Jain and Kristen Grauman},
      title = {Far-sighted active learning on a budget for image and video recognition},
      booktitle = {Proceedings of the Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
      year = {2010},
      pages = {3035--3042},
      url = {http://dx.doi.org/10.1109/CVPR.2010.5540055},
      doi = {http://doi.org/10.1109/CVPR.2010.5540055}
    }
    

  • Matrix Completion from Power-Law Distributed Samples
    Raghu Meka, Prateek Jain and Inderjit S. Dhillon,
    in Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS), 2009.
    [BibTeX] [Abstract] [URL]
    @inproceedings{MekaJD09,
      author = {Raghu Meka and Prateek Jain and Inderjit S. Dhillon},
      title = {Matrix Completion from Power-Law Distributed Samples},
      booktitle = {Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2009},
      pages = {1258--1266},
      url = {http://books.nips.cc/papers/files/nips22/NIPS2009_0864.pdf}
    }
    

  • Geometry-aware metric learning
    Zhengdong Lu, Prateek Jain and Inderjit S. Dhillon,
    in Proceedings of the 26th Annual International Conference on Machine Learning (ICML), 2009.
    [BibTeX] [Abstract] [URL]
    @inproceedings{LuJD09,
      author = {Zhengdong Lu and Prateek Jain and Inderjit S. Dhillon},
      title = {Geometry-aware metric learning},
      booktitle = {Proceedings of the 26th Annual International Conference on Machine Learning (ICML)},
      year = {2009},
      pages = {673--680},
      url = {http://doi.acm.org/10.1145/1553374.1553461},
      doi = {http://doi.org/10.1145/1553374.1553461}
    }
    

  • Active learning for large multi-class problems
    Prateek Jain and Ashish Kapoor,
    in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainK09,
      author = {Prateek Jain and Ashish Kapoor},
      title = {Active learning for large multi-class problems},
      booktitle = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)},
      year = {2009},
      pages = {762--769},
      url = {http://dx.doi.org/10.1109/CVPRW.2009.5206651},
      doi = {http://doi.org/10.1109/CVPRW.2009.5206651}
    }
    

  • Online Metric Learning and Fast Similarity Search
    Prateek Jain, Brian Kulis, Inderjit S. Dhillon and Kristen Grauman,
    in Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS), 2008.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainKDG08,
      author = {Prateek Jain and Brian Kulis and Inderjit S. Dhillon and Kristen Grauman},
      title = {Online Metric Learning and Fast Similarity Search},
      booktitle = {Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems (NIPS)},
      year = {2008},
      pages = {761--768},
      url = {http://books.nips.cc/papers/files/nips21/NIPS2008_1003.pdf}
    }
    

  • Rank minimization via online learning
    Raghu Meka, Prateek Jain, Constantine Caramanis and Inderjit S. Dhillon,
    in Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML), 2008.
    [BibTeX] [Abstract] [URL]
    @inproceedings{MekaJCD08,
      author = {Raghu Meka and Prateek Jain and Constantine Caramanis and Inderjit S. Dhillon},
      title = {Rank minimization via online learning},
      booktitle = {Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML)},
      year = {2008},
      pages = {656--663},
      url = {http://doi.acm.org/10.1145/1390156.1390239},
      doi = {http://doi.org/10.1145/1390156.1390239}
    }
    

  • Fast image search for learned metrics
    Prateek Jain, Brian Kulis and Kristen Grauman,
    in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2008.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainKG08,
      author = {Prateek Jain and Brian Kulis and Kristen Grauman},
      title = {Fast image search for learned metrics},
      booktitle = {Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)},
      year = {2008},
      url = {http://dx.doi.org/10.1109/CVPR.2008.4587841},
      doi = {http://doi.org/10.1109/CVPR.2008.4587841}
    }
    

  • Simultaneous Unsupervised Learning of Disparate Clusterings
    Prateek Jain, Raghu Meka and Inderjit S. Dhillon,
    in Proceedings of the SIAM International Conference on Data Mining (SDM), 2008.
    [BibTeX] [Abstract] [URL]
    @inproceedings{JainMD08,
      author = {Prateek Jain and Raghu Meka and Inderjit S. Dhillon},
      title = {Simultaneous Unsupervised Learning of Disparate Clusterings},
      booktitle = {Proceedings of the SIAM International Conference on Data Mining (SDM)},
      year = {2008},
      pages = {858--869},
      url = {http://dx.doi.org/10.1137/1.9781611972788.77},
      doi = {http://doi.org/10.1137/1.9781611972788.77}
    }
    

  • Information-theoretic metric learning
    Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra and Inderjit S. Dhillon,
    in Proceedings of the Twenty-Fourth International Conference on Machine Learning (ICML), 2007.
    [BibTeX] [Abstract] [URL]
    @inproceedings{DavisKJSD07,
      author = {Jason V. Davis and Brian Kulis and Prateek Jain and Suvrit Sra and Inderjit S. Dhillon},
      title = {Information-theoretic metric learning},
      booktitle = {Proceedings of the Twenty-Fourth International Conference on Machine Learning (ICML)},
      year = {2007},
      pages = {209--216},
      url = {http://doi.acm.org/10.1145/1273496.1273523},
      doi = {http://doi.org/10.1145/1273496.1273523}
    }