UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization

Abstract

We propose a novel adaptive, accelerated algorithm for the stochastic constrained convex optimization setting. Our method, which is inspired by the Mirror-Prox method, \emph{simultaneously} achieves the optimal rates for smooth/non-smooth problems with either deterministic/stochastic first-order oracles. This is done without any prior knowledge of the smoothness nor the noise properties of the problem. To the best of our knowledge, this is the first adaptive, unified algorithm that achieves the optimal rates in the constrained setting. We demonstrate the practical performance of our framework through extensive numerical experiments.

NeurIPS 2019

Cited by in corpus (7)

• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Regret minimization in stochastic non-convex learning via a proximal-gradient approach
• Explicit Regularization of Stochastic Gradient Methods through Duality
• About some works of Boris Polyak on convergence of gradient methods and their development
• Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements
• Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
• Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays