Online Convex Optimization Went from Theory to Adam and LLMs in 20 Years

Twenty years ago, online convex optimization (OCO) was still a young field at the intersection of theoretical computer science, machine learning and optimization. Today its vocabulary (regret, adaptive updates, sequential decisions made without knowing the future) is built into how modern models are trained. The Chinese outlet Jiqizhixin has devoted a long piece to this history under a wry headline: a man who spent his whole career studying "regret" says he has no regrets.

In the fragment available to us, the text breaks off in the middle of a list of methods (Online Newton Step and onward), and the subject's name is not given. So below we rely on the public history of the field rather than on details of the interview itself.

What regret measures

The standard formulation of an optimization problem knows the entire loss function in advance. OCO is different. At each step the algorithm picks a point, and only then does the environment reveal a convex loss function. Quality is measured by regret: the algorithm's total loss minus the total loss of the best fixed decision, chosen in hindsight.

The field's main achievement is that regret can be made sublinear. In that case the algorithm's average loss approaches the loss of the best constant choice, with no statistical assumptions about the data. Martin Zinkevich's classic 2003 paper showed that online gradient descent achieves regret on the order of √T on convex Lipschitz functions. That became the starting point.

From Online Newton Step to adaptive optimizers

Around 2006, Elad Hazan, Amit Agarwal and Satyen Kale proposed the Online Newton Step algorithm. For so-called exp-concave functions, it achieves regret on the order of log T, noticeably better than √T. The idea is to use second-order information: the step adapts to the geometry of the accumulated gradients.

This line of work then led to methods familiar to anyone who has ever launched a training run:

• AdaGrad (Duchi, Hazan, Singer, 2011): a separate step scale for each parameter. It works well on sparse features.
• RMSProp and Adam (2014): practical descendants of the same idea, using exponential averaging of gradients.
• Regret analysis as the standard proof technique: the original convergence argument for Adam was built within the OCO framework.

There is also a telling episode. In 2018, the paper "On the Convergence of Adam and Beyond" (Reddi et al., ICLR) showed that the original proof for Adam contains an error and that the method may fail to converge on some convex problems. The fix, AMSGrad, is also stated in the language of regret. Theory did not merely describe practice; it caught practice making mistakes.

Why it matters now

Large language models are usually trained with Adam variants, most often AdamW. The problem there is nonconvex, so OCO guarantees do not transfer directly. The intuition does: adaptive step sizes, preconditioning, accounting for curvature. Current research on optimizers with matrix preconditioners continues the same line, in which AdaGrad's diagonal adaptation gives way to richer structure.

A separate branch concerns online learning in its pure form. Regret minimization underlies algorithms for games, recommender systems, dynamic pricing and resource allocation. In these problems the future really is unknown, and the data need not be independent.

What to take away in practice

If you train or fine-tune models, it helps to remember where optimizer hyperparameters came from. Epsilon, the beta coefficients and the learning-rate schedule are not arbitrary; they have a theoretical meaning. That meaning can help you debug unstable training: divergence is often linked to adaptive averaging "forgetting" rare but large gradients, very much in the spirit of the counterexample to Adam.

For those building systems that make sequential decisions (recommendations, bids in ad auctions, routing requests between models), OCO offers a ready-made framework. It lets you compare algorithms against an honest benchmark and obtain guarantees without assumptions about the data distribution. Hazan's textbook "Introduction to Online Convex Optimization" is a good entry point. The full interview on the Jiqizhixin site is worth reading in the original: behind the "zero regrets" headline, judging by the announcement, is a personal story of the method's twenty years of development.