A simpler approach to accelerated optimization: iterative averaging meets optimism
Recently there have been several attempts to improve the rates of convergence achievable for smooth objectives. In particular, several recent papers have attempted to extend Nesterov's accelerated algorithm to stochastic and variance-reduced optimization. In this paper, we show that there is a simpler approach to obtaining accelerated rates: applying generic, well-known optimistic online learning algorithms and using the online average of their predictions to query the (deterministic or stochastic) first-order optimization oracle at each time step. In particular, we tighten the recent results of Cutkosky (2019) to demonstrate theoretically that online averaging results in a reduced optimization gap, independently of the algorithm involved. Then, we show that a simple tuning of existing generic optimistic online learning algorithms (e.g., Joulani et al [2017]), when combined with the reduced error quantified above, naturally results in optimal accelerated rates. \todoc{what would you consider unnatural? get rid of this word?} Importantly, the smooth objective may or may not be strongly-convex, and the rates are nevertheless optimal for both stochastic and deterministic first-order oracles. We further show that the same ideas transfer to variance-reduced optimization. In each case, the proofs are much simpler than the previous work, such as the new derivations of accelerated algorithms based on a primal-dual view (Wang and Abernethy, 2018) or the ideas based on linear coupling (Allen-Zhu and Orecchia, 2017). Importantly, we also provide algorithms that maintain the ``universality'' property, meaning that the same algorithm achieves the optimal rate for smooth and non-smooth objectives without further prior knowledge, generalizing the results of Kavis et al (2019) and solving a number of their open problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this p…
Adaptive Averaging in Accelerated Descent Dynamics
We study accelerated descent dynamics for constrained convex optimization. This dynamics can be described naturally as a coupling of a dual variable accumulating gradients at a given rate $\eta(t)$, and a primal variable…
On Principled Local Optimization Methods for Federated Learning
Federated Learning (FL), a distributed learning paradigm that scales on-device learning collaboratively, has emerged as a promising approach for decentralized AI applications. Local optimization methods such as Federated…
Federated LearningActor-Accelerated Policy Dual Averaging for Reinforcement Learning in Continuous Action Spaces
Policy Dual Averaging (PDA) offers a principled Policy Mirror Descent (PMD) framework that more naturally admits value function approximation than standard PMD, enabling the use of approximate advantage (or Q-) functions…
Reinforcement LearningA Simple Practical Accelerated Method for Finite Sums
We describe a novel optimization method for finite sums (such as empirical risk minimization problems) building on the recently introduced SAGA method. Our method achieves an accelerated convergence rate on strongly conv…