A Small Bug in My Online Gradient Descent Regret Bound
It’s messing up the computational advantage offered by α-strongly convex functions! 0_0
Did you spot it? 🔥🪰😂
The bug is adding a random variable factor to what is otherwise a very tight guarantee on the upper bound on the average regret accrued after T steps of the Online Gradient Descent (OGD) algorithm.
This particular upper bound guarantee can be attained only when OGD is applied to α-strongly convex cost functions and is a better, ie lower, upper bound than the one offered by OGD in the general case.
What’s an α-strongly convex function, you might ask? Well, that will be explained to you in an upcoming post, kind reader — I promise!
And voilà — this mini post is just a sneak peek at my upcoming post on Chapter 3 of Elad Hazan’s excellent textbook called Introduction to Online Convex Optimization, that I was unable to work on because I was away on a work trip to a music tech conference in New York City, where my company unveiled our new ML-powered music sync licensing product that we’re currently super busy building.
While my fully-featured OCO posts are being over-engineered (which is educational and thus 100% OK, because this Substack is only a hobby for me, remember!), my reading group and I will be meeting later today to discuss Chapter 4, which describes in detail a super cool application of OCO — the application of universal stock portfolio selection!
Thank you and au revoir, kind readers.
Yours truly,
Andrew Pak
PS: I haven’t forgotten about my Chapter 2 posts — as briefly mentioned above, I’m just being a tad obsessive about editing and hesitating between what cool content to keep and what cool content is rather too math-heavy and thus cumbersome to explain in my rather overview-oriented series of posts on OCO.
Sorry for the delay, but it’s not my fault that Chapter 2 is such a mathematical beast! There’s Euclidean balls and spheres and vector random variables in it, that are awesome mathematical tools that allow us to reduce non-convex functions to convex ones! And that’s a good thing!
To give you a little taste though, Chapter 2 is all about the mathematical tools used in “Offline” Convex Optimization, but they also happen to be our bread and butter for analyzing Online Convex Optimization algorithms. But since I’m the decider around here, I decided to sneak in some early OCO content as a nice little oracle post! 🔥😃🎉
