Monographs
Non-convex Optimization for Machine Learning
Prateek Jain and Purushottam Kar,
Foundations and Trends® in Machine Learning,
vol. 10,
December
2017.
[BibTeX]
[URL]
@article{JainK17,
author = {Prateek Jain and Purushottam Kar},
title = {Non-convex Optimization for Machine Learning},
journal = {Foundations and Trends® in Machine Learning},
year = {2017},
volume = {10},
url = {all_papers/JainK17_FTML.pdf}
}
Journal Publications / Preprints
Gecko: Versatile text embeddings distilled from large language models
Jinhyuk Lee, Zhuyun Dai, Xiaoqi Ren, Blair Chen, Daniel Cer, Jeremy R. Cole, Kai Hui, Michael Boratko, Rajvi Kapadia, Wen Ding, Yi Luan, Sai Meher Karthik Duddu, Gustavo Hernandez Abrego, Weiqiang Shi, Nithi Gupta, Aditya Kusupati, Prateek Jain, Siddhartha Reddy Jonnalagadda, Ming-Wei Chang and Iftekhar Naim,
arXiv preprint arXiv:2403.20327,
March
2024.
[BibTeX]
[URL]
@article{LeeDRCCCHBKDLDASGKJJCN24,
author = {Jinhyuk Lee, Zhuyun Dai, Xiaoqi Ren, Blair Chen, Daniel Cer, Jeremy R Cole, Kai Hui, Michael Boratko, Rajvi Kapadia, Wen Ding, Yi Luan, Sai Meher Karthik Duddu, Gustavo Hernandez Abrego, Weiqiang Shi, Nithi Gupta, Aditya Kusupati, Prateek Jain, Siddhartha Reddy Jonnalagadda, Ming-Wei Chang, Iftekhar Naim},
title = {Gecko: Versatile text embeddings distilled from large language models},
journal = {arXiv preprint arXiv:2403.20327},
year = {2024},
url = {all_papers/LeeDRCCCHBKDLDASGKJJCN24.pdf}
}
HiRE: High Recall Approximate Top- Estimation for Efficient LLM Inference
Varun Yerram, Chong You, Srinadh Bhojanapalli, Sanjiv Kumar, Prateek Jain and Praneeth Netrapalli,
arXiv preprint arXiv:2402.09360,
February
2024.
[BibTeX]
[URL]
@article{YerramYBKJN24,
author = {Varun Yerram, Chong You, Srinadh Bhojanapalli, Sanjiv Kumar, Prateek Jain, Praneeth Netrapalli},
title = {HiRE: High Recall Approximate Top- Estimation for Efficient LLM Inference},
journal = {arXiv preprint arXiv:2402.09360},
year = {2024},
url = {all_papers/YerramYBKJN24.pdf}
}
Tandem Transformers for Inference Efficient LLMs
Pranav Ajit Nair, Yashas Samaga, Toby Boyd, Sanjiv Kumar, Prateek Jain and Praneeth Netrapalli,
arXiv preprint arXiv:2402.08644,
February
2024.
[BibTeX]
[URL]
@article{NairSBKJN24,
author = {Pranav Ajit Nair, Yashas Samaga, Toby Boyd, Sanjiv Kumar, Prateek Jain, Praneeth Netrapalli},
title = {Tandem Transformers for Inference Efficient LLMs},
journal = {arXiv preprint arXiv:2402.08644},
year = {2024},
url = {all_papers/NairSBKJN24.pdf}
}
Llm augmented llms: Expanding capabilities through composition
Rachit Bansal, Bidisha Samanta, Siddharth Dalmia, Nitish Gupta, Shikhar Vashishth, Sriram Ganapathy, Abhishek Bapna, Prateek Jain and Partha Talukdar,
arXiv preprint arXiv:2401.02412,
January
2024.
[BibTeX]
[URL]
@article{BansalSDGVGBJT24,
author = {Rachit Bansal, Bidisha Samanta, Siddharth Dalmia, Nitish Gupta, Shikhar Vashishth, Sriram Ganapathy, Abhishek Bapna, Prateek Jain, Partha Talukdar},
title = {Llm augmented llms: Expanding capabilities through composition},
journal = {arXiv preprint arXiv:2401.02412},
year = {2024},
url = {all_papers/BansalSDGVGBJT24.pdf}
}
Efficacy of dual-encoders for extreme multi-label classification
Nilesh Gupta, Devvrit Khatri, Ankit S. Rawat, Srinadh Bhojanapalli, Prateek Jain and Inderjit S. Dhillon,
arXiv preprint arXiv:2310.10636,
October
2023.
[BibTeX]
[URL]
@article{GuptaKRBJD23,
author = {Nilesh Gupta, Devvrit Khatri, Ankit S Rawat, Srinadh Bhojanapalli, Prateek Jain, Inderjit S Dhillon},
title = {Efficacy of dual-encoders for extreme multi-label classification},
journal = {arXiv preprint arXiv:2310.10636},
year = {2023},
url = {all_papers/GuptaKRBJD23.pdf}
}
EHI: End-to-end Learning of Hierarchical Index for Efficient Dense Retrieval
Ramnath Kumar, Anshul Mittal, Nilesh Gupta, Aditya Kusupati, Inderjit Dhillon and Prateek Jain,
arXiv preprint arXiv:2310.08891,
October
2023.
[BibTeX]
[URL]
@article{KumarMGKDJ23,
author = {Ramnath Kumar, Anshul Mittal, Nilesh Gupta, Aditya Kusupati, Inderjit Dhillon, Prateek Jain},
title = {EHI: End-to-end Learning of Hierarchical Index for Efficient Dense Retrieval},
journal = {arXiv preprint arXiv:2310.08891},
year = {2023},
url = {all_papers/KumarMGKDJ23.pdf}
}
MatFormer: Nested Transformer for Elastic Inference
Sneha Kudugunta, Aditya Kusupati, Tim Dettmers, Kaifeng Chen, Inderjit Dhillon, Yulia Tsvetkov, Hannaneh Hajishirzi, Sham Kakade, Ali Farhadi and Prateek Jain,
arXiv preprint arXiv:2310.07707,
October
2023.
[BibTeX]
[URL]
@article{KuduguntaKDCDTHKFJ23,
author = {Sneha Kudugunta, Aditya Kusupati, Tim Dettmers, Kaifeng Chen, Inderjit Dhillon, Yulia Tsvetkov, Hannaneh Hajishirzi, Sham Kakade, Ali Farhadi, Prateek Jain},
title = {MatFormer: Nested Transformer for Elastic Inference},
journal = {arXiv preprint arXiv:2310.07707},
year = {2023},
url = {all_papers/KuduguntaKDCDTHKFJ23.pdf}
}
End-to-End Neural Network Compression via Regularized Latency Surrogates
Anshul Nasery, Hardik Shah, Arun Sai Suggala and Prateek Jain,
arXiv preprint arXiv:2306.05785,
June
2023.
[BibTeX]
[URL]
@article{NaserySSJ23,
author = {Anshul Nasery, Hardik Shah, Arun Sai Suggala, Prateek Jain},
title = {End-to-End Neural Network Compression via Regularized Latency Surrogates},
journal = {arXiv preprint arXiv:2306.05785},
year = {2023},
url = {all_papers/NaserySSJ23.pdf}
}
Near optimal private and robust linear regression
Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh and Arun Sai Suggala,
arXiv preprint arXiv:2301.13273,
January
2023.
[BibTeX]
[URL]
@article{LiuJKOS23,
author = {Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, Arun Sai Suggala},
title = {Near optimal private and robust linear regression},
journal = {arXiv preprint arXiv:2301.13273},
year = {2023},
url = {all_papers/LiuJKOS23.pdf}
}
DAFT: Distilling Adversarially Fine-tuned Models for Better OOD Generalization
Anshul Nasery, Sravanti Addepalli, Praneeth Netrapalli and Prateek Jain,
arXiv preprint arXiv:2208.09139,
August
2022.
[BibTeX]
[URL]
@article{NaseryANJ22,
author = {Anshul Nasery, Sravanti Addepalli, Praneeth Netrapalli, Prateek Jain},
title = {DAFT: Distilling Adversarially Fine-tuned Models for Better OOD Generalization},
journal = {arXiv preprint arXiv:2208.09139},
year = {2022},
url = {all_papers/NaseryANJ22.pdf}
}
Met: Masked encoding for tabular data
Kushal Majmundar, Sachin Goyal, Praneeth Netrapalli and Prateek Jain,
arXiv preprint arXiv:2206.08564,
June
2022.
[BibTeX]
[URL]
@article{MajmundarGNJ22,
author = {Kushal Majmundar, Sachin Goyal, Praneeth Netrapalli, Prateek Jain},
title = {Met: Masked encoding for tabular data},
journal = {arXiv preprint arXiv:2206.08564},
year = {2022},
url = {all_papers/MajmundarGNJ22.pdf}
}
Multivariate Time Series Forecasting
S. Suhas, Arun Suggala, Prateek Jain and Praneeth Nethrapalli,
May
2022.
[BibTeX]
[URL]
@article{SuhasSJN22,
author = {S Suhas, Arun Suggala, Prateek Jain, Praneeth Nethrapalli},
title = {Multivariate Time Series Forecasting},
year = {2022},
url = {all_papers/SuhasSJN22.pdf}
}
Matryoshka representations for adaptive deployment
Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ramanujan, William Howard-Snyder, Kaifeng Chen, Sham Kakade, Prateek Jain and Ali Farhadi,
arXiv preprint arXiv:2205.13147,
May
2022.
[BibTeX]
[URL]
@article{KusupatiBRWSRHCKJF22,
author = {Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ramanujan, William Howard-Snyder, Kaifeng Chen, Sham Kakade, Prateek Jain, Ali Farhadi},
title = {Matryoshka representations for adaptive deployment},
journal = {arXiv preprint arXiv:2205.13147},
year = {2022},
url = {all_papers/KusupatiBRWSRHCKJF22.pdf}
}
Learning accurate decision trees with bandit feedback via quantized gradient descent
Ajaykrishna Karthikeyan, Naman Jain, Nagarajan Natarajan and Prateek Jain,
Transactions of Machine Learning Research (TMLR),
February
2022.
[BibTeX]
[URL]
@article{KarthikeyanJNJ21,
author = {Ajaykrishna Karthikeyan, Naman Jain, Nagarajan Natarajan, Prateek Jain},
title = {Learning accurate decision trees with bandit feedback via quantized gradient descent},
journal = {Transactions of Machine Learning Research (TMLR)},
year = {2022},
url = {all_papers/KarthikeyanJNJ21.pdf}
}
Node-level differentially private graph neural networks
Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal and Prateek Jain,
arXiv preprint arXiv:2111.15521,
November
2021.
[BibTeX]
[URL]
@article{DaigavaneMSTAJ21,
author = {Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, Prateek Jain},
title = {Node-level differentially private graph neural networks},
journal = {arXiv preprint arXiv:2111.15521},
year = {2021},
url = {all_papers/DaigavaneMSTAJ21.pdf}
}
Optimal nonsmooth Frank-Wolfe method for stochastic regret minimization
Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli and Sewoong Oh,
12th OPT Workshop on Optimization for Machine Learning (OPT2020),
December
2020.
[BibTeX]
[URL]
@article{ThekumparampilJNO20,
author = {Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh},
title = {Optimal nonsmooth Frank-Wolfe method for stochastic regret minimization},
journal = {12th OPT Workshop on Optimization for Machine Learning (OPT2020)},
year = {2020},
url = {all_papers/ThekumparampilJNO20.pdf}
}
Nonconvex Optimization for Signal Processing and Machine Learning [From the Guest Editors]
Anthony Man-Cho So, Prateek Jain, Wing-Kin Ma and Gesualdo Scutari,
IEEE Signal Processing Magazine,
pp. 15-17,
September
2020.
[BibTeX]
[URL]
@article{SoJMS20,
author = {Anthony Man-Cho So, Prateek Jain, Wing-Kin Ma, Gesualdo Scutari},
title = {Nonconvex Optimization for Signal Processing and Machine Learning [From the Guest Editors]},
journal = {IEEE Signal Processing Magazine},
year = {2020},
pages = {15-17},
url = {all_papers/SoJMS20.pdf}
}
Programming by rewards
Nagarajan Natarajan, Ajaykrishna Karthikeyan, Prateek Jain, Ivan Radicek, Sriram Rajamani, Sumit Gulwani and Johannes Gehrke,
arXiv preprint arXiv:2007.06835,
July
2020.
[BibTeX]
[URL]
@article{NatarajanKJRRGG20,
author = {Nagarajan Natarajan, Ajaykrishna Karthikeyan, Prateek Jain, Ivan Radicek, Sriram Rajamani, Sumit Gulwani, Johannes Gehrke},
title = {Programming by rewards},
journal = {arXiv preprint arXiv:2007.06835},
year = {2020},
url = {all_papers/NatarajanKJRRGG20.pdf}
}
Globally-convergent iteratively reweighted least squares for robust regression problems
Bhaskar Mukhoty, Govind Gopakumar, Prateek Jain and Purushottam Kar,
arXiv preprint arXiv:2006.14211,
June
2020.
[BibTeX]
[URL]
@article{MukhotyGJK20,
author = {Bhaskar Mukhoty, Govind Gopakumar, Prateek Jain, Purushottam Kar},
title = {Globally-convergent iteratively reweighted least squares for robust regression problems},
journal = {arXiv preprint arXiv:2006.14211},
year = {2020},
url = {all_papers/MukhotyGJK20.pdf}
}
COVID-19: strategies for allocation of test kits
Arpita Biswas, Shruthi Bannur, Prateek Jain and Srujana Merugu,
arXiv preprint arXiv:2004.01740,
April
2020.
[BibTeX]
[URL]
@article{BiswasBJM20,
author = {Arpita Biswas, Shruthi Bannur, Prateek Jain, Srujana Merugu},
title = {COVID-19: strategies for allocation of test kits},
journal = {arXiv preprint arXiv:2004.01740},
year = {2020},
url = {all_papers/BiswasBJM20.pdf}
}
Rich-Item Recommendations for Rich-Users: Exploiting Dynamic and Static Side Information
Amar Budhiraja, Gaurush Hiranandani, Darshak Chhatbar, Aditya Sinha, Navya Yarrabelly, Ayush Choure, Oluwasanmi Koyejo and Prateek Jain,
arXiv preprint arXiv:2001.10495,
January
2020.
[BibTeX]
[URL]
@article{BudhirajaHCSYCKJ20,
author = {Amar Budhiraja, Gaurush Hiranandani, Darshak Chhatbar, Aditya Sinha, Navya Yarrabelly, Ayush Choure, Oluwasanmi Koyejo, Prateek Jain},
title = {Rich-Item Recommendations for Rich-Users: Exploiting Dynamic and Static Side Information},
journal = {arXiv preprint arXiv:2001.10495},
year = {2020},
url = {all_papers/BudhirajaHCSYCKJ20.pdf}
}
On Scaling Data-Driven Loop Invariant Inference
Sahil Bhatia, Saswat Padhi, Nagarajan Natarajan, Rahul Sharma and Prateek Jain,
arXiv preprint arXiv:1911.11728,
November
2019.
[BibTeX]
[URL]
@article{BhatiaPNSJ19,
author = {Sahil Bhatia, Saswat Padhi, Nagarajan Natarajan, Rahul Sharma, Prateek Jain},
title = {On Scaling Data-Driven Loop Invariant Inference},
journal = {arXiv preprint arXiv:1911.11728},
year = {2019},
url = {all_papers/BhatiaPNSJ19.pdf}
}
Learning functions over sets via permutation adversarial networks
Prateek Jain Chirag Pabbaraju,
arXiv preprint arXiv:1907.05638,
July
2019.
[BibTeX]
[URL]
@article{PabbarajuJ19,
author = {Chirag Pabbaraju, Prateek Jain},
title = {Learning functions over sets via permutation adversarial networks},
journal = {arXiv preprint arXiv:1907.05638},
year = {2019},
url = {all_papers/PabbarajuJ19.pdf}
}
Gradient Methods for Non-convex Optimization
Prateek Jain,
pp. 247-256,
June
2019.
[BibTeX]
[URL]
@article{Jain19,
author = {Prateek Jain},
title = {Gradient Methods for Non-convex Optimization},
year = {2019},
pages = {247-256},
url = {all_papers/Jain19.pdf}
}
Universality Patterns in the Training of Neural Networks
Raghav Somani, Navin Goyal, Prateek Jain and Praneeth Netrapalli,
May
2019.
[BibTeX]
[URL]
@article{SomaniGJN19,
author = {Raghav Somani, Navin Goyal, Prateek Jain, Praneeth Netrapalli},
title = {Universality Patterns in the Training of Neural Networks},
year = {2019},
url = {all_papers/SomaniGJN19.pdf}
}
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli and Aaron Sidford,
Journal of Machine Learning Research,
vol. 18,
pp. 223:1-223:42,
2017.
[BibTeX]
[URL]
@article{JainKKNS17,
author = {Prateek Jain and Sham M. Kakade and Rahul Kidambi and Praneeth Netrapalli and Aaron Sidford},
title = {Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification},
journal = {Journal of Machine Learning Research},
year = {2017},
volume = {18},
pages = {223:1--223:42},
url = {all_papers/JainKKNS17.pdf}
}
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 = {https://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 = {https://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 = {https://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 = {https://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 = {https://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 = {https://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 = {https://doi.org/10.1002/sam.10007}
}
Conference Publications
Sample-Efficient Personalization: Modeling User Parameters as Low Rank Plus Sparse Components
Soumyabrata Pal, Prateek Varshney, Gagan Madan, Prateek Jain, Abhradeep Thakurta, Gaurav Aggarwal, Pradeep Shenoy and Gaurav Srivastava,
in International Conference on Artificial Intelligence and Statistics,
2024.
[BibTeX]
[Abstract]
[URL]
Personalization of machine learning (ML) predictions for individual users/domains/enterprises is critical for practical recommendation systems. Standard personalization approaches involve learning a user/domain specific\emph {embedding} that is fed into a fixed global model which can be limiting. On the other hand, personalizing/fine-tuning model itself for each user/domain—aka meta-learning—has high storage/infrastructure cost. Moreover, rigorous theoretical studies of scalable personalization approaches have been very limited. To address the above issues, we propose a novel meta-learning style approach that models network weights as a sum of low-rank and sparse components. This captures common information from multiple individuals/users together in the low-rank part while sparse part captures user-specific idiosyncrasies. We then study the framework in the linear setting, where the problem reduces to that of estimating the sum of a rank- and a -column sparse matrix using a small number of linear measurements. We propose a computationally efficient alternating minimization method with iterative hard thresholding—AMHT-LRS—to learn the low-rank and sparse part. Theoretically, for the realizable Gaussian data setting, we show that AMHT-LRS solves the problem efficiently with nearly optimal sample complexity. Finally, a significant challenge in personalization is ensuring privacy of each user’s sensitive data. We alleviate this problem by proposing a differentially private variant of our method that also is equipped with strong generalization guarantees.
@inproceedings{PalVMJTASS24,
author = {Soumyabrata Pal, Prateek Varshney, Gagan Madan, Prateek Jain, Abhradeep Thakurta, Gaurav Aggarwal, Pradeep Shenoy, Gaurav Srivastava},
title = {Sample-Efficient Personalization: Modeling User Parameters as Low Rank Plus Sparse Components},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2024},
pages = {1702-1710},
url = {all_papers/PalVMJTASS24.pdf}
}
Label Robust and Differentially Private Linear Regression: Computational and Statistical Efficiency
Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh and Arun Suggala,
in Advances in Neural Information Processing Systems (NeurIPS),
2024.
[BibTeX]
[Abstract]
[URL]
We study the canonical problem of linear regression under -differential privacy when the datapoints are sampled iid~ from a distribution and a fraction of response variables are adversarially corrupted. We provide the first provably efficient--both computationally and statistically--method for this problem, assuming standard assumptions on the data distribution. Our algorithm is a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two key innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. Our method requires only linear time in input size, and still matches the information theoretical optimal sample complexity up to a data distribution dependent condition number factor. Interestingly, the same algorithm, when applied to a setting where there is no adversarial corruption, still improves upon the existing state-of-the-art and achieves a near optimal sample complexity.
@inproceedings{LiuJKOS24,
author = {Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, Arun Suggala},
title = {Label Robust and Differentially Private Linear Regression: Computational and Statistical Efficiency},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2024},
url = {all_papers/LiuJKOS24.pdf}
}
Simplicity bias in 1-hidden layer neural networks
Depen Morwani, Jatin Batra, Prateek Jain and Praneeth Netrapalli,
in Advances in Neural Information Processing Systems (NeurIPS),
2024.
[BibTeX]
[Abstract]
[URL]
Recent works have demonstrated that neural networks exhibit extreme* simplicity bias*(SB). That is, they learn* only the simplest* features to solve a task at hand, even in the presence of other, more robust but more complex features. Due to the lack of a general and rigorous definition of* features*, these works showcase SB on* semi-synthetic* datasets such as Color-MNIST, MNIST-CIFAR where defining features is relatively easier. In this work, we rigorously define as well as thoroughly establish SB for* one hidden layer* neural networks in the infinite width regime. More concretely,(i) we define SB as the network essentially being a function of a low dimensional projection of the inputs (ii) theoretically, we show that when the data is linearly separable, the network primarily depends on only the linearly separable (-dimensional) subspace even in the presence of an arbitrarily large number of other, more complex features which could have led to a significantly more robust classifier,(iii) empirically, we show that models trained on* real* datasets such as Imagenet and Waterbirds-Landbirds indeed depend on a low dimensional projection of the inputs, thereby demonstrating SB on these datasets, iv) finally, we present a natural ensemble approach that encourages diversity in models by training successive models on features not used by earlier models, and demonstrate that it yields models that are significantly more robust to Gaussian noise.
@inproceedings{MorwaniBJN24,
author = {Depen Morwani, Jatin Batra, Prateek Jain, Praneeth Netrapalli},
title = {Simplicity bias in 1-hidden layer neural networks},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2024},
url = {all_papers/MorwaniBJN24.pdf}
}
Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints
Soumyabrata Pal, Arun Suggala, Karthikeyan Shanmugam and Prateek Jain,
in Advances in Neural Information Processing Systems (NeurIPS),
2024.
[BibTeX]
[Abstract]
[URL]
We consider the problem of\emph {blocked} collaborative bandits where there are multiple users, each with an associated multi-armed bandit problem. These users are grouped into\emph {latent} clusters such that the mean reward vectors of users within the same cluster are identical. Our goal is to design algorithms that maximize the cumulative reward accrued by all the users over time, under the\emph {constraint} that no arm of a user is pulled more than times. This problem has been originally considered by\cite {Bresler: 2014}, and designing regret-optimal algorithms for it has since remained an open problem. In this work, we propose an algorithm called B-LATTICE (Blocked Latent bAndiTs via maTrIx ComplEtion) that collaborates across users, while simultaneously satisfying the budget constraints, to maximize their cumulative rewards. Theoretically, under certain reasonable assumptions on the latent structure, with users, arms, rounds per user, and latent clusters, B-LATTICE achieves a per-user regret of under a budget constraint of . These are the first sub-linear regret bounds for this problem, and match the minimax regret bounds when . Empirically, we demonstrate that our algorithm has superior performance over baselines even when . B-LATTICE is a phased algorithm where in each phase it clusters users into groups and collaborates across users within a group to quickly learn their reward models.
@inproceedings{PalSSJ24,
author = {Soumyabrata Pal, Arun Suggala, Karthikeyan Shanmugam, Prateek Jain},
title = {Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2024},
url = {all_papers/PalSSJ24.pdf}
}
Adanns: A framework for adaptive semantic search
Aniket Rege, Aditya Kusupati, Alan Fan, Qingqing Cao, Sham Kakade, Prateek Jain and Ali Farhadi,
in Advances in Neural Information Processing Systems (NeurIPS),
2024.
[BibTeX]
[Abstract]
[URL]
Web-scale search systems learn an encoder to embed a given query which is then hooked into an approximate nearest neighbor search (ANNS) pipeline to retrieve similar data points. To accurately capture tail queries and data points, learned representations typically are _rigid, high-dimensional_ vectors that are generally used as-is in the entire ANNS pipeline and can lead to computationally expensive retrieval. In this paper, we argue that instead of rigid representations, different stages of ANNS can leverage _adaptive representations_ of varying capacities to achieve significantly better accuracy-compute trade-offs, ie, stages of ANNS that can get away with more approximate computation should use a lower-capacity representation of the same data point. To this end, we introduce AdANNS, a novel ANNS design framework that explicitly leverages the flexibility of Matryoshka Representations. We demonstrate state-of-the-art accuracy-compute trade-offs using novel AdANNS-based key ANNS building blocks like search data structures (AdANNS-IVF) and quantization (AdANNS-OPQ). For example on ImageNet retrieval, AdANNS-IVF is up to % more accurate than the rigid representations-based IVF at the same compute budget; and matches accuracy while being up to faster in _wall-clock time_. For Natural Questions, -byte AdANNS-OPQ matches the accuracy of the -byte OPQ baseline constructed using rigid representations--_same accuracy at half the cost! _ We further show that the gains from AdANNS translate to modern-day composite ANNS indices that combine search structures and quantization. Finally, we demonstrate that …
@inproceedings{RegeKFCKJF24,
author = {Aniket Rege, Aditya Kusupati, Alan Fan, Qingqing Cao, Sham Kakade, Prateek Jain, Ali Farhadi},
title = {Adanns: A framework for adaptive semantic search},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2024},
url = {all_papers/RegeKFCKJF24.pdf}
}
Matformer: Nested transformer for elastic inference
Fnu Devvrit, Sneha Kudugunta, Aditya Kusupati, Tim Dettmers, Kaifeng Chen, Inderjit S. Dhillon, Yulia Tsvetkov, Hannaneh Hajishirzi, Sham M. Kakade, Ali Farhadi and Prateek Jain,
in Workshop on Advancing Neural Network Training: Computational Efficiency, Scalability, and Resource Optimization (WANT@ NeurIPS 2023),
2023.
[BibTeX]
[Abstract]
[URL]
Transformer models are deployed in a wide range of settings, from multi-accelerator clusters to standalone mobile phones. The diverse inference constraints in these scenarios necessitate practitioners to train foundation models such as PaLM 2, Llama, & ViTs as a series of models of varying sizes. Due to significant training costs, only a select few model sizes are trained and supported, limiting more fine-grained control over relevant tradeoffs, including latency, cost, and accuracy. This work introduces MatFormer, a nested Transformer architecture designed to offer elasticity in a variety of deployment constraints. Each Feed Forward Network (FFN) block of a MatFormer model is jointly optimized with a few nested smaller FFN blocks. This training procedure allows for the Mix'n'Match of model granularities across layers -- i.e., a trained universal MatFormer model enables extraction of hundreds of accurate smaller models, which were never explicitly optimized. We empirically demonstrate MatFormer's effectiveness across different model classes (decoders & encoders), modalities (language & vision), and scales (up to 2.6B parameters). We find that a 2.6B decoder-only MatFormer language model (MatLM) allows us to extract smaller models spanning from 1.5B to 2.6B, each exhibiting comparable validation loss and one-shot downstream evaluations to their independently trained counterparts. Furthermore, we observe that smaller encoders extracted from a universal MatFormer-based ViT (MatViT) encoder preserve the metric-space structure for adaptive large-scale retrieval. Finally, we showcase that speculative decoding with the accurate and …
@inproceedings{DevvritKKDCDTHKFJ23,
author = {Fnu Devvrit, Sneha Kudugunta, Aditya Kusupati, Tim Dettmers, Kaifeng Chen, Inderjit S Dhillon, Yulia Tsvetkov, Hannaneh Hajishirzi, Sham M Kakade, Ali Farhadi, Prateek Jain},
title = {Matformer: Nested transformer for elastic inference},
booktitle = {Workshop on Advancing Neural Network Training: Computational Efficiency, Scalability, and Resource Optimization (WANT@ NeurIPS 2023)},
year = {2023},
url = {all_papers/DevvritKKDCDTHKFJ23.pdf}
}
Multi-task differential privacy under distribution skew
Walid Krichene, Prateek Jain, Shuang Song, Mukund Sundararajan, Abhradeep Guha Thakurta and Li Zhang,
in International Conference on Machine Learning,
2023.
[BibTeX]
[Abstract]
[URL]
We study the problem of multi-task learning under user-level differential privacy, in which n users contribute data to m tasks, each involving a subset of users. One important aspect of the problem, that can significantly impact quality, is the distribution skew among tasks. Tasks that have much fewer data samples than others are more susceptible to the noise added for privacy. It is natural to ask whether algorithms can adapt to this skew to improve the overall utility. We give a systematic analysis of the problem, by studying how to optimally allocate a user’s privacy budget among tasks. We propose a generic algorithm, based on an adaptive reweighting of the empirical loss, and show that in the presence of distribution skew, this gives a quantifiable improvement of excess empirical risk. Experimental studies on recommendation problems that exhibit a long tail of small tasks, demonstrate that our methods significantly improve utility, achieving the state of the art on two standard benchmarks.
@inproceedings{KricheneJSSTZ23,
author = {Walid Krichene, Prateek Jain, Shuang Song, Mukund Sundararajan, Abhradeep Guha Thakurta, Li Zhang},
title = {Multi-task differential privacy under distribution skew},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {17784-17807},
url = {all_papers/KricheneJSSTZ23.pdf}
}
Multi-user reinforcement learning with low rank rewards
Dheeraj Mysore Nagaraj, Suhas S. Kowshik, Naman Agarwal, Praneeth Netrapalli and Prateek Jain,
in International Conference on Machine Learning,
2023.
[BibTeX]
[Abstract]
[URL]
We consider collaborative multi-user reinforcement learning, where multiple users have the same state-action space and transition probabilities but different rewards. Under the assumption that the reward matrix of the users has a low-rank structure–a standard and practically successful assumption in the collaborative filtering setting–we design algorithms with significantly lower sample complexity compared to the ones that learn the MDP individually for each user. Our main contribution is an algorithm which explores rewards collaboratively with user-specific MDPs and can learn rewards efficiently in two key settings: tabular MDPs and linear MDPs. When is large and the rank is constant, the sample complexity per MDP depends logarithmically over the size of the state-space, which represents an exponential reduction (in the state-space size) when compared to the standard “non-collaborative” algorithms. Our main technical contribution is a method to construct policies which obtain data such that low rank matrix completion is possible (without a generative model). This goes beyond the regular RL framework and is closely related to mean field limits of multi-agent RL.
@inproceedings{NagarajKANJ23,
author = {Dheeraj Mysore Nagaraj, Suhas S Kowshik, Naman Agarwal, Praneeth Netrapalli, Prateek Jain},
title = {Multi-user reinforcement learning with low rank rewards},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {25627-25659},
url = {all_papers/NagarajKANJ23.pdf}
}
Optimal algorithms for latent bandits with cluster structure
Soumyabrata Pal, Arun Sai Suggala, Karthikeyan Shanmugam and Prateek Jain,
in International Conference on Artificial Intelligence and Statistics,
2023.
[BibTeX]
[Abstract]
[URL]
We consider the problem of latent bandits with cluster structure where there are multiple users, each with an associated multi-armed bandit problem. These users are grouped into latent clusters such that the mean reward vectors of users within the same cluster are identical. At each round, a user, selected uniformly at random, pulls an arm and observes a corresponding noisy reward. The goal of the users is to maximize their cumulative rewards. This problem is central to practical recommendation systems and has received wide attention of late Gentile et al.(2014), Maillard and Mannor (2014). Now, if each user acts independently, then they would have to explore each arm independently and a regret of is unavoidable, where M, N are the number of arms and users, respectively. Instead, we propose LATTICE (Latent bAndiTs via maTrIx ComplEtion) which allows exploration of the latent cluster structure to provide the minimax optimal regret of when the number of clusters is . This is the first algorithm to guarantee such strong regret bound. LATTICE is based on a careful exploitation of arm information within a cluster while simultaneously clustering users. Furthermore, it is computationally efficient and requires only calls to an offline matrix completion oracle across all T rounds.
@inproceedings{PalSSJ23,
author = {Soumyabrata Pal, Arun Sai Suggala, Karthikeyan Shanmugam, Prateek Jain},
title = {Optimal algorithms for latent bandits with cluster structure},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2023},
pages = {7540-7577},
url = {all_papers/PalSSJ23.pdf}
}
Reproducibility in optimization: Theoretical framework and limits
Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli and Gil I. Shamir,
in Advances in Neural Information Processing Systems (NeurIPS),
2022.
[BibTeX]
[Abstract]
[URL]
We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.
@inproceedings{AhnJJKNS22,
author = {Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, Gil I Shamir},
title = {Reproducibility in optimization: Theoretical framework and limits},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2022},
pages = {18022-18033},
url = {all_papers/AhnJJKNS22.pdf}
}
S3GC: scalable self-supervised graph clustering
Fnu Devvrit, Aditya Sinha, Inderjit Dhillon and Prateek Jain,
in Advances in Neural Information Processing Systems (NeurIPS),
2022.
[BibTeX]
[Abstract]
[URL]
We study the problem of clustering graphs with additional side-information of node features. The problem is extensively studied, and several existing methods exploit Graph Neural Networks to learn node representations. However, most of the existing methods focus on generic representations instead of their cluster-ability or do not scale to large scale graph datasets. In this work, we propose S3GC which uses contrastive learning along with Graph Neural Networks and node features to learn clusterable features. We empirically demonstrate that S3GC is able to learn the correct cluster structure even when graph information or node features are individually not informative enough to learn correct clusters. Finally, using extensive evaluation on a variety of benchmarks, we demonstrate that S3GC is able to significantly outperform state-of-the-art methods in terms of clustering accuracy--with as much as 5% gain in NMI--while being scalable to graphs of size 100M.
@inproceedings{DevvritSDJ22,
author = {Fnu Devvrit, Aditya Sinha, Inderjit Dhillon, Prateek Jain},
title = {S3GC: scalable self-supervised graph clustering},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2022},
pages = {3248-3261},
url = {all_papers/DevvritSDJ22.pdf}
}
Matryoshka representation learning
Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ramanujan, William Howard-Snyder, Kaifeng Chen, Sham Kakade, Prateek Jain and Ali Farhadi,
in Advances in Neural Information Processing Systems (NeurIPS),
2022.
[BibTeX]
[Abstract]
[URL]
Learned representations are a central component in modern ML systems, serving a multitude of downstream tasks. When training such representations, it is often the case that computational and statistical constraints for each downstream task are unknown. In this context rigid, fixed capacity representations can be either over or under-accommodating to the task at hand. This leads us to ask: can we design a flexible representation that can adapt to multiple downstream tasks with varying computational resources? Our main contribution is Matryoshka Representation Learning (MRL) which encodes information at different granularities and allows a single embedding to adapt to the computational constraints of downstream tasks. MRL minimally modifies existing representation learning pipelines and imposes no additional cost during inference and deployment. MRL learns coarse-to-fine representations that are at least as accurate and rich as independently trained low-dimensional representations. The flexibility within the learned Matryoshka Representations offer:(a) up to smaller embedding size for ImageNet-1K classification at the same level of accuracy;(b) up to real-world speed-ups for large-scale retrieval on ImageNet-1K and 4K; and (c) up to accuracy improvements for long-tail few-shot classification, all while being as robust as the original representations. Finally, we show that MRL extends seamlessly to web-scale datasets (ImageNet, JFT) across various modalities--vision (ViT, ResNet), vision+ language (ALIGN) and language (BERT). MRL code and pretrained models are open-sourced at https://github. com/RAIVNLab/MRL.
@inproceedings{KusupatiBRWSRHCKJF22,
author = {Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ramanujan, William Howard-Snyder, Kaifeng Chen, Sham Kakade, Prateek Jain, Ali Farhadi},
title = {Matryoshka representation learning},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2022},
pages = {30233-30249},
url = {all_papers/KusupatiBRWSRHCKJF22.pdf}
}
Feature reconstruction from outputs can mitigate simplicity bias in neural networks
Sravanti Addepalli, Anshul Nasery, Venkatesh Babu Radhakrishnan, Praneeth Netrapalli and Prateek Jain,
in The Eleventh International Conference on Learning Representations,
2022.
[BibTeX]
[Abstract]
[URL]
Deep Neural Networks are known to be brittle to even minor distribution shifts compared to the training distribution. While one line of work has demonstrated that \emph{Simplicity Bias} (SB) of DNNs -- bias towards learning only the simplest features -- is a key reason for this brittleness, another recent line of work has surprisingly found that diverse/ complex features are indeed learned by the backbone, and their brittleness is due to the linear classification head relying primarily on the simplest features. To bridge the gap between these two lines of work, we first hypothesize and verify that while SB may not altogether preclude learning complex features, it amplifies simpler features over complex ones. Namely, simple features are replicated several times in the learned representations while complex features might not be replicated. This phenomenon, we term \emph{Feature Replication Hypothesis}, coupled with the \emph{Implicit Bias} of SGD to converge to maximum margin solutions in the feature space, leads the models to rely mostly on the simple features for classification. To mitigate this bias, we propose \emph{Feature Reconstruction Regularizer (FRR)} to ensure that the learned features can be reconstructed back from the logits. The use of \emph{FRR} in linear layer training (\emph{FRR-L}) encourages the use of more diverse features for classification. We further propose to finetune the full network by freezing the weights of the linear layer trained using \emph{FRR-L}, to refine the learned features, making them more suitable for classification. Using this simple solution, we demonstrate up to 15\% gains in OOD accuracy on the recently …
@inproceedings{AddepalliNRNJ22,
author = {Sravanti Addepalli, Anshul Nasery, Venkatesh Babu Radhakrishnan, Praneeth Netrapalli, Prateek Jain},
title = {Feature reconstruction from outputs can mitigate simplicity bias in neural networks},
booktitle = {The Eleventh International Conference on Learning Representations},
year = {2022},
url = {all_papers/AddepalliNRNJ22.pdf}
}
DAFT: Distilling Adversarially Fine-tuned teachers for OOD Robustness
Anshul Nasery, Sravanti Addepalli, Praneeth Netrapalli and Prateek Jain,
in ICML 2022: Workshop on Spurious Correlations, Invariance and Stability,
2022.
[BibTeX]
[Abstract]
[URL]
We consider the problem of OOD generalization,where the goal is to train a model that performs well on test distributions that are different from the training distribution. Deep learning models are known to be fragile to such shifts and can suffer large accuracy drops even for slightly different test distributions (Hendrycks & Dietterich, 2019).We propose a new method –DAFT– based on the intuition that adversarially robust combination of a large number of rich features should provide OOD robustness. Our method carefully distills the model from a powerful teacher that learns several discriminative features using standard training while combining them using adversarial training. The standard adversarial training procedure is modified to produce teachers which can guide the student better. We evaluate DAFT on standard benchmarks in the DomainBed framework, and find that DAFT consistently out-performs well-tuned ERM and distillation baselines by up to 6%, with more pronounced gains for smaller networks
@inproceedings{NaseryANJ22,
author = {Anshul Nasery, Sravanti Addepalli, Praneeth Netrapalli, Prateek Jain},
title = {DAFT: Distilling Adversarially Fine-tuned teachers for OOD Robustness},
booktitle = {ICML 2022: Workshop on Spurious Correlations, Invariance and Stability},
year = {2022},
url = {all_papers/NaseryANJ22.pdf}
}
(Nearly) Optimal Private Linear Regression for Sub-Gaussian Data via Adaptive Clipping
Prateek Varshney, Abhradeep Thakurta and Prateek Jain,
in Conference on Learning Theory,
2022.
[BibTeX]
[Abstract]
[URL]
We study the problem of differentially private linear regression where each of the data point is sampled from a fixed sub-Gaussian style distribution. We propose and analyze a one-pass mini-batch stochastic gradient descent method (DP-AMBSSGD) where points in each iteration are sampled without replacement. Noise is added for DP but the noise standard deviation is estimated online. Compared to existing -DP techniques which have sub-optimal error bounds, DP-AMBSSGD is able to provide nearly optimal error bounds in terms of key parameters like dimensionality , number of points , and the standard deviation\sigma of the noise in observations. For example, when the -dimensional covariates are sampled iid from the normal distribution, then the excess error of DP-AMBSSGD due to privacy is , ie, the error is meaningful when number of samples N\geq d\log d which is the standard operative regime for linear regression. In contrast, error bounds for existing efficient methods in this setting are: , even for . That is, for constant , the existing techniques require to provide a non-trivial result.
@inproceedings{VarshneyTJ22,
author = {Prateek Varshney, Abhradeep Thakurta, Prateek Jain},
title = {(Nearly) Optimal Private Linear Regression for Sub-Gaussian Data via Adaptive Clipping},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {1126-1166},
url = {all_papers/VarshneyTJ22.pdf}
}
Robust training in high dimensions via block coordinate geometric median descent
Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S. Dhillon and Ufuk Topcu,
in International Conference on Artificial Intelligence and Statistics,
2022.
[BibTeX]
[Abstract]
[URL]
Geometric median (GM) is a classical method in statistics for achieving robust estimation of the uncorrupted data; under gross corruption, it achieves the optimal breakdown point of 1/2. However, its computational complexity makes it infeasible for robustifying stochastic gradient descent (SGD) in high-dimensional optimization problems. In this paper, we show that by applying GM to only a judiciously chosen block of coordinates at a time and using a memory mechanism, one can retain the breakdown point of 1/2 for smooth non-convex problems, with non-asymptotic convergence rates comparable to the SGD with GM while resulting in significant speedup in training. We further validate the run-time and robustness of our approach empirically on several popular deep learning tasks. Code available at: https://github. com/anishacharya/BGMD
@inproceedings{AcharyaHJSDT22,
author = {Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S Dhillon, Ufuk Topcu},
title = {Robust training in high dimensions via block coordinate geometric median descent},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2022},
pages = {11145-11168},
url = {all_papers/AcharyaHJSDT22.pdf}
}
Streaming linear system identification with reverse experience replay
Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain and Praneeth Netrapalli,
in Advances in Neural Information Processing Systems (NeurIPS),
2021.
[BibTeX]
[Abstract]
[URL]
We consider the problem of estimating a linear time-invariant (LTI) dynamical system from a single trajectory via streaming algorithms, which is encountered in several applications including reinforcement learning (RL) and time-series analysis. While the LTI system estimation problem is well-studied in the {\em offline} setting, the practically important streaming/online setting has received little attention. Standard streaming methods like stochastic gradient descent (SGD) are unlikely to work since streaming points can be highly correlated. In this work, we propose a novel streaming algorithm, SGD with Reverse Experience Replay (SGD-RER), that is inspired by the experience replay (ER) technique popular in the RL literature. SGD-RER divides data into small buffers and runs SGD backwards on the data stored in the individual buffers. We show that this algorithm exactly deconstructs the dependency structure and obtains information theoretically optimal guarantees for both parameter error and prediction error. Thus, we provide the first--to the best of our knowledge--optimal SGD-style algorithm for the classical problem of linear system identification with a first order oracle. Furthermore, SGD-RER can be applied to more general settings like sparse LTI identification with known sparsity pattern, and non-linear dynamical systems. Our work demonstrates that the knowledge of data dependency structure can aid us in designing statistically and computationally efficient algorithms which can``decorrelate''streaming samples.
@inproceedings{KowshikNJN21,
author = {Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain, Praneeth Netrapalli},
title = {Streaming linear system identification with reverse experience replay},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2021},
pages = {30140-30152},
url = {all_papers/KowshikNJN21.pdf}
}
Near-optimal offline and streaming algorithms for learning non-linear dynamical systems
Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain and Praneeth Netrapalli,
in Advances in Neural Information Processing Systems (NeurIPS),
2021.
[BibTeX]
[Abstract]
[URL]
We consider the setting of vector valued non-linear dynamical systems , where is unbiased noise and is a known link function that satisfies certain {\em expansivity property}. The goal is to learn from a single trajectory of {\em dependent or correlated} samples. While the problem is well-studied in the linear case, where is identity, with optimal error rates even for non-mixing systems, existing results in the non-linear case hold only for mixing systems. In this work, we improve existing results for learning nonlinear systems in a number of ways: a) we provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) we significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting we study a SGD with Reverse Experience Replay (SGD-RER) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) we justify the expansivity assumption by showing that for the popular ReLU link function---a non-expansive but easy to learn link function with iid samples---any method would require exponentially many samples (with respect to dimension of ) from the dynamical system. We validate our results via. simulations and demonstrate that a naive application of SGD can be highly sub-optimal. Indeed, our work demonstrates that for correlated data, specialized methods designed for the dependency structure in data can significantly outperform standard SGD based methods.
@inproceedings{KowshikNJN21,
author = {Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain, Praneeth Netrapalli},
title = {Near-optimal offline and streaming algorithms for learning non-linear dynamical systems},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2021},
pages = {8518-8531},
url = {all_papers/KowshikNJN21.pdf}
}
Do input gradients highlight discriminative features?
Harshay Shah, Prateek Jain and Praneeth Netrapalli,
in Advances in Neural Information Processing Systems (NeurIPS),
2021.
[BibTeX]
[Abstract]
[URL]
Post-hoc gradient-based interpretability methods [Simonyan et al., 2013, Smilkov et al., 2017] that provide instance-specific explanations of model predictions are often based on assumption (A): magnitude of input gradients—gradients of logits with respect to input—noisily highlight discriminative task-relevant features. In this work, we test the validity of assumption (A) using a three-pronged approach: 1. We develop an evaluation framework, DiffROAR, to test assumption (A) on four image classification benchmarks. Our results suggest that (i) input gradients of standard models (ie, trained on original data) may grossly violate (A), whereas (ii) input gradients of adversarially robust models satisfy (A). 2. We then introduce BlockMNIST, an MNIST-based semi-real dataset, that by design encodes a priori knowledge of discriminative features. Our analysis on BlockMNIST leverages this information to validate as well as characterize differences between input gradient attributions of standard and robust models. 3. Finally, we theoretically prove that our empirical findings hold on a simplified version of the BlockMNIST dataset. Specifically, we prove that input gradients of standard one-hidden-layer MLPs trained on this dataset do not highlight instance-specific signal coordinates, thus grossly violating assumption (A). Our findings motivate the need to formalize and test common assumptions in interpretability in a falsifiable manner [Leavitt and Morcos, 2020]. We believe that the DiffROAR evaluation framework and BlockMNIST-based datasets can serve as sanity checks to audit instance-specific interpretability methods; code and data available at https://github …
@inproceedings{ShahJN21,
author = {Harshay Shah, Prateek Jain, Praneeth Netrapalli},
title = {Do input gradients highlight discriminative features?},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2021},
pages = {2046-2059},
url = {all_papers/ShahJN21.pdf}
}
Statistically and computationally efficient linear meta-representation learning
Kiran K. Thekumparampil, Prateek Jain, Praneeth Netrapalli and Sewoong Oh,
in Advances in Neural Information Processing Systems (NeurIPS),
2021.
[BibTeX]
[Abstract]
[URL]
In typical few-shot learning, each task is not equipped with enough data to be learned in isolation. To cope with such data scarcity, meta-representation learning methods train across many related tasks to find a shared (lower-dimensional) representation of the data where all tasks can be solved accurately. It is hypothesized that any new arriving tasks can be rapidly trained on this low-dimensional representation using only a few samples. Despite the practical successes of this approach, its statistical and computational properties are less understood. Moreover, the prescribed algorithms in these studies have little resemblance to those used in practice or they are computationally intractable. To understand and explain the success of popular meta-representation learning approaches such as ANIL, MetaOptNet, R2D2, and OML, we study a alternating gradient-descent minimization (AltMinGD) method (and its variant alternating minimization (AltMin)) which underlies the aforementioned methods. For a simple but canonical setting of shared linear representations, we show that AltMinGD achieves nearly-optimal estimation error, requiring only samples per task. This agrees with the observed efficacy of this algorithm in the practical few-shot learning scenarios.
@inproceedings{ThekumparampilJNO21,
author = {Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh},
title = {Statistically and computationally efficient linear meta-representation learning},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2021},
pages = {18487-18500},
url = {all_papers/ThekumparampilJNO21.pdf}
}
Private alternating least squares: Practical private matrix completion with tighter rates
Steve Chien, Prateek Jain, Walid Krichene, Steffen Rendle, Shuang Song, Abhradeep Thakurta and Li Zhang,
in International Conference on Machine Learning,
2021.
[BibTeX]
[Abstract]
[URL]
We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method that achieves: i)(nearly) optimal sample complexity for matrix completion (in terms of number of items, users), and ii) the best known privacy/utility trade-off both theoretically, as well as on benchmark data sets. In particular, we provide the first global convergence analysis of ALS with noise introduced to ensure DP, and show that, in comparison to the best known alternative (the Private Frank-Wolfe algorithm by Jain et al.(2018)), our error bounds scale significantly better with respect to the number of items and users, which is critical in practical problems. Extensive validation on standard benchmarks demonstrate that the algorithm, in combination with carefully designed sampling procedures, is significantly more accurate than existing techniques, thus promising to be the first practical DP embedding model.
@inproceedings{ChienJKRSTZ21,
author = {Steve Chien, Prateek Jain, Walid Krichene, Steffen Rendle, Shuang Song, Abhradeep Thakurta, Li Zhang},
title = {Private alternating least squares: Practical private matrix completion with tighter rates},
booktitle = {International Conference on Machine Learning},
year = {2021},
pages = {1877-1887},
url = {all_papers/ChienJKRSTZ21.pdf}
}
Optimal regret algorithm for pseudo-1d bandit convex optimization
Aadirupa Saha, Nagarajan Natarajan, Praneeth Netrapalli and Prateek Jain,
in International Conference on Machine Learning,
2021.
[BibTeX]
[Abstract]
[URL]
We study online learning with bandit feedback (ie learner has access to only zeroth-order oracle) where cost/reward functions $\f_t $ admit a" pseudo-1d" structure, ie $\f_t (\w)=\loss_t (\pred_t (\w)) $ where the output of $\pred_t $ is one-dimensional. At each round, the learner observes context $\x_t $, plays prediction $\pred_t (\w_t;\x_t) $(eg $\pred_t (\cdot)=⟨\x_t,\cdot⟩ $) for some $\w_t\in\mathbb {R}^ d $ and observes loss $\loss_t (\pred_t (\w_t)) $ where $\loss_t $ is a convex Lipschitz-continuous function. The goal is to minimize the standard regret metric. This pseudo-1d bandit convex optimization problem (\SBCO) arises frequently in domains such as online decision-making or parameter-tuning in large systems. For this problem, we first show a regret lower bound of for any algorithm, where is the number of rounds. We propose a new algorithm\sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively, guaranteeing the {\em optimal} regret bound mentioned above, up to additional logarithmic factors. In contrast, applying state-of-the-art online convex optimization methods leads to regret, that is significantly suboptimal in terms of .
@inproceedings{SahaNNJ21,
author = {Aadirupa Saha, Nagarajan Natarajan, Praneeth Netrapalli, Prateek Jain},
title = {Optimal regret algorithm for pseudo-1d bandit convex optimization},
booktitle = {International Conference on Machine Learning},
year = {2021},
pages = {9255-9264},
url = {all_papers/SahaNNJ21.pdf}
}
RNNPool: Efficient non-linear pooling for RAM constrained inference
Oindrila Saha, Aditya Kusupati, Harsha Vardhan Simhadri, Manik Varma and Prateek Jain,
in Advances in Neural Information Processing Systems (NeurIPS),
2020.
[BibTeX]
[Abstract]
[URL]
Standard Convolutional Neural Networks (CNNs) designed for computer vision tasks tend to have large intermediate activation maps. These require large working memory and are thus unsuitable for deployment on resource-constrained devices typically used for inference on the edge. Aggressively downsampling the images via pooling or strided convolutions can address the problem but leads to a significant decrease in accuracy due to gross aggregation of the feature map by standard pooling operators. In this paper, we introduce RNNPool, a novel pooling operator based on Recurrent Neural Networks (RNNs), that efficiently aggregates features over large patches of an image and rapidly downsamples activation maps. Empirical evaluation indicates that an RNNPool layer can effectively replace multiple blocks in a variety of architectures such as MobileNets, DenseNet when applied to standard vision tasks like image classification and face detection. That is, RNNPool can significantly decrease computational complexity and peak memory usage for inference while retaining comparable accuracy. We use RNNPool with the standard S3FD architecture to construct a face detection method that achieves state-of-the-art MAP for tiny ARM Cortex-M4 class microcontrollers with under 256 KB of RAM. Code is released at https://github. com/Microsoft/EdgeML.
@inproceedings{SahaKSVJ20,
author = {Oindrila Saha, Aditya Kusupati, Harsha Vardhan Simhadri, Manik Varma, Prateek Jain},
title = {RNNPool: Efficient non-linear pooling for RAM constrained inference},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2020},
pages = {20473-20484},
url = {all_papers/SahaKSVJ20.pdf}
}
The pitfalls of simplicity bias in neural networks
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain and Praneeth Netrapalli,
in Advances in Neural Information Processing Systems (NeurIPS),
2020.
[BibTeX]
[Abstract]
[URL]
Several works have proposed Simplicity Bias (SB)---the tendency of standard training procedures such as Stochastic Gradient Descent (SGD) to find simple models---to justify why neural networks generalize well [Arpit et al. 2017, Nakkiran et al. 2019, Valle-Perez et al. 2019]. However, the precise notion of simplicity remains vague. Furthermore, previous settings [Soudry et al. 2018, Gunasekar et al. 2018] that use SB to theoretically justify why neural networks generalize well do not simultaneously capture the non-robustness of neural networks---a widely observed phenomenon in practice [Goodfellow et al. 2014, Jo and Bengio 2017]. We attempt to reconcile SB and the superior standard generalization of neural networks with the non-robustness observed in practice by introducing piecewise-linear and image-based datasets, which (a) incorporate a precise notion of simplicity,(b) comprise multiple predictive features with varying levels of simplicity, and (c) capture the non-robustness of neural networks trained on real data. Using theory and empirics on these datasets, we make four observations:(i) SB of SGD and variants can be extreme: neural networks can exclusively rely on the simplest feature and remain invariant to all predictive complex features.(ii) The extreme aspect of SB could explain why seemingly benign distribution shifts and small adversarial perturbations significantly degrade model performance.(iii) Contrary to conventional wisdom, SB can also hurt generalization on the same data distribution, as SB persists even when the simplest feature has less predictive power than the more complex features.(iv) Common approaches to …
@inproceedings{ShahTRJN20,
author = {Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, Praneeth Netrapalli},
title = {The pitfalls of simplicity bias in neural networks},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2020},
pages = {9573-9585},
url = {all_papers/ShahTRJN20.pdf}
}
Projection efficient subgradient method and optimal nonsmooth frank-wolfe method
Kiran K. Thekumparampil, Prateek Jain, Praneeth Netrapalli and Sewoong Oh,
in Advances in Neural Information Processing Systems (NeurIPS),
2020.
[BibTeX]
[Abstract]
[URL]
We consider the classical setting of optimizing a nonsmooth Lipschitz continuous convex function over a convex constraint set, when having access to a (stochastic) first-order oracle (FO) for the function and a projection oracle (PO) for the constraint set. It is well known that to achieve -suboptimality in high-dimensions, FO calls are necessary. This is achieved by the projected subgradient method (PGD). However, PGD also entails PO calls, which may be computationally costlier than FO calls (eg nuclear norm constraints). Improving this PO calls complexity of PGD is largely unexplored, despite the fundamental nature of this problem and extensive literature. We present first such improvement. This only requires a mild assumption that the objective function, when extended to a slightly larger neighborhood of the constraint set, still remains Lipschitz and accessible via FO. In particular, we introduce MOPES method, which carefully combines Moreau-Yosida smoothing and accelerated first-order schemes. This is guaranteed to find a feasible -suboptimal solution using only PO calls and optimal FO calls. Further, instead of a PO if we only have a linear minimization oracle (LMO, a la Frank-Wolfe) to access the constraint set, an extension of our method, MOLES, finds a feasible -suboptimal solution using LMO calls and FO calls---both match known lower bounds, resolving a question left open since White (1993). Our experiments confirm that these methods achieve significant speedups over the state-of-the-art, for a problem with costly PO and LMO calls.
@inproceedings{ThekumparampilJNO20,
author = {Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh},
title = {Projection efficient subgradient method and optimal nonsmooth frank-wolfe method},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2020},
pages = {12211-12224},
url = {all_papers/ThekumparampilJNO20.pdf}
}
DROCC: Deep robust one-class classification
Sachin Goyal, Aditi Raghunathan, Moksh Jain, Harsha Vardhan Simhadri and Prateek Jain,
in International conference on machine learning,
2020.
[BibTeX]
[Abstract]
[URL]
Classical approaches for one-class problems such as one-class SVM and isolation forest require careful feature engineering when applied to structured domains like images. State-of-the-art methods aim to leverage deep learning to learn appropriate features via two main approaches. The first approach based on predicting transformations (Golan & El-Yaniv, 2018; Hendrycks et al., 2019a) while successful in some domains, crucially depends on an appropriate domain-specific set of transformations that are hard to obtain in general. The second approach of minimizing a classical one-class loss on the learned final layer representations, eg, DeepSVDD (Ruff et al., 2018) suffers from the fundamental drawback of representation collapse. In this work, we propose Deep Robust One Class Classification (DROCC) that is both applicable to most standard domains without requiring any side-information and robust to representation collapse. DROCC is based on the assumption that the points from the class of interest lie on a well-sampled, locally linear low dimensional manifold. Empirical evaluation demonstrates that DROCC is highly effective in two different one-class problem settings and on a range of real-world datasets across different domains: tabular data, images (CIFAR and ImageNet), audio, and time-series, offering up to 20% increase in accuracy over the state-of-the-art in anomaly detection. Code is available at https://github. com/microsoft/EdgeML
@inproceedings{GoyalRJSJ20,
author = {Sachin Goyal, Aditi Raghunathan, Moksh Jain, Harsha Vardhan Simhadri, Prateek Jain},
title = {DROCC: Deep robust one-class classification},
booktitle = {International conference on machine learning},
year = {2020},
pages = {3711-3721},
url = {all_papers/GoyalRJSJ20.pdf}
}
Optimization and Analysis of the pAp@ k Metric for Recommender Systems
Gaurush Hiranandani, Warut Vijitbenjaronk, Sanmi Koyejo and Prateek Jain,
in International Conference on Machine Learning,
2020.
[BibTeX]
[Abstract]
[URL]
Modern recommendation and notification systems must be robust to data imbalance, limitations on the number of recommendations/notifications, and heterogeneous engagement profiles across users. The pAp@ k metric, which combines the partial-AUC and the precision@ k metrics, was recently proposed to evaluate such recommendation systems and has been used in real-world deployments. Conceptually, pAp@ k measures the probability of correctly ranking a top-ranked positive instance over top-ranked negative instances. Due to the combinatorial aspect surfaced by top-ranked points, little is known about the characteristics and optimization methods of pAp@ k. In this paper, we analyze the learning-theoretic properties of pAp@ k, particularly its benefits in evaluating modern recommender systems, and propose novel surrogates that are consistent under certain data regularity conditions. We then provide gradient descent based algorithms to optimize the surrogates directly. Our analysis and experimental evaluation suggest that pAp@ k indeed exhibits a certain dual behavior with respect to partial-AUC and precision@ k. Moreover, the proposed methods outperform all the baselines in various applications. Taken together, our results motivate the use of pAp@ k for large-scale recommender systems with heterogeneous user-engagement.
@inproceedings{HiranandaniVKJ20,
author = {Gaurush Hiranandani, Warut Vijitbenjaronk, Sanmi Koyejo, Prateek Jain},
title = {Optimization and Analysis of the pAp@ k Metric for Recommender Systems},
booktitle = {International Conference on Machine Learning},
year = {2020},
pages = {4260-4270},
url = {all_papers/HiranandaniVKJ20.pdf}
}
Soft threshold weight reparameterization for learnable sparsity
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade and Ali Farhadi,
in International Conference on Machine Learning,
2020.
[BibTeX]
[Abstract]
[URL]
Sparsity in Deep Neural Networks (DNNs) is studied extensively with the focus of maximizing prediction accuracy given an overall parameter budget. Existing methods rely on uniform or heuristic non-uniform sparsity budgets which have sub-optimal layer-wise parameter allocation resulting in a) lower prediction accuracy or b) higher inference cost (FLOPs). This work proposes Soft Threshold Reparameterization (STR), a novel use of the soft-threshold operator on DNN weights. STR smoothly induces sparsity while learning pruning thresholds thereby obtaining a non-uniform sparsity budget. Our method achieves state-of-the-art accuracy for unstructured sparsity in CNNs (ResNet50 and MobileNetV1 on ImageNet-1K), and, additionally, learns non-uniform budgets that empirically reduce the FLOPs by up to 50%. Notably, STR boosts the accuracy over existing results by up to 10% in the ultra sparse (99%) regime and can also be used to induce low-rank (structured sparsity) in RNNs. In short, STR is a simple mechanism which learns effective sparsity budgets that contrast with popular heuristics. Code, pretrained models and sparsity budgets are at https://github. com/RAIVNLab/STR.
@inproceedings{KusupatiRSWJKF20,
author = {Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, Ali Farhadi},
title = {Soft threshold weight reparameterization for learnable sparsity},
booktitle = {International Conference on Machine Learning},
year = {2020},
pages = {5544-5555},
url = {all_papers/KusupatiRSWJKF20.pdf}
}
OASIS: ILP-guided synthesis of loop invariants
Sahil Bhatia, Saswat Padhi, Nagarajan Natarajan, Rahul Sharma and Prateek Jain,
in NeurIPS 2020 Workshop on Computer-Assisted Programming,
2020.
[BibTeX]
[Abstract]
[URL]
Automated synthesis of inductive invariants is an important problem in software verification. We propose a novel technique that is able to solve complex loop invariant synthesis problems involving large number of variables. We reduce the problem of synthesizing invariants to a set of integer linear programming (ILP) problems. We instantiate our techniques in the tool Oasis that outperforms state-of-the-art systems on benchmarks from the invariant synthesis track of the Syntax Guided Synthesis competition.
@inproceedings{BhatiaPNSJ20,
author = {Sahil Bhatia, Saswat Padhi, Nagarajan Natarajan, Rahul Sharma, Prateek Jain},
title = {OASIS: ILP-guided synthesis of loop invariants},
booktitle = {NeurIPS 2020 Workshop on Computer-Assisted Programming},
year = {2020},
url = {all_papers/BhatiaPNSJ20.pdf}
}
A topic-aligned multilingual corpus of Wikipedia articles for studying information asymmetry in low resource languages
Dwaipayan Roy, Sumit Bhatia and Prateek Jain,
in Proceedings of the Twelfth Language Resources and Evaluation Conference,
2020.
[BibTeX]
[Abstract]
[URL]
Wikipedia is the largest web-based open encyclopedia covering more than three hundred languages. However, different language editions of Wikipedia differ significantly in terms of their information coverage. We present a systematic comparison of information coverage in English Wikipedia (most exhaustive) and Wikipedias in eight other widely spoken languages (Arabic, German, Hindi, Korean, Portuguese, Russian, Spanish and Turkish). We analyze the content present in the respective Wikipedias in terms of the coverage of topics as well as the depth of coverage of topics included in these Wikipedias. Our analysis quantifies and provides useful insights about the information gap that exists between different language editions of Wikipedia and offers a roadmap for the IR community to bridge this gap.
@inproceedings{RoyBJ20,
author = {Dwaipayan Roy, Sumit Bhatia, Prateek Jain},
title = {A topic-aligned multilingual corpus of Wikipedia articles for studying information asymmetry in low resource languages},
booktitle = {Proceedings of the Twelfth Language Resources and Evaluation Conference},
year = {2020},
pages = {2373-2380},
url = {all_papers/RoyBJ20.pdf}
}
ShaRNN: A Method for Accurate Time-series Classification on Tiny Devices
Don Dennis, Alp Acar, Mandikal Vikram, Harsha Simhadri, Venkatesh Saligrama and Prateek Jain,
in Proceedings of the Thirty-second Annual Conference on Neural Information Processing Systems (NeurIPS),
2019.
[BibTeX]
[Abstract]
[URL]
Recurrent Neural Networks (RNNs) capture long dependencies and context, and
hence are the key component of typical sequential data based tasks. However, the
sequential nature of RNNs dictates a large inference cost for long sequences even if
the hardware supports parallelization. To induce long-term dependencies, and yet
admit parallelization, we introduce novel shallow RNNs. In this architecture, the
first layer splits the input sequence and runs several independent RNNs. The second
layer consumes the output of the first layer using a second RNN thus capturing
long dependencies. We provide theoretical justification for our architecture under
weak assumptions that we verify on real-world benchmarks. Furthermore, we show
that for time-series classification, our technique leads to substantially improved
inference time over standard RNNs without compromising accuracy. For example,
we can deploy audio-keyword classification on tiny Cortex M4 devices (100MHz
processor, 256KB RAM, no DSP available) which was not possible using standard
RNN models. Similarly, using ShaRNN in the popular Listen-Attend-Spell (LAS)
architecture for phoneme classification, we can reduce the lag in phoneme
classification by 10-12x while maintaining state-of-the-art accuracy.
@inproceedings{DennisAVSSJ19,
author = {Don Dennis and Alp Acar and Mandikal Vikram and Harsha Simhadri and Venkatesh Saligrama and Prateek Jain},
title = {ShaRNN: A Method for Accurate Time-series Classification on Tiny Devices},
booktitle = {Proceedings of the Thirty-second Annual Conference on Neural Information Processing Systems (NeurIPS)},
year = {2019},
url = {all_papers/DennisAVSSJ19.pdf}
}
Efficient Algorithms for Smooth Minimax Optimization
Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli and Sewoong Oh,
in Proceedings of the Thirty-second Annual Conference on Neural Information Processing Systems (NeurIPS),
2019.
[BibTeX]
[Abstract]
[URL]
This paper studies first order methods for solving smooth minimax optimization problems where is smooth and is concave for each . In terms of , we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. For strongly-convex , we propose a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in iterations, improving over current state-of-the-art rate of . We use this result along with an inexact proximal point method to provide rate for finding stationary points in the nonconvex setting where can be nonconvex. This improves over current best-known rate of . Finally, we instantiate our result for finite nonconvex minimax problems, i.e., , with nonconvex , to obtain convergence rate of total gradient evaluations for finding a stationary point.
@inproceedings{TJNO19,
author = {Kiran Koshy Thekumparampil and Prateek Jain and Praneeth Netrapalli and Sewoong Oh},
title = {Efficient Algorithms for Smooth Minimax Optimization},
booktitle = {Proceedings of the Thirty-second Annual Conference on Neural Information Processing Systems (NeurIPS)},
year = {2019},
url = {all_papers/TJNO19.pdf}
}
Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
Kai Zhong, Zhao Song, Prateek Jain and Inderjit S. Dhillon,
in Proceedings of the Thirty-second Annual Conference on Neural Information Processing Systems (NeurIPS),
2019.
[BibTeX]
[Abstract]
[URL]
The goal of a recommendation system is to predict the interest of a user in a given item by exploiting the existing set of ratings as well as certain user/item features. A standard approach to modeling this problem is Inductive Matrix Completion where the predicted rating is modeled as an inner product of the user and the item features projected onto a latent space. In order to learn the parameters effectively from a small number of observed ratings, the latent space is constrained to be low-dimensional which implies that the parameter matrix is constrained to be low-rank. However, such bilinear modeling of the ratings can be limiting in practice and non-linear prediction functions can lead to significant improvements. A natural approach to introducing non-linearity in the prediction function is to apply a non-linear activation function on top of the projected user/item features. Imposition of non-linearities further complicates an already challenging problem that has two sources of non-convexity: a) low-rank structure of the parameter matrix, and b) non-linear activation function. We show that one can still solve the non-linear Inductive Matrix Completion problem using gradient descent type methods as long as the solution is initialized well. That is, close to the optima, the optimization function is strongly convex and hence admits standard optimization techniques, at least for certain activation functions, such as Sigmoid and tanh. We also highlight the importance of the activation function and show how ReLU can behave significantly differently than say a sigmoid function. Finally, we apply our proposed technique to recommendation systems and semi-supervised clustering, and show that our method can lead to much better performance than standard linear Inductive Matrix Completion methods.
@inproceedings{ZhongSJD19,
author = {Kai Zhong and Zhao Song and Prateek Jain and Inderjit S. Dhillon},
title = {Nonlinear Inductive Matrix Completion based on One-layer Neural Networks},
booktitle = {Proceedings of the Thirty-second Annual Conference on Neural Information Processing Systems (NeurIPS)},
year = {2019},
url = {all_papers/ZhongSJD19.pdf}
}
GesturePod: Enabling On-device Gesture-based Interaction for White Cane Users
Shishir G. Patil, Don Kurian Dennis, Chirag Pabbaraju, Nadeem Shaheer, Harsha Vardhan Simhadri, Vivek Seshadri, Manik Varma and Prateek Jain,
in Proceedings of the 32nd Annual ACM Symposium on User Interface Software and Technology (UIST),
2019.
[BibTeX]
[Abstract]
[URL]
People using white canes for navigation find it challenging to concurrently access devices such as smartphones. Building on prior research on abandonment of specialized devices, we explore a new touch free mode of interaction wherein a person with visual impairment can perform gestures on their existing white cane to trigger tasks on their smartphone. We present GesturePod, an easy-to-integrate device that clips on to any white cane, and detects gestures performed with the cane. With GesturePod, a user can perform common tasks on their smartphone without touch or even removing the phone from their pocket or bag. We discuss the challenges in building the device and our design choices. We propose a novel, efficient machine learning pipeline to train and deploy the gesture recognition model. Our in-lab study shows that GesturePod achieves 92 percent gesture recognition accuracy and can help perform common smartphone tasks faster. Our in-wild study suggests that GesturePod is a promising tool to improve smartphone access for people with VI, especially in constrained outdoor scenarios.
@inproceedings{PatilDPSSSVJ19,
author = {Shishir G. Patil and Don Kurian Dennis and Chirag Pabbaraju and Nadeem Shaheer and Harsha Vardhan Simhadri and Vivek Seshadri and Manik Varma and Prateek Jain},
title = {GesturePod: Enabling On-device Gesture-based Interaction for White Cane Users},
booktitle = {Proceedings of the 32nd Annual ACM Symposium on User Interface Software and Technology (UIST)},
year = {2019},
pages = {403--415},
note = {slides/PatilDPSSSVJ19.pdf},
url = {all_papers/PatilDPSSSVJ19.pdf},
doi = {https://doi.org/10.1145/3332165.3347881}
}
Making the Last Iterate of SGD Information Theoretically Optimal
Prateek Jain, Dheeraj Nagaraj and Praneeth Netrapalli,
in Proceedings of the Annual Conference On Learning Theory (COLT),
2019.
[BibTeX]
[Abstract]
[URL]
Stochastic gradient descent (SGD) is one of the most widely used algorithms for large scale optimization problems. While classical theoretical analysis of SGD for convex problems studies (suffix) {averages} of iterates and obtains information theoretically optimal bounds on suboptimality, the {last point} of SGD is, by far, the most preferred choice in practice. The best known results for last point of SGD (Shamir and Zhang, 2013) however, are suboptimal compared to information theoretic lower bounds by a logT factor, where T is the number of iterations. Harvey et. al (2018) shows that in fact, this additional logT factor is tight for standard step size sequences of 1/sqrt(t) and 1/t for non-strongly convex and strongly convex settings, respectively. Similarly, even for subgradient descent (GD) when applied to non-smooth, convex functions, the best known step-size sequences still lead to O(logT)-suboptimal convergence rates (on the final iterate). The main contribution of this work is to design new step size sequences that enjoy information theoretically optimal bounds on the suboptimality of {last point} of SGD as well as GD. We achieve this by designing a modification scheme, that converts one sequence of step sizes to another so that the last point of SGD/GD with modified sequence has the same suboptimality guarantees as the average of SGD/GD with original sequence. We also show that our result holds with high-probability. We validate our results through simulations which demonstrate that the new step size sequence indeed improves the final iterate significantly compared to the standard step size sequences.
@inproceedings{JainNN19,
author = {Prateek Jain and Dheeraj Nagaraj and Praneeth Netrapalli},
title = {Making the Last Iterate of SGD Information Theoretically Optimal},
booktitle = {Proceedings of the Annual Conference On Learning Theory (COLT)},
year = {2019},
pages = {1752--1755},
note = {slides/JainNN19.pdf},
url = {all_papers/JainNN19}
}
Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar and Prateek Jain,
in Proceedings of the Annual Conference On Learning Theory (COLT),
2019.
[BibTeX]
[Abstract]
[URL]
We study the problem of robust linear regression with response variable corruptions. We consider the oblivious adversary model, where the adversary corrupts a fraction of the responses in complete ignorance of the data. We provide a nearly linear time estimator which consistently estimates the true regression vector, even with 1−o(1) fraction of corruptions. Existing results in this setting either don’t guarantee consistent estimates or can only handle a small fraction of corruptions. We also extend our estimator to robust sparse linear regression and show that similar guarantees hold in this setting. Finally, we apply our estimator to the problem of linear regression with heavy-tailed noise and show that our estimator consistently estimates the regression vector even when the noise has unbounded variance (e.g., Cauchy distribution), for which most existing results don’t even apply. Our estimator is based on a novel variant of outlier removal via hard thresholding in which the threshold is chosen adaptively and crucially relies on randomness to escape bad fixed points of the non-convex hard thresholding operation.
@inproceedings{SuggalaBRJ19,
author = {Arun Sai Suggala and Kush Bhatia and Pradeep Ravikumar and Prateek Jain},
title = {Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression},
booktitle = {Proceedings of the Annual Conference On Learning Theory (COLT)},
year = {2019},
pages = {2892--2897},
note = {slides/SuggalaBRJ19.pdf},
url = {all_papers/SuggalaBRJ19.pdf}
}
SGD without Replacement: Sharper Rates for General Smooth Convex Functions
Dheeraj Nagaraj, Prateek Jain and Praneeth Netrapalli,
in Proceedings of the 36th International Conference on Machine Learning (ICML),
2019.
[BibTeX]
[Abstract]
[URL]
We study stochastic gradient descent without replacement (SGDo) for smooth convex functions. SGDo is widely observed to converge faster than true SGD where each sample is drawn independently with replacement (Bottou,2009) and hence, is more popular in practice. But it’s convergence properties are not well understood as sampling without replacement leads to coupling between iterates and gradients. By using method of exchangeable pairs to bound Wasserstein distance, we provide the first non-asymptotic results for SGDo when applied to general smooth, strongly-convex functions. In particular, we show that SGDo converges at a rate of O(1/K2) while SGD is known to converge at O(1/K) rate, where K denotes the number of passes over data and is required to be large enough. Existing results for SGDo in this setting require additional Hessian Lipschitz assumption (Gurbuzbalaban et al, 2015; HaoChen and Sra 2018). For small K, we show SGDo can achieve same convergence rate as SGD for general smooth strongly-convex functions. Existing results in this setting require K=1 and hold only for generalized linear models (Shamir,2016). In addition, by careful analysis of the coupling, for both large and small K, we obtain better dependence on problem dependent parameters like condition number.
@inproceedings{NagarajJN19,
author = {Dheeraj Nagaraj and Prateek Jain and Praneeth Netrapalli},
title = {SGD without Replacement: Sharper Rates for General Smooth Convex Functions},
booktitle = {Proceedings of the 36th International Conference on Machine Learning (ICML)},
year = {2019},
pages = {4703--4711},
note = {slides/NagarajJN19.pdf},
url = {all_papers/NagarajJN19.pdf}
}
Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems
Bhaskar Mukhoty, Govind Gopakumar, Prateek Jain and Purushottam Kar,
in The 22nd International Conference on Artificial Intelligence and Statistics ( AISTATS),
2019.
[BibTeX]
[Abstract]
[URL]
We provide the first global model recovery results for the IRLS (iteratively reweighted least squares) heuristic for robust regression problems. IRLS is known to offer excellent performance, despite bad initializations and data corruption, for several parameter estimation problems. Existing analyses of IRLS frequently require careful initialization, thus offering only local convergence guarantees. We remedy this by proposing augmentations to the basic IRLS routine that not only offer guaranteed global recovery, but in practice also outperform state-of-the-art algorithms for robust regression. Our routines are more immune to hyperparameter misspecification in basic regression tasks, as well as applied tasks such as linear-armed bandit problems. Our theoretical analyses rely on a novel extension of the notions of strong convexity and smoothness to weighted strong convexity and smoothness, and establishing that sub-Gaussian designs offer bounded weighted condition numbers. These notions may be useful in analyzing other algorithms as well.
@inproceedings{MukhotyGJK19,
author = {Bhaskar Mukhoty and Govind Gopakumar and Prateek Jain and Purushottam Kar},
title = {Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems},
booktitle = {The 22nd International Conference on Artificial Intelligence and Statistics ( AISTATS)},
year = {2019},
pages = {313--322},
url = {all_papers/MukhotyGJK19}
}
Learning Natural Programs from a Few Examples in Real-Time
Nagarajan Natarajan, Danny Simmons, Naren Datha, Prateek Jain and Sumit Gulwani,
in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS),
2019.
[BibTeX]
[Abstract]
[URL]
Programming by examples (PBE) is a rapidly growing subfield of AI, that aims to synthesize user-intended programs using input-output examples from the task. As users can provide only a few I/O examples, capturing user-intent accurately and ranking user-intended programs over other programs is challenging even in the simplest of the domains. Commercially deployed PBE systems often require years of engineering effort and domain expertise to devise ranking heuristics for real-time synthesis of accurate programs. But such heuristics may not cater to new domains, or even to a different segment of users from the same domain. In this work, we develop a novel, real-time, ML-based program ranking algorithm that enables synthesis of natural, user-intended, personalized programs. We make two key technical contributions: 1) a new technique to embed programs in a vector space making them amenable to ML-formulations, 2) a novel formulation that interleaves program search with ranking, enabling real-time synthesis of accurate user-intended programs. We implement our solution in the state-of-the-art PROSE framework. The proposed approach learns the intended program with just {\em one} I/O example in a variety of real-world string/date/number manipulation tasks, and outperforms state-of-the-art neural synthesis methods along multiple metrics.
@inproceedings{NatarajanSDJG19,
author = {Nagarajan Natarajan and Danny Simmons and Naren Datha and Prateek Jain and Sumit Gulwani},
title = {Learning Natural Programs from a Few Examples in Real-Time},
booktitle = {Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS)},
year = {2019},
pages = {1714--1722},
note = {slides/NatarajanSDJG19.pdf},
url = {all_papers/NatarajanSDJG19.pdf}
}
Distributional Semantics Meets Multi-Label Learning
Vivek Gupta, Rahul Wadbude, Nagarajan Natarajan, Harish Karnick, Prateek Jain and Piyush Rai,
in Proceedings of the 33rd AAAI Conference on Artificial Intelligence,
2019.
[BibTeX]
[Abstract]
[URL]
We present a label embedding based approach to large-scale multi-label learning, drawing inspiration from ideas rooted in distributional semantics, specifically the Skip Gram Negative Sampling (SGNS) approach, widely used to learn word embeddings. Besides leading to a highly scalable model for multi-label learning, our approach highlights interesting connections between label embedding methods commonly used for multi-label learning and paragraph embedding methods commonly used for learning representations of text data. The framework easily extends to incorporating auxiliary information such as label-label correlations; this is crucial especially when many training instances are only partially annotated. To facilitate end-to-end learning, we develop a joint learning algorithm that can learn the embeddings as well as a regression model that predicts these embeddings for the new input to be annotated, via efficient gradient based methods. We demonstrate the effectiveness of our approach through an extensive set of experiments on a variety of benchmark datasets, and show that the proposed models perform favorably as compared to state-of-the-art methods for large-scale multi-label learning.
@inproceedings{GuptaWNKJR2019,
author = {Vivek Gupta, Rahul Wadbude, Nagarajan Natarajan, Harish Karnick, Prateek Jain, Piyush Rai},
title = {Distributional Semantics Meets Multi-Label Learning},
booktitle = {Proceedings of the 33rd AAAI Conference on Artificial Intelligence},
year = {2019},
url = {all_papers/GuptaWNKJR19.pdf}
}
Multiple Instance Learning for Efficient Sequential Data Classification on Resource-constrained Devices
Don Dennis, Chirag Pabbaraju, Harsha Vardhan Simhadri and Prateek Jain,
in Proceedings of the Thirty-first Annual Conference on Neural Information Processing Systems (NeurIPS),
2018.
[BibTeX]
[Abstract]
[URL]
We study the problem of fast and efficient classification of sequential data (such as time-series) on tiny devices, which is critical for various IoT related applications like audio keyword detection or gesture detection. Such tasks are cast as a standard classification task by sliding windows over the data stream to construct data points. Deploying such classification modules on tiny devices is challenging as predictions over sliding windows of data need to be invoked continuously at a high frequency. Each such predictor instance in itself is expensive as it evaluates large models over long windows of data. In this paper, we address this challenge by exploiting the following two observations about classification tasks arising in typical IoT related applications: (a) the "signature" of a particular class (e.g. an audio keyword) typically occupies a small fraction of the overall data, and (b) class signatures tend to be discernible early on in the data. We propose a method, EMI-RNN, that exploits these observations by using a multiple instance learning formulation along with an early prediction technique to learn a model that achieves better accuracy compared to baseline models, while simultaneously reducing computation by a large fraction. For instance, on a gesture detection benchmark, EMI-RNN improves standard LSTM model’s accuracy by up to 1 percent while requiring 72x less computation. This enables us to deploy such models for continuous real-time prediction on a small device such as Raspberry Pi0 and Arduino variants, a task that the baseline LSTM could not achieve. Finally, we also provide an analysis of our multiple instance learning algorithm in a simple setting and show that the proposed algorithm converges to the global optima at a linear rate, one of the first such result in this domain. The code for EMI-RNN is available at: https://github.com/Microsoft/EdgeML/tree/master/tf/examples/EMI-RNN
@inproceedings{DennisPSJ18,
author = {Don Dennis and Chirag Pabbaraju and Harsha Vardhan Simhadri and Prateek Jain},
title = {Multiple Instance Learning for Efficient Sequential Data Classification on Resource-constrained Devices},
booktitle = {Proceedings of the Thirty-first Annual Conference on Neural Information Processing Systems (NeurIPS)},
year = {2018},
pages = {10976--10987},
note = {slides/DennisPSJ18.pdf},
url = {all_papers/DennisPSJ18.pdf}
}
FastGRNN: A Fast, Accurate, Stable and Tiny Kilobyte Sized Gated Recurrent Neural Network
Aditya Kusupati, Manish Singh, Kush Bhatia, Ashish Kumar, Prateek Jain and Manik Varma,
in Proceedings of the Thirty-first Annual Conference on Neural Information Processing Systems (NeurIPS),
2018.
[BibTeX]
[Abstract]
[URL]
This paper develops the FastRNN and FastGRNN algorithms to address the twin RNN limitations of inaccurate training and inefficient prediction. Previous approaches have improved accuracy at the expense of prediction costs making them infeasible for resource-constrained and real-time applications. Unitary RNNs have increased accuracy somewhat by restricting the range of the state transition matrix's singular values but have also increased the model size as they require a larger number of hidden units to make up for the loss in expressive power. Gated RNNs have obtained state-of-the-art accuracies by adding extra parameters thereby resulting in even larger models. FastRNN addresses these limitations by adding a residual connection that does not constrain the range of the singular values explicitly and has only two extra scalar parameters. FastGRNN then extends the residual connection to a gate by reusing the RNN matrices to match state-of-the-art gated RNN accuracies but with a 2-4x smaller model. Enforcing FastGRNN's matrices to be low-rank, sparse and quantized resulted in accurate models that could be up to 35x smaller than leading gated and unitary RNNs. This allowed FastGRNN to accurately recognize the "Hey Cortana" wakeword with a 1 KB model and to be deployed on severely resource-constrained IoT microcontrollers too tiny to store other RNN models. FastGRNN's code is available online.
@inproceedings{KusupatiSBKJV18,
author = {Aditya Kusupati and Manish Singh and Kush Bhatia and Ashish Kumar and Prateek Jain and Manik Varma},
title = {FastGRNN: A Fast, Accurate, Stable and Tiny Kilobyte Sized Gated Recurrent Neural Network},
booktitle = {Proceedings of the Thirty-first Annual Conference on Neural Information Processing Systems (NeurIPS)},
year = {2018},
pages = {9031--9042},
note = {slides/fastgrnn.pdf},
url = {all_papers/KusupatiSBKJV18.pdf}
}
Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds
Raghav Somani, Chirag Gupta, Prateek Jain and Praneeth Netrapalli,
in Proceedings of the Thirty-first Annual Conference on Neural Information Processing Systems (NeurIPS),
2018.
[BibTeX]
[Abstract]
[URL]
This paper studies the problem of sparse regression where the goal is to learn a sparse vector that best optimizes a given objective function. Under the assumption that the objective function satisfies restricted strong convexity (RSC), we analyze orthogonal matching pursuit (OMP), a greedy algorithm that is used heavily in applications, and obtain support recovery result as well as a tight generalization error bound for OMP. Furthermore, we obtain lower bounds for OMP, showing that both our results on support recovery and generalization error are tight up to logarithmic factors. To the best of our knowledge, these support recovery and generalization bounds are the first such matching upper and lower bounds (up to logarithmic factors) for {\em any} sparse regression algorithm under the RSC assumption.
@inproceedings{SomaniGJN18,
author = {Raghav Somani and Chirag Gupta and Prateek Jain and Praneeth Netrapalli},
title = {Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds},
booktitle = {Proceedings of the Thirty-first Annual Conference on Neural Information Processing Systems (NeurIPS)},
year = {2018},
pages = {10837--10847},
note = {slides/SomaniGJN18.pdf},
url = {all_papers/SomaniGJN18.pdf}
}
Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain and Praneeth Netrapalli,
in Proceedings of the Annual Conference On Learning Theory (COLT),
2018.
[BibTeX]
[Abstract]
[URL]
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer--Monteiro factorization approach for solving SDPs. We show that all approximate local optima are global optima for the penalty formulation of appropriately rank-constrained SDPs as long as the number of constraints scales sub-quadratically with the desired rank of the optimal solution. Our result is based on a simple penalty function formulation of the rank-constrained SDP along with a smoothed analysis to avoid worst-case cost matrices. We particularize our results to two applications, namely, Max-Cut and matrix completion.
@inproceedings{BhojanapalliBJN18,
author = {Srinadh Bhojanapalli and Nicolas Boumal and Prateek Jain and Praneeth Netrapalli},
title = {Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form},
booktitle = {Proceedings of the Annual Conference On Learning Theory (COLT)},
year = {2018},
pages = {3243--3270},
note = {slides/BhojanapalliBJN18.pdf},
url = {all_papers/BhojanapalliBJN18.pdf}
}
Accelerating Stochastic Gradient Descent for Least Squares Regression
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli and Aaron Sidford,
in Proceedings of the Annual Conference On Learning Theory (COLT),
2018.
[BibTeX]
[Abstract]
[URL]
There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation, a notion made precise in d'Aspremont 2008 and Devolder, Glineur, and Nesterov 2014. This work considers these issues for the special case of stochastic approximation for the least squares regression problem, and our main result refutes the conventional wisdom by showing that acceleration can be made robust to statistical errors. In particular, this work introduces an accelerated stochastic gradient method that provably achieves the minimax optimal statistical risk faster than stochastic gradient descent. Critical to the analysis is a sharp characterization of accelerated stochastic gradient descent as a stochastic process. We hope this characterization gives insights towards the broader question of designing simple and effective accelerated stochastic methods for more general convex and non-convex optimization problems.
@inproceedings{JKKNS18,
author = {Prateek Jain and Sham M. Kakade and Rahul Kidambi and Praneeth Netrapalli and Aaron Sidford},
title = {Accelerating Stochastic Gradient Descent for Least Squares Regression},
booktitle = {Proceedings of the Annual Conference On Learning Theory (COLT)},
year = {2018},
pages = {545--604},
note = {slides/JKNNS18.pdf},
url = {all_papers/JKKNS18.pdf}
}
Differentially Private Matrix Completion Revisited
Prateek Jain, Om Dipakbhai Thakkar and Abhradeep Thakurta,
in Proceedings of the 35th International Conference on Machine Learning (ICML),
2018.
[BibTeX]
[Abstract]
[URL]
We study the problem of privacy-preserving collaborative filtering where the objective is to reconstruct the entire users-items preference matrix using a few observed preferences of users for some of the items. Furthermore, the collaborative filtering algorithm should reconstruct the preference matrix while preserving the privacy of each user. We study this problem in the setting of joint differential privacy where each user computes her own preferences for all the items, without violating privacy of other users' preferences. We provide the first provably differentially private algorithm with formal utility guarantees for this problem. Our algorithm is based on the Frank-Wolfe (FW) method, and consistently estimates the underlying preference matrix as long as the number of users $m$ is $\omega(n^{5/4})$, where $n$ is the number of items, and each user provides her preference for at least $\sqrt{n}$ randomly selected items. We also empirically evaluate our FW-based algorithm on a suite of datasets, and show that our method provides nearly same accuracy as the state-of-the-art non-private algorithm, and outperforms the state-of-the-art private algorithm by as much as 30 percent.
@inproceedings{JTT18,
author = {Prateek Jain and Om Dipakbhai Thakkar and Abhradeep Thakurta},
title = {Differentially Private Matrix Completion Revisited},
booktitle = {Proceedings of the 35th International Conference on Machine Learning (ICML)},
year = {2018},
pages = {2220--2229},
note = {slides/JTT18.pdf},
url = {all_papers/JTT18.pdf}
}
Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain and Sumit Gulwani,
in Proceedings of the International Conference on Learning Representations (ICLR),
2018.
[BibTeX]
[Abstract]
[URL]
Synthesizing user-intended programs from a small number of input-output exam-
ples is a challenging problem with several important applications like spreadsheet
manipulation, data wrangling and code refactoring. Existing synthesis systems
either completely rely on deductive logic techniques that are extensively hand-
engineered or on purely statistical models that need massive amounts of data, and in
general fail to provide real-time synthesis on challenging benchmarks. In this work,
we propose Neural Guided Deductive Search (NGDS), a hybrid synthesis technique
that combines the best of both symbolic logic techniques and statistical models.
Thus, it produces programs that satisfy the provided specifications by construction
and generalize well on unseen examples, similar to data-driven systems. Our
technique effectively utilizes the deductive search framework to reduce the learning
problem of the neural component to a simple supervised learning setup. Further,
this allows us to both train on sparingly available real-world data and still leverage
powerful recurrent neural network encoders. We demonstrate the effectiveness
of our method by evaluating on real-world customer scenarios by synthesizing
accurate programs with up to 12× speed-up compared to state-of-the-art systems.
@inproceedings{kalyanMPBJG18,
author = {Ashwin Kalyan and Abhishek Mohta and Oleksandr Polozov and Dhruv Batra and Prateek Jain and Sumit Gulwani},
title = {Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples},
booktitle = {Proceedings of the International Conference on Learning Representations (ICLR)},
year = {2018},
note = {slides/kalyanMPBJG18.pdf},
url = {all_papers/kalyanMPBJG18.pdf}
}
On the insufficiency of existing momentum schemes for Stochastic Optimization
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain and Sham M. Kakade,
in Proceedings of the International Conference on Learning Representations (ICLR),
2018.
[BibTeX]
[Abstract]
[URL]
Momentum based stochastic gradient methods such as heavy ball (HB) and Nesterov's accelerated gradient descent (NAG) method are widely used in practice for training deep networks and other supervised learning models, as they often provide significant improvements over stochastic gradient descent (SGD). Rigorously speaking, fast gradient methods have provable improvements over gradient descent only for the deterministic case, where the gradients are exact. In the stochastic case, the popular explanations for their wide applicability is that when these fast gradient methods are applied in the stochastic case, they partially mimic their exact gradient counterparts, resulting in some practical gain. This work provides a counterpoint to this belief by proving that there exist simple problem instances where these methods cannot outperform SGD despite the best setting of its parameters. These negative problem instances are, in an informal sense, generic; they do not look like carefully constructed pathological instances. These results suggest (along with empirical evidence) that HB or NAG's practical performance gains are a by-product of minibatching.
Furthermore, this work provides a viable (and provable) alternative, which, on the same set of problem instances, significantly improves over HB, NAG, and SGD's performance. This algorithm, referred to as Accelerated Stochastic Gradient Descent (ASGD), is a simple to implement stochastic algorithm, based on a relatively less popular variant of Nesterov's Acceleration. Extensive empirical results in this paper show that ASGD has performance gains over HB, NAG, and SGD. The code for implementing the ASGD Algorithm can be found at https://github.com/rahulkidambi/AccSGD.
@inproceedings{KidambiNJK18,
author = {Rahul Kidambi and Praneeth Netrapalli and Prateek Jain and Sham M. Kakade},
title = {On the insufficiency of existing momentum schemes for Stochastic Optimization},
booktitle = {Proceedings of the International Conference on Learning Representations (ICLR)},
year = {2018},
note = {slides/KidambiNJK18.pdf},
url = {all_papers/KidambiNJK18.pdf}
}
FlashProfile: a framework for synthesizing data profiles
Saswat Padhi, Prateek Jain, Daniel Perelman, Oleksandr Polozov, Sumit Gulwani and Todd D. Millstein,
in Proceedings of Object-Oriented Programming, Systems, Languages and Applications (OOPSLA),
2018.
[BibTeX]
[Abstract]
[URL]
We address the problem of learning a syntactic profile for a collection of strings, i.e. a set of regex-like patterns
that succinctly describe the syntactic variations in the strings. Real-world datasets, typically curated from
multiple sources, often contain data in various syntactic formats. Thus, any data processing task is preceded
by the critical step of data format identification. However, manual inspection of data to identify the different
formats is infeasible in standard big-data scenarios.
Prior techniques are restricted to a small set of pre-defined patterns (e.g. digits, letters, words, etc.), and
provide no control over granularity of profiles. We define syntactic profiling as a problem of clustering strings
based on syntactic similarity, followed by identifying patterns that succinctly describe each cluster. We present
a technique for synthesizing such profiles over a given language of patterns, that also allows for interactive
refinement by requesting a desired number of clusters.
Using a state-of-the-art inductive synthesis framework, PROSE, we have implemented our technique as
FlashProfile. Across 153 tasks over 75 large real datasets, we observe a median profiling time of only 0.7 s.
Furthermore, we show that access to syntactic profiles may allow for more accurate synthesis of programs, i.e.
using fewer examples, in programming-by-example (PBE) workflows such as Flash Fill.
@inproceedings{PadhiJPPGM18,
author = {Saswat Padhi and Prateek Jain and Daniel Perelman and Oleksandr Polozov and Sumit Gulwani and Todd D. Millstein},
title = {FlashProfile: a framework for synthesizing data profiles},
booktitle = {Proceedings of Object-Oriented Programming, Systems, Languages and Applications (OOPSLA)},
year = {2018},
pages = {150:1--150:28},
note = {slides/PadhiJPPGM18.pdf},
url = {all_papers/PadhiJPPGM18.pdf},
doi = {https://doi.org/10.1145/3276520}
}
A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla and Aaron Sidford,
in Proceedings of the Thirty-seventh IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS),
2017.
[BibTeX]
[Abstract]
[URL]
This work provides a simplified proof of the statistical minimax optimality of (iterate averaged) stochastic gradient descent (SGD), for the special case of least squares. This result is obtained by analyzing SGD as a stochastic process and by sharply characterizing the stationary covariance matrix of this process. The finite rate optimality characterization captures the constant factors and addresses model mis-specification.
@inproceedings{JainKKNPS17,
author = {Prateek Jain and Sham M. Kakade and Rahul Kidambi and Praneeth Netrapalli and Venkata Krishna Pillutla and Aaron Sidford},
title = {A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)},
booktitle = {Proceedings of the Thirty-seventh IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)},
year = {2017},
pages = {2:1--2:10},
url = {all_papers/JKKNPS17.pdf}
}
Consistent Robust Regression
Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban and Purushottam Kar,
in Proceedings of the 30th Annual Conference on Advances in Neural Information Processing Systems (NIPS),
2017.
[BibTeX]
[Abstract]
[URL]
We present the first efficient and provably consistent estimator for the robust regression problem. The area of robust learning and optimization has generated a significant amount of interest in the learning and statistics communities in recent years owing to its applicability in scenarios with corrupted data, as well as in handling model mis-specifications. In particular, special interest has been devoted to the fundamental problem of robust linear regression where estimators that can tolerate corruption in up to a constant fraction of the response variables are widely studied. Surprisingly however, to this date, we are not aware of a polynomial time estimator that offers a consistent estimate in the presence of dense, unbounded corruptions. In this work we present such an estimator, called CRR. This solves an open problem put forward in the work of (Bhatia et al, 2015). Our consistency analysis requires a novel two-stage proof technique involving a careful analysis of the stability of ordered lists which may be of independent interest. We show that CRR not only offers consistent estimates, but is empirically far superior to several other recently proposed algorithms for the robust regression problem, including extended Lasso and the TORRENT algorithm. In comparison, CRR offers comparable or better model recovery but with runtimes that are faster by an order of magnitude.
@inproceedings{BhatiaJKK17,
author = {Kush Bhatia and Prateek Jain and Parameswaran Kamalaruban and Purushottam Kar},
title = {Consistent Robust Regression},
booktitle = {Proceedings of the 30th Annual Conference on Advances in Neural Information Processing Systems (NIPS)},
year = {2017},
pages = {2107--2116},
url = {all_papers/BhatiaJKK17.pdf}
}
Learning Mixture of Gaussians with Streaming Data
Aditi Raghunathan, Prateek Jain and Ravishankar Krishnaswamy,
in Proceedings of the 30th Annual Conference on Advances in Neural Information Processing Systems (NIPS),
2017.
[BibTeX]
[URL]
@inproceedings{RaghunathanJK17,
author = {Aditi Raghunathan and Prateek Jain and Ravishankar Krishnaswamy},
title = {Learning Mixture of Gaussians with Streaming Data},
booktitle = {Proceedings of the 30th Annual Conference on Advances in Neural Information Processing Systems (NIPS)},
year = {2017},
pages = {6608--6617},
url = {all_papers/RaghunathanJK17.pdf}
}
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]
Programming by Examples (PBE) involves synthesizing intended
programs in an underlying domain-specific language from
example-based specifications. PBE systems are already revolutionizing
the application domain of data wrangling and are set to significantly
impact several other domains including code refactoring. There are three key components in a PBE system.
(i) A search algorithm that can efficiently search for programs that are consistent with the examples
provided by the user.
We leverage a divide-and-conquer-based deductive search paradigm that
inductively reduces the problem of synthesizing a program expression of a certain kind that
satisfies a given specification into sub-problems that refer to
sub-expressions or sub-specifications.
(ii) Program ranking techniques to pick an intended program from among the many that satisfy the examples
provided by the user. We leverage features of the program structure as well of the outputs generated by the program on test inputs.
(iii) User interaction models to facilitate usability and debuggability.
We leverage active-learning techniques based on clustering inputs and synthesizing
multiple programs. Each of these PBE components leverage both symbolic reasoning and heuristics.
We make the case for synthesizing these heuristics from
training data using appropriate machine learning methods.
This can not only lead to better heuristics, but can also enable easier development,
maintenance, and even personalization of a PBE system.
@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 = {https://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]
[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 = {https://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 = {https://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]
We study the problem of Robust Least Squares Regression (RLSR) where several response variables can be adversarially corrupted. More specifically, for a data matrix $X\in \R^{p\times n}$ and an underlying model $\bto$, the response vector is generated as $\y=X^T\bto+\b$ where $\b\in \R^n$ is the corruption vector supported over at most $C\cdot n$ coordinates. Existing exact recovery results for RLSR focus solely on $L_1$-penalty based convex formulations and impose relatively strict model assumptions such as requiring the corruptions $\b$ to be selected independently of $X$.
In this work, we study a simple hard-thresholding algorithm called \alg which, under mild conditions on $X$, can recover $\bto$ exactly even if $\b$ corrupts the response variables in an \emph{adversarial} manner, i.e. both the support and entries of $\b$ are selected adversarially after observing $X$ and $\bto$. Our results hold under \emph{deterministic} assumptions which are satisfied if $X$ is sampled from any sub-Gaussian distribution. Finally unlike existing results that apply only to a fixed $\bto$, generated independently of $X$, our results are \emph{universal} and hold for any $\bto\in \R^p$.
Next, we propose gradient descent-based extensions of \alg that can scale efficiently to large scale problems, such as high dimensional sparse recovery, and prove similar recovery guarantees for these extensions. Empirically we find \alg, and more so its extensions, offering significantly faster recovery than the state-of-the-art $L_1$ solvers. Empirically we find \alg, and more so its extensions, offering significantly faster recovery than the state-of-the-art $L_1$ solvers. For instance, even on moderate-sized datasets (with $p=50K$) with around $40\%$ corrupted responses, a variant of our proposed method called \alg-HYB is more than $20\times$ faster than the best $L_1$ solver.
@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]
The objective in extreme multi-label learning is to train a classifier that can automatically
tag a novel data point with the most relevant subset of labels from an
extremely large label set. Embedding based approaches attempt to make training
and prediction tractable by assuming that the training label matrix is low-rank and
reducing the effective number of labels by projecting the high dimensional label
vectors onto a low dimensional linear subspace. Still, leading embedding approaches
have been unable to deliver high prediction accuracies, or scale to large
problems as the low rank assumption is violated in most real world applications.
In this paper we develop the SLEEC classifier to address both limitations. The
main technical contribution in SLEEC is a formulation for learning a small ensemble
of local distance preserving embeddings which can accurately predict infrequently
occurring (tail) labels. This allows SLEEC to break free of the traditional
low-rank assumption and boost classification accuracy by learning embeddings
which preserve pairwise distances between only the nearest label vectors.
We conducted extensive experiments on several real-world, as well as benchmark
data sets and compared our method against state-of-the-art methods for extreme
multi-label classification. Experiments reveal that SLEEC can make significantly
more accurate predictions then the state-of-the-art methods including both
embedding-based (by as much as 35\%) as well as tree-based (by as much as 6\%)
methods. SLEEC can also scale efficiently to data sets with a million labels which
are beyond the pale of leading embedding methods.
@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]
Modern prediction problems arising in multilabel learning and learning to rank pose unique challenges to the classical theory of supervised learning. These problems have large prediction and label spaces of a combinatorial nature and involve sophisticated loss functions. We offer a general framework to derive mistake driven online algorithms and associated loss bounds. The key ingredients in our framework are a general loss function, a general vector space representation of predictions, and a notion of margin with respect to a general norm. Our general algorithm, \algoname, yields the perceptron algorithm and its variants when instantiated on classic problems such as binary classification, multiclass classification, ordinal regression, and multilabel classification. For multilabel ranking and subset ranking, we derive novel algorithms, notions of margins, and loss bounds. A simulation study confirms the behavior predicted by our bounds and demonstrates the flexibility of the design choices in our framework.
@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]
In regression problems involving vector-valued outputs (or equivalently, multiple responses), it is well known that the maximum likelihood estimator (MLE), which takes noise covariance structure into account, can be significantly more accurate than the ordinary least squares (OLS) estimator. However, existing literature compares OLS and MLE in terms of their asymptotic, not finite sample, guarantees. More crucially, computing the MLE in general requires solving a non-convex optimization problem and is not known to be efficiently solvable. We provide finite sample upper and lower bounds on the estimation error of OLS and MLE, in two popular models: a) Pooled model, b) Seemingly Unrelated Regression (SUR) model. We provide precise instances where the MLE is significantly more accurate than OLS. Furthermore, for both models, we show that the output of a computationally efficient alternating minimization procedure enjoys the same performance guarantee as MLE, up to universal constants. Finally, we show that for high-dimensional settings as well, the alternating minimization procedure leads to significantly more accurate solutions than the corresponding OLS solutions but with error bound that depends only logarithmically on the data dimensionality.
@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]
The problem of maximizing precision at top, also dubbed Precision@k, finds relevance in myriad learning applications such as ranking, multi-label classification, and learning with severe label imbalances. Despite its popularity, Precision@k is not known to have a surrogate function that upper bounds it. Similarly, notions of consistency under certain noise/margin conditions are also not explored.
In this work, we devise two novel convex surrogate functions for Precision@k, that upper bound it and are motivated by certain natural notions of margin for Precision@k performance measure. We also provide two novel perceptron algorithms for Precision@k that have interesting mistake bounds w.r.t. the proposed surrogates.
Moreover, we devise scalable stochastic gradient descent style methods for our proposed surrogates and prove convergence bounds for the same. Our convergence bounds rely on a strong uniform convergence bound for Precsion@k and crucially exploit the structural simplicity of Precision@k. We conclude with experimental evidence of superiority of our surrogates when compared to the structural SVM surrogate \cite{Joachims05}, a state-of-the-art approach to optimize Precision@k.
@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]
Modern classification problems frequently present mild to severe label imbalance as well as specific requirements on classification characteristics, and require optimizing performance measures that are non-decomposable over the dataset, such as F-measure. Such measures have spurred much interest and pose specific challenges to learning algorithms since their non-additive nature precludes a direct application of well-studied large scale optimization methods such as stochastic gradient descent.
In this paper we reveal that for two large families of performance measures that can be expressed as functions of true positive/negative rates, it is indeed possible to implement point stochastic updates. The families we consider are concave and pseudo-linear functions of TPR, TNR which cover several popularly used performance measures such as F-measure, G-mean and H-mean.
Our core contribution is an adaptive linearization scheme for these families, using which we develop optimization techniques that enable truly point-based stochastic updates. For concave performance measures we propose \pdsgd, a stochastic primal dual solver; for pseudo-linear measures we propose \amsgd, a stochastic alternate maximization procedure. Both methods have crisp convergence guarantees, demonstrate significant speedups over existing methods - often by an order of magnitude or more, and give similar or more accurate predictions on test data.
@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]
Matrix completion is the problem of recovering a low rank matrix by observing a small fraction of its entries. A series of recent works \citep{Keshavan2012,JainNS2013,Hardt2013} have proposed fast non-convex optimization based iterative algorithms to solve this problem. However, the sample complexity in all these results is sub-optimal in its dependence on the rank, condition number and the desired accuracy.
In this paper, we present a fast iterative algorithm that solves the matrix completion problem by observing $\order{nr^5 \log^3 n}$ entries, which is independent of the condition number and the desired accuracy. The run time of our algorithm is $\order{nr^7\log^3 n\log 1/\epsilon}$ which is near linear in the dimension of the matrix. To the best of our knowledge, this is the first near linear time algorithm for exact matrix completion with finite sample complexity (i.e. independent of $\epsilon$).
Our algorithm is based on a well known projected gradient descent method, where the projection is onto the (non-convex) set of low rank matrices. There are two key ideas in our result: 1) our argument is based on a $\ell_\infty$ norm potential function (as opposed to the spectral norm) and provides a novel way to obtain perturbation bounds for it. 2) we prove and use a natural extension of the Davis-Kahan theorem to obtain perturbation bounds on the best low rank approximation of matrices with good eigen gap. Both of these ideas may be of independent interest.
@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]
In this work, we propose a new randomized algorithm for computing a low-rank approximation to a given matrix. Taking an approach different from existing literature, our method first involves a specific biased sampling, with an element being chosen based on the leverage scores of its row and column, and then involves weighted alternating minimization over the factored form of the intended low-rank matrix, to minimize error only on these samples. Our method can leverage input sparsity, yet produce approximations in {\em spectral} (as opposed to the weaker Frobenius) norm; this combines the best aspects of otherwise disparate current results, but with a dependence on the condition number $\kappa = \sigma_1/\sigma_r$. In particular we require $O(nnz(M) + \frac{n\kappa^2 r^5}{\epsilon^2} )$ computations to generate a rank-$r$ approximation to $M$ in spectral norm. In contrast, the best existing method requires $O(nnz(M)+ \frac{nr^2}{\epsilon^4})$ time to compute an approximation in Frobenius norm. Besides the tightness in spectral norm, we have a better dependence on the error $\epsilon$. Our method is naturally and highly parallelizable.
Our new approach enables two extensions that are interesting on their own. The first is a new method to directly compute a low-rank approximation (in efficient factored form) to the product of two given matrices; it computes a small random set of entries of the product, and then executes weighted alternating minimization (as before) on these. The sampling strategy is different because now we cannot access leverage scores of the product matrix (but instead have to work with input matrices). The second extension is an improved algorithm with smaller communication complexity for the distributed PCA setting (where each server has small set of rows of the matrix, and want to compute low rank approximation with small amount of communication with other servers).
@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 = {https://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]
Modern applications in sensitive domains such as biometrics and medicine frequently require the use of \emph{non-decomposable} loss functions such as precision$@k$, F-measure etc. Compared to point loss functions such as hinge-loss, these offer much more fine grained control over prediction, but at the same time present novel challenges in terms of algorithm design and analysis. In this work we initiate a study of online learning techniques for such non-decomposable loss functions with an aim to enable incremental learning as well as design scalable solvers for batch problems. To this end, we propose an online learning framework for such loss functions. Our model enjoys several nice properties, chief amongst them being the existence of efficient online learning algorithms with sublinear regret and online to batch conversion bounds. Our model is a provable extension of existing online learning models for point loss functions. We instantiate two popular losses, \preck and pAUC, in our model and prove sublinear regret bounds for both of them. Our proofs require a novel structural lemma over ranked lists which may be of independent interest. We then develop scalable stochastic gradient descent solvers for non-decomposable loss functions. We show that for a large family of loss functions satisfying a certain uniform convergence property (that includes \preck, pAUC, and F-measure), our methods provably converge to the empirical risk minimizer. Such uniform convergence results were not known for these losses and we establish these using novel proof techniques. We then use extensive experimentation on real life and benchmark datasets to establish that our method can be orders of magnitude faster than a recently proposed cutting plane method.
@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]
The problem of low-rank matrix completion has recently generated a lot of interest leading to several results that offer exact solutions to the problem. However, in order to do so, these methods make assumptions that can be quite restrictive in practice. More specifically, the methods assume that: a) the observed indices are sampled uniformly at random, and b) for every new matrix, the observed indices are sampled \emph{afresh}. In this work, we address these issues by providing a universal recovery guarantee for matrix completion that works for a variety of sampling schemes. In particular, we show that if the set of sampled indices come from the edges of a bipartite graph with large spectral gap (i.e. gap between the first and the second singular value), then the nuclear norm minimization based method exactly recovers all low-rank matrices that satisfy certain incoherence properties.
Moreover, we also show that under certain stricter incoherence conditions, $O(nr^2)$ uniformly sampled entries are enough to recover any rank-$r$ $n\times n$ matrix, in contrast to the $O(nr\log n)$ sample complexity required by other matrix completion algorithms as well as existing analyses of the nuclear norm method.
@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]
The multi-label classification problem has generated significant interest in recent Years. However, existing approaches do not adequately address two key challenges: (a) scaling up to problems with a large number (say millions) of labels, and (b) handling data with missing labels. In this paper, we directly address both these problems by studying the multi-label problem in a generic empirical risk minimization (ERM) framework. Our framework, despite being simple, is surprisingly able to encompass several recent label-compression based methods which can be derived as special cases of our method. To optimize the ERM problem, we develop techniques that exploit the structure of specific loss functions - such as the squared loss function - to obtain efficient algorithms. We further show that our learning framework admits excess risk bounds even in the presence of missing labels. Our bounds are tight and demonstrate better generalization performance for low-rank promoting trace-norm regularization when compared to (rank insensitive) Frobenius norm regularization. Finally, we present extensive empirical results on a variety of benchmark datasets and show that our methods perform significantly better than existing label compression based methods and can scale up to very large datasets such as a Wikipedia dataset that has more than 200,000 labels.
@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]
We consider the problem of learning sparsely used overcomplete dictionaries, where each observation
is a sparse combination of elements from an unknown overcomplete dictionary. We establish
exact recovery when the dictionary elements are mutually incoherent. Our method consists of a
clustering-based initialization step, which provides an approximate estimate of the true dictionary
with guaranteed accuracy. This estimate is then refined via an iterative algorithm with the following
alternating steps: 1) estimation of the dictionary coefficients for each observation through $\ell_1$
minimization, given the dictionary estimate, and 2) estimation of the dictionary elements through
least squares, given the coefficient estimates. We establish that, under a set of sufficient conditions,
our method converges at a linear rate to the true dictionary as well as the true coefficients for each
observation.
@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]
We study the problem of learning a distribution from samples, when the underlying distribution is a mixture of product distributions over discrete domains. This problem is motivated by several practical applications such as crowdsourcing, recommendation systems, and learning Boolean functions. The existing solutions either heavily rely on the fact that the number of mixtures is finite or have sample/time complexity that is exponential in the number of mixtures. In this paper, we introduce a polynomial time/sample complexity method for learning a mixture of $r$ discrete product distributions over $\{1, 2, \dots, \ell\}^n$, for general $\ell$ and $r$. We show that our approach is consistent and further provide finite sample guarantees.
We use recently developed techniques from tensor decompositions for moment matching. A crucial step in these approaches is to construct certain tensors with low-rank spectral decompositions.These tensors are typically estimated from the sample moments. The main challenge in learning mixtures of discrete product distributions is that the corresponding low-rank tensors cannot be obtained directly from the sample moments. Instead, we need to estimate a low-rank matrix using only off-diagonal entries, and estimate a tensor using a few linear measurements. We give an alternating minimization based method to estimate the low-rank matrix, and formulate the tensor estimation problem as a least-squares problem.
@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]
We consider streaming, one-pass principal component analysis (PCA), in the high-dimensional regime, with limited memory. Here, $p$-dimensional samples are presented sequentially, and the goal is to produce the $k$-dimensional subspace that best approximates these points. Standard algorithms require $O(p^2)$ memory; meanwhile no algorithm can do better than $O(kp)$ memory, since this is what the output itself requires. Memory (or storage) complexity is most meaningful when understood in the context of computational and sample complexity. Sample complexity for high-dimensional PCA is typically studied in the setting of the {\em spiked covariance model}, where $p$-dimensional points are generated from a population covariance equal to the identity (white noise) plus a low-dimensional perturbation (the spike) which is the signal to be recovered. It is now well-understood that the spike can be recovered when the number of samples, $n$, scales proportionally with the dimension, $p$. Yet, all algorithms that provably achieve this, have memory complexity $O(p^2)$. Meanwhile, algorithms with memory-complexity $O(kp)$ do not have provable bounds on sample complexity comparable to $p$. We present an algorithm that achieves both: it uses $O(kp)$ memory (meaning storage of any kind) and is able to compute the $k$-dimensional spike with $O(p \log p)$ sample-complexity -- the first algorithm of its kind. While our theoretical analysis focuses on the spiked covariance model, our simulations show that our algorithm is successful on much more general models for the data.
@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]
Phase retrieval problems involve solving linear equations, but with missing sign (or phase, for complex numbers).
Over the last two decades, a popular generic empirical approach to the many variants of this problem has been one of alternating minimization;
i.e. alternating between estimating the missing phase information, and the candidate solution. In this paper, we show that a simple alternating
minimization algorithm geometrically converges to the solution of one such problem -- finding a vector $\vecfont{x}$ from $\vecfont{y},\mat{A}$,
where $\vecfont{y} = |\mat{A}^T\vecfont{x}|$ and $|\vecfont{z}|$ denotes a vector of element-wise magnitudes of $\vecfont{z}$ -- under the assumption that $\mat{A}$ is Gaussian.
Empirically, our algorithm performs similar to recently proposed convex techniques for this variant (which are based on ``lifting" to a convex matrix problem) in sample complexity and robustness to noise.
However, our algorithm is much more efficient and can scale to large problems.
Analytically, we show geometric convergence to the solution, and sample complexity that is off by log factors from obvious lower bounds.
We also establish close to optimal scaling for the case when the unknown vector is sparse. Our work represents the only known
theoretical guarantee for alternating minimization for any variant of phase retrieval problems in the non-convex setting.
@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]
In this paper, we study the generalization properties of online learning based
stochastic methods for supervised learning problems where the loss function is
dependent on more than one training sample (e.g., metric learning, ranking). We
present a generic decoupling technique that enables us to provide Rademacher
complexity-based generalization error bounds. Our bounds are in general tighter
than those obtained by \citet{online-batch-pairwise} for the same problem. Using
our decoupling technique, we are further able to obtain fast convergence rates
for strongly convex pairwise loss functions. We are also able to analyze a class
of memory efficient online learning algorithms for pairwise learning problems that use
only a bounded subset of past training samples to update the hypothesis at each
step. Finally, in order to complement our generalization bounds, we propose a
novel memory efficient online learning algorithm for higher order learning
problems with bounded regret guarantees.
@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 = {https://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]
A typical problem for a search engine (hosting sponsored search
service) is to provide the advertisers with a forecast of the number
of impressions his/her ad is likely to obtain for a given bid.
Accurate forecasts have high business value, since they enable advertisers
to select bids that lead to better returns on their investment.
They also play an important role in services such as automatic
campaign optimization. Despite its importance the problem
has remained relatively unexplored in literature. Existing methods
typically overfit to the training data, leading to inconsistent performance.
Furthermore, some of the existing methods cannot provide
predictions for new ads, i.e., for ads that are not present in
the logs. In this paper, we develop a generative model based approach
that addresses these drawbacks. We design a Bayes net to
capture inter-dependencies between the query traffic features and
the competitors in an auction. Furthermore, we account for variability
in the volume of query traffic by using a dynamic linear
model. Finally, we implement our approach on a production grade
MapReduce framework and conduct extensive large scale experiments
on substantial volumes of sponsored search data from Bing.
Our experimental results demonstrate significant advantages over
existing methods as measured using several accuracy/error criteria,
improved ability to provide estimates for new ads and more consistent
performance with smaller variance in accuracies. Our method
can also be adapted to several other related forecasting problems
such as predicting average position of ads or the number of clicks
under budget constraints.
@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 = {https://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]
In this paper, we focus on the problem of private database
release in the interactive setting: a trusted database curator receives
queries in an online manner for which it needs to respond with accurate
but privacy preserving answers. To this end, we generalize the IDC (Iter-
ative Database Construction) framework of [HR10,GRU11] that maintains a dif-
ferentially private artificial dataset and answers incoming linear queries
using the artificial dataset. In particular, we formulate a generic IDC
framework based on the Mirror Descent algorithm, a popular convex
optimization algorithm. We then present two concrete applications,
namely, cut queries over a bipartite graph and linear queries over low-
rank matrices, and provide significantly tighter error bounds than the
ones by [HR10, GRU11].
@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 = {https://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 = {https://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 = {https://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 = {https://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 = {https://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 = {https://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 = {https://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 = {https://doi.org/10.1145/1273496.1273523}
}
