Acceleration through Optimistic No-Regret Dynamics
Authors: Jun-Kun Wang, Jacob D. Abernethy
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider the problem of minimizing a smooth convex function by reducing the optimization to computing the Nash equilibrium of a particular zero-sum convexconcave game. Zero-sum games can be solved using online learning dynamics, where a classical technique involves simulating two no-regret algorithms that play against each other and, after T rounds, the average iterate is guaranteed to solve the original optimization problem with error decaying as O(log T/T). In this paper we show that the technique can be enhanced to a rate of O(1/T 2) by extending recent work [22, 25] that leverages optimistic learning to speed up equilibrium computation. The resulting optimization algorithm derived from this analysis coincides exactly with the well-known NESTEROVACCELERATION [16] method, and indeed the same story allows us to recover several variants of the Nesterov s algorithm via small tweaks. We are also able to establish the accelerated linear rate for a function which is both strongly-convex and smooth. This methodology uniļ¬es a number of different iterative optimization methods: we show that the HEAVYBALL algorithm is precisely the non-optimistic variant of NESTEROVACCELERATION, and recent prior work already established a similar perspective on FRANKWOLFE [2, 1]. |
| Researcher Affiliation | Academia | Jun-Kun Wang College of Computing Georgia Institute of Technology Atlanta, GA 30313 jimwang@gatech.edu Jacob Abernethy College of Computing Georgia Institute of Technology Atlanta, GA 30313 prof@gatech.edu |
| Pseudocode | Yes | Algorithm 1 Computing equilibrium using no-regret algorithms; Algorithm 2 A variant of our accelerated algorithm.; Algorithm 3 Nesterov Algorithm; Algorithm 4 HEAVYBALL algorithm; Algorithm 5 (A) Nesterov s 1-memory method [17] and (B) Nesterov s -memory method [19]; Algorithm 6 Accelerated Proximal Method |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or a link to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets, therefore it does not mention public dataset availability. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report on empirical experiments; thus, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an empirical experimental setup with hyperparameters or system-level training settings. |