Reproduce “No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Jun-Kun Wang, Jacob Abernethy, Kfir Y. Levy
A unified framework, Fenchel Game No-Regret Dynamics (FGNRD), is presented for first-order convex optimization, leveraging sequential two-player zero-sum games with no-regret learning. This framework systematically recovers numerous classical optimization algorithms, including Nesterov's accelerated methods and Frank-Wolfe, and derives new algorithms with convergence rates such as O(1/T^2) for smooth convex functions.
Key insights
- A surprisingly large number of classical first-order optimization methods can be viewed as specific instantiations of no-regret dynamics within the Fenchel game framework.
- The convergence rate of an optimization algorithm can be modularly derived by combining the known regret bounds of individual online learning strategies for each player.
- The framework provides a systematic "recipe book" for constructing new first-order methods by combining different no-regret strategies and weighting schemes for the Fenchel game players.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.