Thesis Oral Defense - Mikhail Khodak

— 5:00pm

Speaker:
MIKHAIL KHODAK, Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~mkhodak/

The Learning of Algorithms and Architectures

How should we design the algorithms we run and the architectures we learn? Several high-impact areas of computing have begun to automate these procedures using machine learning (ML), reducing the need for human effort by using our expanding amount of data and compute. We use ideas from ML, algorithm design, and optimization to advance our understanding of these areas of data-driven computing—meta-learning, algorithms with predictions, and architecture search—and to translate the resulting methodologies into state-of-the-art implementations.

  • In meta-learning, which uses ML itself to improve ML algorithms by learning across many learning tasks, we introduce ARUBA, a framework for designing and analyzing meta-learning methods. Our analysis yields the first guarantees for gradient-based meta-learning, showing how such methods improve performance based upon quantifiable measures of similarity between learning tasks. We use ARUBA to extend the practical impact of meta-learning to new areas of ML, including to learning with partial feedback and to federated learning.
  • We build upon the success of ARUBA by taking its core approach—the optimization of surrogate loss functions approximating algorithmic objectives—and extending it beyond learning algorithms to show learning guarantees for algorithms with predictions, which are algorithms that take advantage of learned predictions about their instances; in particular, we show the first learning-theoretic guarantees for predictions that depend on the instance the algorithm is run on, a crucial property for practical applications. We apply our framework while introducing algorithms with predictions to new areas such as scientific computing, where we design learning algorithms that, under natural structural assumptions, can learn to make instance-optimal predictions.
  • Lastly, we address the problem of finding neural network architectures to train on specific learning tasks, or architecture search, where we make progress towards understanding the optimization and generalization properties of weight-sharing, a dominant heuristic used throughout the field. We then extend weight-sharing to design new search spaces based around neural operations that allow for the automated discovery of truly novel architectures from data; the culmination of this effort is DASH, a method that efficiently finds architectures that outperform human expert-designed neural architectures on the majority of diverse tasks we test.

Thesis Committee:

Maria-Florina Balcan (Co-Chair)
Ameet Talwalkar (Co-Chair)
Tom Mitchell
Peter Bartlett (University of California, Berkeley)
Piotr Indyk (Massachusetts Institute of Technology)
Alexander Smola (Boson AI)

In Person and Zoom Participation.  See announcement.

Event Website:
https://csd.cmu.edu/calendar/thesis-oral-defense-mikhail-khodak