Elad Hazan's 20-Year OCO Retrospective: Regret Minimization, AdaGrad, and AI Frameworks

Princeton professor Elad Hazan published a personal retrospective on two decades of Online Convex Optimization (OCO), tracing its evolution from a niche theoretical area to a foundation of modern machine learning. The article, compiled by Machine Heart, combines Hazan's first-person narrative with contextual commentary on AI's growing role in mathematics.

Early Motivation: Fear of the Job Market

Hazan began studying OCO in his third PhD year at Princeton, partly as a fallback plan. Surrounded by theoretical computer science luminaries — Ryan O'Donnell, Irit Dinur, Scott Aaronson, Sanjeev Arora — he felt unable to compete on pure theorem-proving ability. He organized a student reading group on Thomas Cover's universal portfolios, aiming to build a practical algorithm with optimal regret bounds. This pragmatic fear, he notes, pushed him toward framework-building rather than theorem-proving — a choice he now sees as prescient given AI's strength at the latter.

Online Newton Step: Unifying Optimization and Learning

Cover's universal portfolios guarantee performance against the best fixed rebalanced portfolio without market assumptions. Martin Zinkevich introduced regret — cumulative loss versus the best fixed decision in hindsight — and showed gradient descent achieves near-optimal regret. Hazan, with Satyen Kale and others, asked whether Newton's method could yield better regret bounds. The resulting Online Newton Step (ONS) algorithm unified portfolio selection, gradient descent, and Newton's method under a single regret-minimization framework. The paper was rejected by FOCS/STOC, but Hazan considers it a career favorite for its conceptual unification.

AdaGrad: Competing with the Best Regularizer

During a postdoc at IBM Almaden, Hazan collaborated with Yoram Singer and John Duchi (then a Berkeley student commuting by bike to Google Mountain View). Their core question: can we compete with the best regularizer in hindsight? This lifted the regret perspective from learning algorithms to the optimizer family itself. The result was AdaGrad, an adaptive gradient method that became a workhorse of deep learning. Hazan credits Singer's optimization drive, Duchi's matrix mathematics, and his own job-search urgency for the trio's success.

Golden Era with Satyen Kale

From postdoc to first faculty position, Hazan and Kale produced nearly 20 papers in a few years, exploring:

Projection-free methods

Variational bounds in regret

Bandit algorithms

Game theory, equilibria, and fixed points

Optimal stochastic strongly convex optimization

Online submodular minimization

Online matrix prediction (with Shai Shalev-Shwartz)

Multiplicative weights and applications (with Sanjeev Arora)

A visa delay at NeurIPS 2008 stranded Hazan in Canada; Kale stayed with him, and they wrote three papers during the ordeal.

Technion Years: Mentoring and New Results

At Technion, Hazan supervised Tomer Koren, Dan Garber, Kfir Levy, and Oren Anava (three became professors). Highlights include:

Playing non-linear games with linear oracles (with Garber)

Equivalence of Blackwell approachability and no-regret learning (with Jake Abernethy, Peter Bartlett)

Beating SGD: learning SVMs in sublinear time (with Koren, Nati Srebro)

Tight bounds for stochastic and online logistic regression (with Koren, Levy)

Dynamical Systems, Control, and Spectral Filtering

Tengyu Ma's talk on learning linear dynamical systems statistically triggered Hazan's "regret treatment" approach. With students Cyril and Karan, he developed spectral filtering: instead of identifying the hidden system, use a larger predictor class (fixed filters from Hankel matrices) and learn their combination via improper learning and regret minimization. This turned the prediction problem convex. Initially limited to symmetric systems, it expanded to universal sequence preconditioning (with Annie Marsden, John Duchi's student).

In nonstochastic control, actions affect future states. The key was finding a controller parameterization that embeds OCO into the dynamics, leading to a book with Karan.

Return to Deep Learning: Spectral State Space Models and Flash STU

With Naman Agarwal, Daniel Suo, and Xinyi Chen, spectral filtering yielded spectral state space models and eventually Flash STU — a representation designed for regret theorems that became a neural network architecture component.

Final Reflection: Zero Regret

Hazan connects his journey to the 2024 letter by Terence Tao and 24 Fields Medalists on AI in mathematics. As AI masters theorem-proving, he argues, choosing interesting problems and inventing new frameworks becomes the core human contribution. He expresses deep satisfaction with OCO's mathematical elegance and practical impact, but emphasizes his greatest reward: the relationships built with students and collaborators. "I have zero regret," he concludes, punning on his life's work.

"AI only proves theorems, doesn't invent frameworks." — Elad Hazan