Semi-Proximal Mirror-Prox for Nonsmooth Composite Minimization

Niao He, Zaïd Harchaoui

In high-dimensional machine learning, optimizing composite problems—where the objective function mixes a non-smooth loss (like a hinge loss) with a non-smooth regularizer (like the nuclear norm)—often forces a difficult computational trade-off. As dimensionality grows, standard mathematical toolkits struggle to keep up.

A new paper by Niao He and Zaid Harchaoui, "Semi-Proximal Mirror-Prox for Nonsmooth Composite Minimization," introduces a clever hybrid algorithm designed to navigate these high-dimensional hurdles without breaking the computational bank.

TL;DR

The authors propose Semi-Proximal Mirror-Prox (Semi-MP), a first-order optimization algorithm that handles complex, non-smooth composite problems by combining proximal operators with faster linear minimization oracles (LMOs). It achieves the optimal $O(1/\epsilon^2)$ convergence rate while avoiding the expensive singular value decompositions (SVDs) that plague traditional methods in high dimensions.

The Bottleneck in High-Dimensional Optimization

Many machine learning tasks, such as robust collaborative filtering or link prediction, involve minimizing a function like $F(x) = f(x) + \|Bx\|$. Here, $f(x)$ is a loss function and $\|Bx\|$ is a regularization penalty.

The challenge arises when both parts are non-smooth. Traditionally, practitioners use proximal gradient methods. These work well if the "proximal operator" (a specific kind of optimization sub-step) is cheap to compute. But for penalties like the matrix nuclear norm, the proximal operator requires a full SVD at every single iteration. In high dimensions, this becomes a massive bottleneck.

The alternative is the Frank-Wolfe (conditional gradient) algorithm, which uses a Linear Minimization Oracle (LMO). LMOs are much cheaper—for a nuclear norm, an LMO only needs the top singular vector, not a full SVD. However, standard Frank-Wolfe methods struggle with the "composite" structure where a linear mapping $B$ is involved.

The Semi-Proximal Mirror-Prox Method

The authors bridge this gap with a hybrid approach. Their key innovation is the Semi-Proximal Mirror-Prox algorithm, which operates through four main steps:

  1. Saddle Point Reformulation: The non-smooth objective is transformed into a smooth convex-concave saddle point problem, making the math more tractable for first-order methods.
  2. The "Semi-Proximal" Split: The algorithm recognizes that some variables might be "prox-friendly" (easy to compute proximal steps for), while others are "LMO-friendly" (better suited for linear minimization). It splits the domain and applies the appropriate tool to each part.
  3. Inexact Prox-mappings: Because computing an exact proximal step for the LMO-friendly part is too computationally expensive, the algorithm uses an inner loop—the Composite Conditional Gradient (CCG)—to find an approximate solution.
  4. Mirror-Prox Framework: This is all wrapped in a Mirror-Prox framework, known for its stability and optimal convergence rates in saddle-point problems.

Key Insights and Theoretical Guarantees

  • Best of Both Worlds: You don't have to choose between the precision of proximal methods and the speed of LMOs. By decomposing the problem, Semi-MP uses proximal steps where they are cheap and LMOs where they save the most time.
  • Optimal Complexity: The paper proves that even with "inexact" inner steps, the algorithm still hits the theoretical speed limit ($O(1/\epsilon^2)$ calls to the LMO) for this class of non-smooth problems.
  • Handling the Linear Map $B$: Unlike previous conditional gradient methods that ignore the composite structure, Semi-MP handles non-trivial linear mappings $B$ directly through its saddle-point setup.

Experimental Results

The authors evaluated their algorithm on two main tasks: robust collaborative filtering using the MovieLens dataset (utilizing a nuclear norm penalty and an $\ell_1$-loss) and link prediction using the Wikivote social network graph (involving hinge loss, $\ell_1$-norm, and nuclear norm penalties).

Superior Speed

In the MovieLens experiments, Semi-MP significantly outperformed "Smooth-CG" (a smoothing-based conditional gradient method) in terms of elapsed time to reach a target objective value. It also proved highly competitive with Semi-Proximal Stochastic Proximal Gradient (Semi-SPG) methods.

Objective value vs. Elapsed time for Semi-MP and baselines

Robustness to Inner Accuracy

On the Wikivote dataset, Semi-MP demonstrated strong resilience to the accuracy of its inner-loop calculations. Compared to ADMM-based variants (Semi-LPADMM)—which often stalled if the inner steps weren't solved precisely enough—Semi-MP continued to converge reliably.

Objective value vs. LMO calls comparing Semi-MP and Semi-LPADMM

Limitations and Future Work

While powerful, the method does have limitations:

  • Saddle Point Requirement: The approach relies on the objective function having a "favorable" saddle point representation. While most ML losses have this, it requires an extra analytical step in the modeling process.
  • Hyperparameter Tuning: Like many advanced optimization methods, parameters (such as the inner loop accuracy $\epsilon_t$) may require tuning for peak performance on new datasets.
  • Stochastic Extension: The current paper focuses on the deterministic (full-batch) setting. Extending this framework to stochastic or online settings remains a promising direction for future research.

Summary updated

Abstract

We propose a new first-order optimization algorithm to solve high-dimensional non-smooth composite minimization problems. Typical examples of such problems have an objective that decomposes into a non-smooth empirical risk part and a non-smooth regularization penalty. The proposed algorithm, called Semi-Proximal Mirror-Prox, leverages the saddle point representation of one part of the objective while handling the other part of the objective via linear minimization over the domain. The algorithm stands in contrast with more classical proximal gradient algorithms with smoothing, which require the computation of proximal operators at each iteration and can therefore be impractical for high-dimensional problems. We establish the theoretical convergence rate of Semi-Proximal Mirror-Prox, which exhibits the optimal complexity bounds for the number of calls to linear minimization oracle. We present promising experimental results showing the interest of the approach in comparison to competing methods.
BibTeX
@inproceedings{he2015semi,
  author = {Niao He and Zaïd Harchaoui},
  title = {{Semi-Proximal Mirror-Prox for Nonsmooth Composite Minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=espw-nwObBH},
}
Figure