Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method

Abstract

We consider the classical setting of optimizing a nonsmooth Lipschitz continuous convex function over a convex constraint set, when having access to a (stochastic) first-order oracle (FO) for the function and a projection oracle (PO) for the constraint set. It is well known that to achieve $\epsilon$-suboptimality in high-dimensions, $\Theta ({\epsilon }^{-2})$ FO calls are necessary. This is achieved by the projected subgradient method (PGD). However, PGD also entails $O({\epsilon }^{-2})$ PO calls, which may be computationally costlier than FO calls (e.g. nuclear norm constraints). Improving this PO calls complexity of PGD is largely unexplored, despite the fundamental nature of this problem and extensive literature. We present first such improvement. This only requires a mild assumption that the objective function, when extended to a slightly larger neighborhood of the constraint set, still remains Lipschitz and accessible via FO. In particular, we introduce MOPES method, which carefully combines Moreau-Yosida smoothing and accelerated first-order schemes. This is guaranteed to find a feasible $\epsilon$-suboptimal solution using only $O({\epsilon }^{-1})$ PO calls and optimal $O({\epsilon }^{-2})$ FO calls. Further, instead of a PO if we only have a linear minimization oracle (LMO, a la Frank-Wolfe) to access the constraint set, an extension of our method, MOLES, finds a feasible $\epsilon$-suboptimal solution using $O({\epsilon }^{-2})$ LMO calls and FO calls---both match known lower bounds, resolving a question left open since White (1993). Our experiments confirm that these methods achieve significant speedups over the state-of-the-art, for a problem with costly PO and LMO calls.

References in corpus (22)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Input Convex Neural Networks
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Variance-Reduced and Projection-Free Stochastic Optimization
• Projection-free Online Learning
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• RSG: Beating Subgradient Method without Smoothness and Strong Convexity
• Regularizing with Bregman-Moreau envelopes
• Variance Reduction for Matrix Games
• Input Convex Neural Networks for Optimal Voltage Regulation
• Towards Gradient Free and Projection Free Stochastic Optimization
• Potential-Function Proofs for First-Order Methods
• Stochastic Frank-Wolfe for Composite Convex Minimization
• A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
• Differentially Private Matrix Completion Revisited
• O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
• On the Online Frank-Wolfe Algorithms for Convex and Non-convex Optimizations
• Faster Projection-free Online Learning
• Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization

Cited by in corpus (2)

• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum