Selected Publications

Machine Learning (Foundations, Applications, and Connections to Other Areas)
Algorithm Design and Analysis
Algorithmic Game Theory
Books and Theses

Data Driven Algorithm Design.

• How much data is sufficient to learn high-performing algorithms?
  With Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. Arxiv 2019.
  

• Data-Driven Algorithm Design.
  Book Chapter in Beyond Worst Case Analysis of Algorithms, T. Roughgarden (Ed). Cambridge University Press.
  

• Learning to Link.
  With Travis Dick and Manuel Lang. ICLR 2020.
  

• Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization.
  With Travis Dick and Ellen Vitercik. FOCS 2018.
  

• Data-Driven Clustering via Parameterized Lloyd's Families.
  With Travis Dick and Colin White. NeurIPS 2018.
  

• Learning to Branch.
  With Travis Dick, Tuomas Sandholm, and Ellen Vitercik. ICML 2018.
  

• Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems.
  With Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. COLT 2017.

Analysis of the Algorithms Beyond the Worst Case.

• k-Center Clustering Under Perturbation Resilience. With Nika Haghtalab and Colin White. Transactions of Algorithms Journal (to appear).
  See also earlier version in ICALP 2016.

• Clustering under Perturbation Resilience. With Yingyu Liang. SIAM Journal of Computing 2016.
  
  See also an earlier version in ICALP 2012.

• Finding Low Error Clusterings. With Mark Braverman. COLT 2009.

• Agnostic Clustering. With Heiko Roeglin and Shang-Hua Teng. ALT 2009.

• Better Guarantees for Sparsest Cut Clustering. Open Problem. COLT 2009.
  

• Approximate Clustering without the Approximation. With Avrim Blum and Anupam Gupta. SODA 2009.
  
  Extended version appears under the title Clustering under Approximation Stability in Journal of the ACM 2013.

Learning Representations and Label Efficient Learning (for Multi-task, Life-Long Learning).

• Adaptive Gradient-Based Meta-Learning Method. With Mikhail Khodak and Ameet Talwalkar. NeurIPS 2019.

• Provable Guarantees for Gradient-Based Meta-Learning. With Mikhail Khodak and Ameet Talwalkar. ICML 2019.

• Risk Bounds for Transferring Representations With and Without Fine-Tuning. With Daniel McNamara. ICML 2017.
  See also the ICLR Workshop Track version Performance Guarantees for Transferring Representations.

• Label Efficient Learning by Exploiting Multi-class Output Codes. With Travis Dick and Yishay Mansour. AAAI 2017.

• Lifelong Learning in Costly Feature Spaces. With Avrim Blum and Vaishnavh Nagarajan. ALT 2017.

• Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling. With Hongyang Zhang. NIPS 2016.

• Efficient Representations for Life-Long Learning and Autoencoding. With Avrim Blum and Santosh Vempala. COLT 2015.
  

• Exploiting Ontology Structures and Unlabeled Data for Learning. With Avrim Blum and Yishay Mansour. ICML 2013.
  

Distributed Learning.

• Robust Communication-Optimal Distributed Clustering Algorithms.
  With Pranjal Awasthi, Ainesh Bakshi, Colin White, and David Woodruff. ICALP 2019.

• Data Driven Resource Allocation for Distributed Learning.
  With Travis Dick, Mu Li, Venkata Krishna Pillutla, Colin White, and Alex Smola. AISTATS 2017.

• Communication Efficient Distributed Kernel Principal Component Analysis. With Yingyu Liang, Le Song, David Woodruff, and Bo Xie. KDD 2016.

• Communication Efficient Distributed Agnostic Boosting. With Shang-Tse Chen and Polo Chau. AISTATS 2016.

• Distributed Frank-Wolfe Algorithm: A Unified Framework for Communication-Efficient Sparse Learning.
  With Aurelien Bellet, Yingyu Liang, Alireza Bagheri Garakani, and Fei Sha. SIAM International Conference on Data Mining 2015.
  
  An earlier version appeared in the ICML 2014 workshop on New Learning Frameworks and Models for Big Data.

• Improved Distributed Principal Component Analysis. With With Vandana Kanchanapally, Yingyu Liang, and David Woodruff. NIPS 2014.
  
  An earlier version (Distributed PCA and k-Means Clustering) appeared in the NIPS 2013 Workshop on Big Learning.

• Distributed k-Means and k-Median Clustering on General Topologies. With Steven Ehrlich and Yingyu Liang. NIPS 2013. See arXiv:1306.0604 version.
  

• Distributed Learning, Communication Complexity, and Privacy. With Avrim Blum, Shai Fine, and Yishay Mansour. COLT 2012.
  Winner of the Runner Up Best Paper Award.
  
  

Learning Theoretic Lens on Submodularity (with Applications to Algorithmic Game Theory, Economics, and Social Networks).

• Scalable Influence Maximization for Multiple Products in Continuous -Time Diffusion Networks.
  With Nan Du, Yingyu Liang, Manuel Gomez-Rodriguez, Hongyuan Zha, and Le Song. Journal of Machine Learning Research 2017.
  Earlier version: Continuous-Time Influence Maximization for Multiple Items.
  

• Learning Combinatorial Functions from Pairwise Comparisons. With Ellen Vitercik and Colin White. COLT 2016.

• Learning Cooperative Games. With Ariel D. Procaccia and Yair Zick. IJCAI 2015.

• Learning Time-Varying Coverage Functions. With Nan Du, Yingyu Liang, and Le Song. NIPS 2014.

• Influence Function Learning in Information Diffusion Networks. With Nan Du, Yingyu Liang, and Le Song. ICML 2014.

• Learning Symmetric Non-monotone Submodular Functions. With Nick Harvey and Satoru Iwata. NIPS Workshop on Discrete Optimization in Machine Learning (DISCML) 2012.

• Learning Valuation Functions. With Florin Constantin, Satoru Iwata, and Lei Wang. COLT 2012.

• Learning Submodular Functions. With Nick Harvey. STOC 2011.
  
  Also a NECTAR track paper at ECML-PKDD 2012 (for "significant machine learning results"). See short abstract.
  
  See also Submodular Functions: Learnability, Structure, and Optimization (expanded version, 2012).

Supervised Learning. Noise Tolerant Algorithms.

• The Power of Localization for Efficiently Learning Linear Separators with Noise. With Pranjal Awasthi and Phil Long. Journal of the ACM 2017.
  
  See also an earlier version in STOC 2014.

• Efficient algorithms for learning and 1-bit compressed sensing under asymmetric noise. With Pranjal Awasthi, Nika Haghtalab, and Hongyang Zhang. COLT 2016.

• Efficient Learning of Linear Separators under Bounded Noise. With Pranjal Awasthi, Nika Haghtalab, and Ruth Urner. COLT 2015.

• A New Perspective on Learning Linear Separators with Large L_∞ L₁ Margins. With Chris Berlind. AISTATS 2014.
  
  

Interactive Learning

• Local Algorithms for Interactive Clustering. With Pranjal Awasthi and Konstantin Voevodski. Journal of Machine Learning Research 2017.
  
  See also an earlier version in ICML 2014.

• Active Learning Algorithms for Graphical Model Selection. With Gautam Dasarathy, Aarti Singh, and J. H. Park. AISTATS 2016.

• Active Learning. With Ruth Urner. Encyclopedia of Algorithms 2014.

• Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy. With Vitaly Feldman. Algorithmica 2014. Special issue on Learning Theory (Invited).
  
  See also an earlier version in NIPS 2013.
  

• Active and passive learning of linear separators under log-concave distributions. With Phil Long. COLT 2013.
  
  Also presented in the 51st Annual Allerton Conference on Communication, Control, and Computing.

• Robust Interactive Learning. With Steve Hanneke. COLT 2012.

• The True Sample Complexity of Active Learning. With Steve Hanneke and Jennifer Wortman. COLT 2008.
  Winner of the Mark Fulk Best Student Paper Award.
  
  An extended version appears in Machine Learning Journal, 80(2-3):111 --139, 2010. Special Issue for COLT 2008 (Invited).
  

• Asymptotic Active Learning. With Eyal Even-Dar, Steve Hanneke, Michael Kearns, Yishay Mansour, and Jennifer Wortman. NIPS 2007 Workshop on Principles of Learning Design Problem.
  

• Margin Based Active Learning. With Andrei Broder and Tong Zhang. COLT 2007.
  

• Agnostic Active Learning. With Alina Beygelzimer and John Langford. Journal of Computer and System Sciences, 75(1):78--89, 2009. Special issue on Learning Theory for best papers in 2006 (Invited).
  
  See also an earlier version in ICML 2006.

• Clustering with Interactive Feedback. With Avrim Blum. ALT 2008.
  

Clustering, Unsupervised Learning.

• Differentially Private Clustering in High-Dimensional Euclidean Spaces. With Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. ICML 2017.

• Center Based Clustering: A Foundational Perspective. With Pranjal Awasthi. Book Chapter in Handbook of Cluster Analysis 2015.

• Robust Hierarchical Clustering. Yingyu Liang and Pramod Gupta. Journal of Machine Learning Research 2014. .
  
  See also an earlier version (joint with Pramod Gupta) in COLT 2010.

• Modeling and Detecting Community Hierarchies. With Yingyu Liang. SIMBAD 2013.

• Finding Endogenously Formed Communities. With Christian Borgs, Mark Braverman, Jennifer Chayes, and Shang-Hua Teng. SODA 2013.

• Min-Sum Clustering of Protein Sequences with Limited Distance Information. With Heiko Roeglin, ShangHua Teng, Konstantin Voevodski, and Yu Xia. SIMBAD 2011.

• Efficient Clustering with Limited Distance Information. With Heiko Roeglin, ShangHua Teng, Konstantin Voevodski, and Yu Xia. UAI 2010.
  
  An extended version appears under the title Active Clustering of Biological Sequences in the Journal of Machine Learning Research 2012.

• A Discriminative Framework for Clustering via Similarity Functions. With Avrim Blum and Santosh Vempala. STOC 2008.
  
  See also an extended version (2009).

Property Testing and Learning

• Testing Matrix Rank Optimally. With Yi Li, David P. Woodruff, Hongyang Zhang. SODA 2019.

• Active Property Testing. With Eric Blais, Avrim Blum, and Liu Yang. FOCS 2012.

Learning with Kernels and More General Similarity Functions

• Scalable Kernel Methods via Doubly Stochastic Gradients. With Bo Dai, Xie Dai, Niao He, Yingyu Liang, Anant Raj, and Le Song. NIPS 2014.

• Improved Guarantees for Learning via Similarity Functions. With Avrim Blum and Nathan Srebro. COLT 2008.
  A related note on Similarity-Based Theoretical Foundation for Sparse Parzen Window Prediction. With Avrim Blum and Nathan Srebro. ICML/UAI/COLT 2008 Workshop on Sparse Optimization and Variable Selection.

• On a Theory of Learning with Similarity Functions. With Avrim Blum. ICML 2006.
  
  Combined with subsequent paper by Nathan Srebro in journal version, Machine Learning Journal, 72(1-2):89--112, 2008. DOI 10.1007/s10994-008-5059-5. Special issue of for COLT 2007 (Invited).
  

• On Kernels, Margins, and Low-dimensional Mappings. With Avrim Blum and Santosh Vempala. ALT 2004.
  
  An extended version appears in Machine Learning Journal, 65(1):79--94, 2006.
  

Semi-Supervised Learning

• Efficient Semi-supervised and Active Learning of Disjunctions. With Chris Berlind, Steven Ehrlich, and Yingyu Liang. ICML 2013.
  

• Open Problems in Efficient Semi-Supervised PAC Learning. With Avrim Blum. COLT 2007.
  

• An Augmented PAC Model for Semi-Supervised Learning. With Avrim Blum. Book Chapter in Semi-Supervised Learning, Chapelle, O., Zien, A., and Scholkopf, B. (Eds.), MIT Press, 2006.
  

• A PAC-style Model for Learning from Labeled and Unlabeled Data. With Avrim Blum. COLT 2005.
  
  Extended version appears under the title A Discriminative Model for Semi-Supervised Learning in Journal of the ACM 2010.

• Co-Training and Expansion: Towards Bridging Theory and Practice. With Avrim Blum and Ke Yang. NIPS 2004.
  
  

Ranking

• Robust Reductions from Ranking to Classification. With Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, and Greg Sorkin. COLT 2007.
  
  An extended version appears in Machine Learning Journal, 72(1-2):139--153, 2008. Special issue for COLT 2007 (Invited).
  
  

Computer Vision and Machine Learning

• Combining Self Training and Active Learning for Video Segmentation. With Alireza Fathi, Xiaofeng Ren, and James M. Rehg. BMVC 2011.
  
  See also Alireza's Interactive Segmentation Software.

• Person Identification in Webcam Images: An Application of Semi-Supervised Learning. With Avrim Blum, Pakyan Choi, John Lafferty, Brian Pantano, Mugizi Rwebangira, and Xiaojin Zhu. ICML 2005 Workshop on Learning with Partially Classified Training Data.

• Handwritten Text Localization in  Skewed Documents. With Ergina Kavallieratou, Doru Balcan, and Nikos Fakotakis. International Conference on Image Processing (ICIP) 2001.

• An Adaptive Resonance Theory (ART) Based Approach to Handwritten/ Machine-Printed Text Discrimination. With Doru Balcan. ICC&IE 2001.
  

Equilibrium Computation

• Nash Equilibria in Perturbation-Stable Games. With Mark Braverman. Theory of Computing 2017.
  

• On Nash-Equilibria of Approximation-Stable Games. With Pranjal Awasthi, Avrim Blum, Or Sheffet, and Santosh Vempala. SAGT 2010.
  
  A general audience version appears in the Current Science Journal 2012.
  

• On the Equilibria of Alternating Move Games. With Aaron Roth, Adam Kalai, and Yishay Mansour. SODA 2010

Solution Concepts and Dynamics in Multi-agent Systems

• Diversified Strategies for Mitigating Adversarial Attacks in Multiagent Systems. With Avrim Blum and Shang Tse-Chen. AAMAS 2018.

• Commitment Without Regrets: Online Learning in Stackelberg Security Games. With Avrim Blum, Nika Haghtalab, and Ariel Procaccia. EC 2015.

• Active Learning and Best-Response Dynamics. With Chris Berlind, Avrim Blum, Emma Cohen, Kaushik Patnaik, and Le Song. NIPS 2014.
  

• Near Optimality in Covering and Packing Games by Exposing Global Information. With Sara Krehbiel, Georgios Piliouras, and Jinwoo Shin. CDC 2012.
  
  An extended version appears in ACM Transactions on Economics and Computation 2014.
  

• The Weighted Majority Algorithm does not Converge in Nearly Zero-sum Games. With Florin Constantin and Ruta Mehta. ICML 2012 Workshop on Markets, Mechanisms, and Multi-Agent Models.

• Leading Dynamics to Good Behavior. SIGecom Exchanges, Vol. 10.2, 2011 (Invited).
  

• The Snowball Effect of Uncertainty in Potential Games. With Florin Constantin and Steven Ehrlich. WINE 2011.
  

• Game-theoretic Couplings and Applications. With Florin Constantin, Georgios Piliouras, and Jeff Shamma. CDC 2011.
  
  See also extended version (2013).

• Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior. With Avrim Blum and Yishay Mansour. ICS 2010.
  
  See also a journal paper appearing in SIAM Journal on Computing 2013, combining and extending the ICS'10 and SODA'09 papers.
  

• The Price of Uncertainty. With Avrim Blum and Yishay Mansour. EC 2009.
  
  An extended version appears in ACM Transactions on Economics and Computation 2013.
  

• Improved Equilibria via Public Service Advertising. With Avrim Blum and Yishay Mansour. SODA 2009.
  

Pricing Problems

• Learning Economic Parameters from Revealed Preferences. With Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay Vazirani. WINE 2014.

• Sequential Item Pricing for Unlimited Supply With Florin Constantin. WINE 2010.

• Item Pricing for Revenue Maximization. With Avrim Blum and Yishay Mansour. ACM Conference on Electronic Commerce, 2008.
  
  A related note appears in SIGecom Exchanges, Issue 7.3, 2008 (Invited).

• Approximation Algorithms and Online Mechanisms for Item Pricing. With Avrim Blum. ACM Conference on Electronic Commerce, 2006.
  
  An extended version appears in Theory of Computing, 3/9: 179--195, 2007.
  

• A Theory of Loss-leaders: Making Money by Pricing below Cost. With Avrim Blum, Hubert Chan, and MohammadTaghi Hajiaghayi. WINE 2007. Also available as Technical Report, CMU-CS-07-143.