Tight Complexity Bounds for Optimizing Composite Objectives

Abstract

We provide tight upper and lower bounds on the complexity of minimizing the average of $m$ convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent (AGD) and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for the optimal rate. For non-smooth functions, having access to prox oracles reduces the complexity and we present optimal methods based on smoothing that improve over methods using just gradient accesses.

References in corpus (3)

• Optimal Black-Box Reductions Between Optimization Objectives
• PRISMA: PRoximal Iterative SMoothing Algorithm
• Lower Bound for Randomized First Order Convex Optimization

Cited by in corpus (24)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Byzantine Stochastic Gradient Descent
• The proximal point method revisited
• Stochastic, Distributed and Federated Optimization for Machine Learning
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• Lower Bound for Randomized First Order Convex Optimization
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
• Proximal Alternating Penalty Algorithms for Constrained Convex Optimization
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Lower Bounds for Higher-Order Convex Optimization
• Leverage Score Sampling for Faster Accelerated Regression and ERM
• Accelerated Alternating Direction Method of Multipliers: an Optimal $O(1/K)$ Nonergodic Analysis
• A General Analysis Framework of Lower Complexity Bounds for Finite-Sum Optimization
• First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates