Twenty years ago, online Convex Optimization (OCO) was still a young direction at the intersection of theoretical computer, machine learning and optimization. Today, regret minimization, self-adaptation updates and online decision-making frameworks have profoundly influenced modern machine learning. From Online Newton Step, AdaGrad, to bandit optimization, online control and sequence modeling, many of OCO's ideas have gradually entered the core methodology of AI.
Today, the relationship between AI and mathematics has reached a new juncture. In September, Taoiseach and 24 other Fields Prize winners published A Severe Misalignment of AI in Mathematics, sparking widespread discussion in the mathematical community about AI, the value of mathematical research, and the academic ecology. As AI's ability to search, infer, and prove rapidly improves, an increasingly realistic question arises: where will the core value of mathematicians lie when machines can solve more mathematical problems?
Professor Elad Hazan of Princeton University recently wrote a review of two decades of online optimization. From universal portfolio, Online Newton Step and AdaGrad, to online control, spectral filtering and new neural network architectures, he linked an important technological link between OCO and modern AI through his research experience.
At the end of the article, Hazan also focuses on the impact of AI on mathematical research. He believes that as AI becomes better at theoretical proofs, it will become more important to choose interesting questions and create new frameworks. This touches on a core issue that is being discussed in the mathematical community today: what questions to ask, what concepts to create and what frameworks to build may become even more important when the ability to search, infer and prove is increasingly enlarged by AI.
The following is the original text of Elad Hazan:
20 years of online optimization: a personal memoryI first started studying online Convex Optimization (OCO) in my third year of blogging. At the time, Zinkevich's paper had just been published. At the same time, I was reading a paper with several colleagues in Cover on universal portfolios.
When I was in graduate school, I wanted to do computational complexity theory. But at the time, I was often surrounded by a group of mathematical geniuses: Ryan O'Donnell, Irit Dinur, Scott Aaronson, Dana Moshkovitz, Robert Krauthgamer, Muli Safra, and of course, my mentor Sanjeev Arora, who was under enormous pressure.
I can invite Scott and Dana to my house for dinner; I can have coffee with Noga Alon next week; and I can talk to my youngest son, Avi Wigderson, Oded. I can't imagine being so close to them after reading blogs.
So, let's put our humility aside for a while: it was my idea to organize a group of students that year to study finance together, so that you could get out of the academic path and get a job in the financial industry.
At the same time, we were also studying Cover's investment group logic. Our initial goal was to improve Cover's approach to a truly efficient algorithm while retaining the best regret bound he got. In short, we later found a very beautiful link: Newton's method, regretted minimization, and online optimization, which could actually be put into the same framework. This eventually became one of my favorite papers of my life, which was to come up with that paper on the Newton StepONS algorithm. More importantly, the finding that "whatever method is used to efficiently pursue what appears to be the best fixed decision" can become a unified perspective. In this perspective, portfolio selection, gradient decline and Newton's method suddenly become different forms of the same thing.
It has a very special guarantee: even if you don't make any assumptions about the market, its performance can still be compared to the best-looking, fixed-ratio and continuously rebalanced stock portfolio. Zinkevich's paper examines a similar concept, which comes from the theory of bouncing, i.e. regret.
What really fascinated me was the link between mathematical optimization and learning. But at the time, this link had hardly been explored. I remember asking an optimization expert at ORFE a very basic question: "What is the worst-case computational complexity of constraint-containing optimization?"
So I turned to reading Nesterov and Nemirovski's groundbreaking book. Later, Yuri Nesterov and Arkadi Nemirovski became icons of science in my mind. I had the privilege of communicating with Arkadi himself, one of the greatest scientists I have ever met.
From the perspective of a theoretical computer Ph.D. student, this was a very strange state of affairs in the field of optimization at the time. It was a very deep, very mature field, but it also lacked a concise, unified algorithmic language to connect optimization, learning and sequential decision-making.
From ONS to the Adaptive Ladder Method
One of the biggest achievements in this field was probably the development of adaptive gradient methods. They later became one of the main tools of modern deep learning and AI, and the starting point of the story was AdaGrad. The story behind this was really interesting. Recently, I also spoke at two colleagues' 60th birthday celebrations: one was Yoram Singer who invented this method together with him and John Duchi; the other was Peter Bartlett.
After I graduated, I went to the famous IBM Almaden "Theory Group" as a postdoctoral fellow and was welcomed by the very good mathematician Nimrod Megiddo. From the beginning, my goal was to return to my homeland of Israel as a professor.
So, in order to connect with a senior Israeli professor, I decided to go to the renowned optimization expert, Yoram Singer. It wasn't difficult. Yoram already knew me because he had seen our 2006 ONS paper. He was one of the first to really understand and recognize the work. Later, he worked with my friends, Shai Shalev-Shwartz, and Nati Srebro, to apply some of these ideas to Pegasos.
I have to congratulate Yoram: He was very open about his research. He was very enthusiastic about welcoming me to the office at Google Mountain View. Then, I, Yoram and John Duchi started trying to improve the optimization method. At the time, John was also a Berkeley student, riding a bike every day, going back and forth between Berkeley and Google Mountain View Park for about an hour. I especially liked Google MTV Park: free food, coupled with an extremely thick nerd atmosphere, was the ideal environment for doing research.
Our central question at the time was: Can we compete with "the best way to normalize the future?"
This is actually equivalent to using the idea of regret for the optimizer family itself. Previously, the concept of regret had brought together different learning algorithms. Now, we have raised our perspective a step further and started targeting the optimizer itself. Today, this idea is very common in the field of optimization, but at the time, it was completely new.
Yoram's motivation came from optimizing itself and he wanted to improve machine learning practices. John was obsessed with the part of the matrix mathematics that was really beautiful.:-) As for me, I was still trying to find a teaching job in Israel... As a result, this combination of the three was quite successful, and this is how the adaptive gradient method was born!
Adaptation, calculation and friendship
Satyen and I were like a well-functioning scientific research machine. Regardless of what we saw, we almost always found that no one in the past seemed to really see it from the perspective of regret, optimization, or a combination of the two.
Projection-free methods
Variational bounds in Regret
Bandit algorithms
This is the first time I've ever been in a situation like this.
Optimum randomness and accuracy
Online submodular minimization
Online matrix prediction, in collaboration with Shai Shalev-Shwartz
Multiplicative weights and its applications in collaboration with our mentor Sanjeev Arora
And behind all these studies, there is a very strong sense of partnership. We don't even need to complement each other, it's more like two people are on the same frequency - even what they like to eat and where they like to go.
Chart: Satyen and I were standing in front of a whiteboard full of formulae while reading.
Chart: Satyen and me while reading.
I especially remember one NeurIPS, which was supposed to be held in Vancouver, Canada, in 2008. I needed to renew my U.S. visa. The result was basically that my application was rejected, or that I was told that it could take months to process, and that in the meantime I had to stay outside the U.S. I explained at the consulate that I still had a baby in my house waiting for me in California, but it was completely useless. I was so stuck in Canada that I didn't know what to do next.
Satyen stayed in Vancouver with me. He opened a hotel room next to me and probably stayed with me, I can't remember. After all, we worked together, we ate together before I figured out what to do next. Finally, my solution was to run to a bunch of Patagonia...:-) What's even more amazing is that during that time, we wrote three new papers together!
My first day as a professor
My dream finally came true. I got a teaching position in Israel and went to the Technion. It was a top university, although I was at the Faculty of Industrial Engineering, to be honest, it wasn't my first choice.
It's a completely different experience than any other relationship, and it's how much you put into it, and the end result is often tenfold. I've mentored four graduate students: Tomer Koren, Dan Garber, Kfir Levy, and Oren Anava. All three of them have gone on to become very good professors. Over the years, OCO has been growing rapidly, and new results are emerging around the world, just like in my little paradise. Many friends have visited us, including Jake Abernethy, Manfred Warmuth, Sham Kakade, Alexander Madry, and, of course, many others.
Playing non-linear games with linear oracles, with Dan Garber
The equivalence of Blackwell approachability and no-regret learning, with Jake Abernethy, Peter Bartlett
Beating SGD: learning SVMs in sublinear time, in collaboration with Tomer Koren, Nati Srebro
Tight bounds for stochastic and online logistic regression, in collaboration with Tomer Koren, Kfir Levy
Image: Jake Abernethy and me in the Technion office.
Image: During the Technion, I was with students Tomer Koren, Kfir Levy, Oren Anava, outside a chicken restaurant in Alabama. Dan Garber didn't come to dinner because he was a vegetarian:-)
Power systems, controls and spectral transformers
With the rise of deep learning, adaptive gradient approaches were increasingly seen as an important part of this revolution. Later, I received offers from Stanford and Princeton at the same time, eventually choosing to return to my alma mater, Princeton. After becoming a Princeton professor, I did a few more years of optimizing research, but slowly, my interest in OCO began to wane.
Tengyu Ma, who was also a student of Sanjeev at Princeton, told me about his work with Benjamin Recht, Moritz Hardt, to learn about linear dynamics in statistics. But when I heard statistical models, it was "allergic...:-) So I said to my students Cyril and Karan, "There must be another way, let's give this a regret treatment".
As a result, my two brilliant students invented a new technology that took us much further than we had originally imagined: spectral filtering. The technology behind it is actually very OCO, from improper learning, to fast online optimization, to regret minimization, all taste like OCO. The core idea is that we don't really have to identify that hidden power system. Instead, we can use a different, larger category of predictor to compete directly with it. The initial results were only for symmetric systems, but this approach has since been greatly expanded. Recently, I've had a conversation with Annie Marsden, PhD, who was a student of John Duchi's, who developed it into universal sequence preconditioning.
In non-stochastic control, we compare: under exactly the same disturbance, if changed to another controller and allowed it to evolve along its own trajectory, what would it ultimately accomplish? Again, the real key is to find the right controller parameterization method. Once the parameters are paired, we can insert the online optimization into a dynamic. Later, Karan and I wrote a book specifically about this method.
Then there was another twist. These ideas finally took us back to deep learning. I worked with Naman Agarwal, Daniel Suo, Xinyi Chen to build spectral state space models using spectral filtering, and later developed Flash STU. So, a representation originally designed to prove the regret theorem eventually became part of the neural network architecture.
Chart: I was an early member of the Princeton lab. From left to right are Xinyi, Karan, Brian, me and Naman.
Picture: Meals with students at Princeton. Cyril, I, Zhou, Udaya, Nataly, Wenhan, Naman, Jennifer and Xinyi are next at the table.
The last thing I want to say
In retrospect, I feel that it all started with "fear of not finding a job" and it wasn't accidental. This fear pushed me off a path that relied mainly on theoretical proofs. After all, it was a very competitive path. I turned to something else: building a framework. If I were in today's AI era, I would be more proactive in making the same choices.
I'm very, very satisfied with the science of OCO. Whether it's mathematically sophisticated or realistically valuable, it far exceeds my initial expectations. But there's no doubt that the most important thing I've really gained is the relationships I've built along the way with my students and my collaborators.
Lastly, I apologize for missing out on a lot of collaborations and exchanges -- especially my collaboration with Jake Abernethy, Sasha Rakhlin on bandit optimization, which is worth writing a separate story about -- and my collaboration with Adam Kalai, Sham Kakade, Shay Moran, Paula Gradu, Xinyi Chen, Jennifer Sun, Annie Marsden, and perhaps many others, which didn't happen.
© THE