Abstract
This paper introduces two novel algorithms, MOPES and MOLES, designed to significantly reduce the computational burden of constrained nonsmooth optimization. By strategically applying Moreau-Yosida smoothing and "gradient sliding," the authors achieve the first-ever reduction in the number of expensive projection calls—from $\mathcal{O}(\epsilon^{-2})$ to $\mathcal{O}(\epsilon^{-1})$—and resolve a long-standing open question regarding the optimal complexity of Frank-Wolfe style methods for nonsmooth problems.
The Bottleneck in Nonsmooth Optimization
In convex optimization, a common objective is to minimize a function $f(x)$ subject to specific constraints (e.g., ensuring $x$ remains within a defined set $\mathcal{X}$). For "nonsmooth" functions—those featuring sharp kinks, such as absolute values or matrix norms—the standard algorithmic tool is the Projected Subgradient Method (PGD).
To reach a solution with an error margin of $\epsilon$, PGD typically requires $\mathcal{O}(\epsilon^{-2})$ calls to two distinct "oracles":
- First-order Oracle (FO): Provides a direction to move (a subgradient).
- Projection Oracle (PO): Pulls the solution back into the constraint set if it wanders out.
While the number of FO calls is mathematically optimal, the number of PO calls represents a major computational bottleneck. In many modern machine learning applications, such as collaborative filtering or structural SVMs, the projection step (which might involve a full Singular Value Decomposition) is orders of magnitude more computationally expensive than calculating a gradient. The central question this paper addresses is: Can we achieve the same optimization accuracy using fewer projections?
Methods: Smoothing and Sliding
The authors propose a two-pronged approach grounded in Moreau-Yosida regularization. This technique "smooths out" a bumpy nonsmooth function by approximating it with a differentiable surrogate known as the Moreau envelope.
MOPES (MOreau Projection Efficient Subgradient)
Instead of minimizing the original nonsmooth function directly, MOPES minimizes its Moreau envelope. The critical innovation here is the application of Gradient Sliding. By splitting the problem into a composite form, the authors ensure that the constraint set only interacts with the smooth part of the approximation.
This decoupling allows the algorithm to "slide" past many potential projection steps. As a result, MOPES reduces the required PO calls to $\mathcal{O}(\epsilon^{-1})$ while maintaining the optimal $\mathcal{O}(\epsilon^{-2})$ FO calls.
MOLES (MOreau Linear minimization oracle Efficient Subgradient)
In some scenarios, even a standard projection is computationally prohibitive, prompting the use of a Linear Minimization Oracle (LMO) instead (often referred to as the "Frank-Wolfe" approach). MOLES extends the logic of MOPES to the LMO setting. It successfully achieves $\mathcal{O}(\epsilon^{-2})$ LMO calls, marking a significant improvement over previous methods whose complexities scaled poorly with the dimension ($d$) of the problem.
Theoretical Contributions
The theoretical gains of MOPES and MOLES are substantial:
- Dimension Independence: Unlike previous "randomized smoothing" attempts that introduced factors of $d^{1/4}$ or $\sqrt{d}$ into the complexity bounds, both MOPES and MOLES are dimension-free. This makes them highly practical for high-dimensional machine learning tasks.
- Resolving an Open Question: Since 1993, researchers have debated whether a Frank-Wolfe type method could achieve optimal complexity for general nonsmooth functions. MOLES provides an affirmative answer, perfectly matching the theoretical lower bounds for LMO complexity.
Empirical Results
The authors evaluated their methods on a Matrix Support Vector Machine (SVM) problem to ensure the theoretical gains translated to empirical performance.
- Setup: The dataset was a subset of Imagewoof 2.0, consisting of 400 grayscale images (224x224 pixels). The task was binary classification where weights were constrained by a nuclear norm ball (radius $r=0.1$). This specific constraint is notorious for its expensive projection step (full SVD).
- Projection Efficiency: In the Matrix SVM experiments, MOPES required significantly fewer PO calls than standard PGD to reach the same level of sub-optimality.
- LMO Efficiency: MOLES outperformed the state-of-the-art "Randomized Frank-Wolfe" (RandFW) and FW-PGD baselines, achieving better accuracy with fewer linear minimization calls.
- Stability: Both methods demonstrated robust performance even when utilizing stochastic gradients (SFO), a critical requirement for training on large-scale datasets.
Limitations and Future Work
While MOPES and MOLES represent significant leaps forward, the authors note a few limitations and avenues for future research:
- Neighborhood Assumption: The methods require the objective function $f$ to remain Lipschitz continuous in a small neighborhood outside the constraint set. While generally true in practice, this is a slightly stricter mathematical requirement than standard PGD.
- Euclidean Focus: The current theoretical analysis is tied to the Euclidean norm. Extending these results to general Bregman divergences (useful for non-Euclidean geometries) remains an open challenge, as the smoothness properties of Moreau envelopes are less understood in those spaces.
- Parameter Tuning: The algorithms currently require prior knowledge of the target accuracy $\epsilon$ and the Lipschitz constant $G$. Developing "$\epsilon$-oblivious" versions that do not require these inputs upfront is a promising direction for future work.
Summary updated