Nina's Page

Maria-Florina Balcan

Cadence Design Systems Professor of Computer Science
School of Computer Science (MLD and CSD)
Carnegie Mellon University

Office: GHC 8205
Phone: 412-268-5295
Email: ninamf AT cs DOT cmu DOT edu

I am the Cadence Design Systems Professor of Computer Science at Carnegie Mellon University. My main research interests are in machine learning, artificial intelligence, and theoretical computer science. Current research focus includes:

Foundations for modern machine learning. These include new analysis models and principled, practical algorithms for interactive learning, learning from limited supervision, distributed learning, learning representations, and life-long learning.
Algorithm design and analysis, including the use of machine learning for algorithm design and beyond the worst-case analysis of algorithms.
Computational and data-driven approaches in game theory and economics.
Computational, learning theoretic, and game theoretic aspects of multi-agent systems.

I am a Simons Investigator and a recipient of the 2019 ACM Grace Murray Hopper Award (awarded to the outstanding young computer professional of the year). I was a Program Committee Co-chair for NeurIPS 2020, ICML 2016, and COLT 2014. I was recently the Uhlenbeck Lecturer at the Women in Mathematics program at Princeton (2022), an invited speaker at International Congress of Mathematicians (2022) and at the Stony Brook International Conference on Game Theory (2021). For more information see my my resume.

Research

List of all my papers here.

Selected recent papers

Robustly-reliable learners under poisoning attacks. With Avrim Blum, Steve Hanneke, Dravyansh Sharma. COLT 2022.
Data driven semi-supervised learning. With Dravyansh Sharma. NeurIPS 2021 (Oral).
How much data is sufficient to learn high-performing algorithms?
With Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. STOC 2021.
Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond. With Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik. NeurIPS 2021 (Spotlight).
Data-driven algorithm design. Chapter 29 in the Beyond the Worst-Case Analysis of Algorithms book, Cambridge University Press, 2020.
Noise in Classification. With Nika Haghtalab. Chapter 16 in the Beyond the Worst-Case Analysis of Algorithms book, Cambridge University Press, 2020.
Semi-bandit Optimization in the Dispersed Setting. With Travis Dick and Wesley Pegden. UAI 2020.
Learning to Link. With Travis Dick and Manuel Lang. ICLR 2020.
Adaptive Gradient-Based Meta-Learning Method. With Mikhail Khodak and Ameet Talwalkar. NeurIPS 2019.
Envy-free Classification. With Travis Dick, Ritesh Noothigattu, and Ariel D. Procaccia. NeurIPS 2019.
Estimating Approximate Incentive Compatibility. With Tuomas Sandholm and Ellen Vitercik. ACM EC 2019.
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 (Spotlight).
Learning to Branch. With Travis Dick, Tuomas Sandholm, and Ellen Vitercik. ICML 2018.
A General Theory of Sample Complexity for Multi-Item Profit Maximization. With Tuomas Sandholm and Ellen Vitercik. ACM EC 2018.
Submodular Functions: Learnability, Structure, and Optimization. With Nick Harvey. SIAM Journal of Computing 2018.
Earlier version titled Learning Submodular Functions in STOC 2011.
Also a NECTAR track paper at ECML-PKDD 2012 (for "significant machine learning results"). See short abstract.
Learning-Theoretic Foundations o Algorithm Configuration for Combinatorial Partitioning Problems. With Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. COLT 2017.
The Power of Localization for Efficiently Learning Linear Separators with Noise. With Pranjal Awasthi and Phil Long. Journal of the ACM 2017.
Earlier version in STOC 2014.
Data Driven Allocation for Distributed Learning. With Travis Dick, Mu Li, Venkata Krishna Pillutla, Colin White, and Alex Smola. AISTATS 2017.
Nash Equilibria in Perturbation-Stable Games. With Mark Braverman. Theory of Computing Journal 2017.
Clustering under Perturbation Resilience. With Yingyu Liang. SIAM Journal of Computing 2016.
Efficient Algorithms for Learning and 1-bit Compressed Sensing under Asymmetric Noise. With Pranjal Awasthi, Nika Haghtalab, and Hongyang Zhang. COLT 2016.
Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy. With Vitaly Feldman. Algorithmica 2015 (special issue, invited).
Earlier version in NIPS 2013.
Robust Hierarchical Clustering. With Yingyu Liang and Pramod Gupta. Journal of Machine Learning Research 2014.
Earlier version in COLT 2010.

Teaching

10-701 Machine Learning (at CMU): Spring 2021(with Henry Chai), Spring 2022.
10-315 Machine Learning (at CMU): Spring 2021(with Leila Wehbe), Spring 2019.
10-715 Advanced Introduction to Machine Learning (at CMU): Fall 2018, Fall 2017.
10-401 Machine Learning (at CMU): Spring 2018.
10-601 Machine Learning (at CMU): Fall 2016 (with Matt Gormley), Spring 2016 (with William Cohen), Spring 2015 (with Tom Mitchell).
10-806 Foundations of Machine Learning and Data Science (at CMU): Fall 2015 (with Avrim Blum).
Machine Learning Theory (at Georgia Tech): Fall 2013, Fall 2011, Spring 2010.
Design and Analysis of Algorithms (at Georgia Tech): Spring 2014, Spring 2013, Fall 2012, Spring 2011.
Connections between Learning, Game Theory, and Optimization (at Georgia Tech) Fall 2010.
Machine Learning Theory (at CMU). Spring 200 (with Avrim Blum).
Artificial Intelligence (Spring 2002, University of Bucharest)