Let’s Stop Leaving Money on the Table | Richard M. Karp Distinguished Lecture

Let’s Stop Leaving Money on the Table | Richard M. Karp Distinguished Lecture

by Katrina Ligett

Formal & Physical Sciences AI — Models & Research UYQArtificial intelligence (AI)UYQMMachine learning
🎙 Katrina Ligett 👥 75K 📅 February 5, 2026 ⏱ 63 min 👁 4K 📄 expert opinion 🧭 2026-08-03
Available in: English (current) Français

Keywords

theory-practice gaprandomnessworst-case analysisdifferential privacyinstance-specific analysis

Summary

In this Richard M. Karp Distinguished Lecture, Katrina Ligett addresses the growing divergence between machine learning theory and practice. She argues that while revolutionary new theory may be needed, there is also value in a more conservative approach: reformulating theoretical questions to better capture empirical success. The talk is structured around five vignettes from her own research and that of others, illustrating two main themes: exploiting randomness in algorithms and moving beyond worst-case analysis. The vignettes cover stochastic gradient descent, compression in federated learning, Gaussian sketching, outlier rejection, and adaptive data analysis. Ligett emphasizes that randomness, often already present in algorithms, can be leveraged for multiple benefits such as privacy, stability, and generalization. She also advocates for instance-specific analysis, which can provide more meaningful guarantees than worst-case bounds. Throughout, she highlights how privacy constraints can serve as a useful lens for robustness and stability. The talk concludes with a call for a careful accounting of algorithmic properties to bridge the gap between theory and practice.

165 words

Critical Evaluation

The lecture provides a thoughtful and accessible overview of the challenges facing machine learning theory, particularly the disconnect between theoretical guarantees and empirical performance. Ligett’s central thesis—that we can extract more from existing tools by exploiting randomness and moving beyond worst-case analysis—is well-argued and supported by concrete examples from her research. The five vignettes are well-chosen and illustrate the themes effectively, though the treatment is necessarily high-level given the format. The talk does not delve into technical details, but it succeeds in conveying the conceptual ideas and motivating the audience to consider alternative approaches. The speaker’s expertise is evident, and she appropriately credits the work of others. The discussion of privacy as a lens for robustness is particularly insightful, highlighting how constraints can lead to more careful algorithmic design. However, the talk is more of a perspective piece than a comprehensive review, and some claims could benefit from more rigorous justification. The lack of formal definitions (e.g., differential privacy) may limit accessibility for non-specialists, but the speaker’s informal explanations help mitigate this. Overall, the lecture offers valuable insights and encourages a rethinking of how theory is developed in machine learning. The title’s promise is fulfilled, and the content is both engaging and thought-provoking.

203 words

Title / Content Match

The title accurately reflects the central theme of the talk: identifying ways to extract more value from existing theoretical tools in machine learning, rather than solely pursuing revolutionary new theories.

Quality & Reliability

8/10

The lecture is given by a renowned expert in theoretical computer science, with a strong track record in privacy and machine learning theory. The content is well-structured, references multiple research works, and is presented in an academic setting (Simons Institute). However, it is a high-level talk without formal proofs, and some claims are based on personal perspective rather than exhaustive review.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

The lecture offers a fresh perspective on bridging the theory-practice gap in machine learning by advocating for a more careful accounting of algorithmic properties, particularly randomness and instance-specific analysis. It synthesizes multiple research threads and suggests practical directions for future work.

Pour aller plus loin :

  • Differential Privacy — Foundational concept discussed in the talk.
  • Stochastic Gradient Descent — Core algorithm analyzed in the first vignette.
  • Instance-optimality — A concept related to moving beyond worst-case analysis.
  • Adaptive Data Analysis — Topic of the fifth vignette.

85 words

Radar Profile

The radar profile shows high scores in information quantity, quality, and reliability, with a slightly lower technical level, reflecting the talk's meta-technical nature. The overall balance indicates a well-rounded and credible presentation.

Reliability 8/10