Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method

Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh

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":

  1. First-order Oracle (FO): Provides a direction to move (a subgradient).
  2. 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

Comparison of oracle complexities for MOPES (top) and MOLES (bottom) against prior state-of-the-art and theoretical lower bounds.

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

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 eps-suboptimality in high-dimensions, O(1/eps^2) FO calls are necessary. This is achieved by the projected subgradient method (PGD). However, PGD also entails O(1/eps^2) PO calls, which may be computationally costlier than FO calls (eg 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 eps-suboptimal solution using only O(1/eps) PO calls and optimal O(1/eps^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 eps-suboptimal solution using O(1/eps^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.
BibTeX
@inproceedings{thekumparampil2020projection,
  author = {Kiran Koshy Thekumparampil and Prateek Jain and Praneeth Netrapalli and Sewoong Oh},
  title = {{Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=slKn9WUXuo},
}
Figure