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.
Introduction: The Projection Bottleneck
In the landscape of machine learning and data science, optimizing "nonsmooth" functions—those with sharp kinks like the hinge loss or absolute value—is a fundamental task. These optimizations are typically performed over a constraint set (e.g., a small norm requirement). The standard tool for this, Projected Subgradient Descent (PGD), requires a Projection Oracle (PO) call after every gradient calculation.
In high-dimensional problems, such as those involving nuclear norm constraints for recommendation systems, a single projection can require a full Singular Value Decomposition (SVD), making it computationally expensive. Historically, it was believed that reaching an accuracy of $\epsilon$ required $O(\epsilon^{-2})$ projections. This paper challenges that assumption, introducing methods that significantly reduce projection steps without increasing gradient calls.
Methodology: MOPES and MOLES
The proposed framework leverages two sophisticated mathematical concepts to decouple gradient complexity from constraint complexity:
- Moreau-Yosida Smoothing: Instead of optimizing the nonsmooth function directly, the algorithms optimize its "Moreau envelope," a smooth version that shares the same minimum.
- Gradient Sliding: This technique allows the algorithm to take multiple gradient steps before needing to perform a projection, effectively breaking the 1:1 ratio between gradient and projection calls.
These ideas culminate in two primary algorithms:
- MOPES (MOreau Projection Efficient Subgradient): Designed for cases with a Projection Oracle, it reduces the number of projections from $O(\epsilon^{-2})$ to $O(\epsilon^{-1})$.
- MOLES (MOreau Linear minimization oracle Efficient Subgradient): Designed for the Frank-Wolfe setting where projections are difficult but Linear Minimization (LMO) is efficient. It achieves an optimal $O(\epsilon^{-2})$ complexity for both gradients and LMO calls.
A key requirement for these improvements is "Neighborhood Lipschitzness": the objective function must remain well-behaved in a small neighborhood just outside the constraint set, a mild assumption that holds for most practical machine learning problems.
Key Results and Theoretical Impact
The theoretical contributions of MOPES and MOLES are summarized in the table below, showing their performance against state-of-the-art (SOTA) methods and established lower bounds.
Theoretical Breakthroughs
- Efficiency Gains: MOPES provides the first-ever reduction in PO calls for this class of problems while maintaining optimal first-order complexity.
- Resolving the "White Question": MOLES provides an affirmative answer to a question open since 1993, matching theoretical lower bounds for both gradient and linear minimization calls in Frank-Wolfe style methods.
Experimental Validation
The authors evaluated their methods on a Matrix SVM task using a subset of the Imagewoof 2.0 dataset. With an effective dimension of over 50,000 and costly nuclear norm constraints, MOPES reached target accuracy using orders of magnitude fewer projections than standard PGD. Similarly, MOLES significantly outperformed existing Frank-Wolfe variants, reaching lower error rates with far fewer linear minimization steps.
Conclusion
MOPES and MOLES represent a significant advancement in nonsmooth optimization by breaking the projection bottleneck. While currently limited to Euclidean geometry and requiring knowledge of certain parameters like the Lipschitz constant ($G$), they pave the way for more efficient high-dimensional optimization. Future work may extend these techniques to general Bregman divergences and "$\epsilon$-horizon oblivious" implementations.
Summary updated