Mirror Prox Algorithm for Multi-Term Composite Minimization and Alternating Directions

Niao He, Anatoli B. Juditsky, Arkadi NemirovskiarXiv 2013 · arXiv · OpenReview

TL;DR

This paper introduces a "composite" version of the Mirror Prox algorithm designed to efficiently solve complex optimization problems involving multiple non-smooth penalty terms. The new algorithm maintains the optimal convergence rate of its predecessor while handling these challenging composite structures, making it applicable to a wider range of real-world problems in machine learning and signal processing.

What Problem Does This Paper Address?

Many modern optimization problems, particularly in areas like machine learning, image restoration, and signal processing, involve minimizing an objective function that is a sum of several components. These components often include "smooth" functions (whose derivatives are well-behaved) and "non-smooth" functions (which might have sharp corners or kinks, like L1-norm regularization). Traditional optimization methods struggle when these non-smooth components are combined in complex ways, especially when there are multiple such terms. The paper specifically targets "multi-term composite minimization" and "semi-separable" problems, which are common formulations that are difficult to solve efficiently with existing tools. The challenge is to develop an algorithm that can handle these composite structures without sacrificing the optimal convergence rates achieved for simpler problems.

Methods

The core contribution is a Composite Mirror Prox (CoMP) algorithm. This is an extension of the well-established Mirror Prox algorithm. The key innovation lies in how CoMP handles the non-smooth terms. Instead of treating them as separate, difficult-to-optimize components, CoMP effectively "moves" these non-smooth terms into the problem's domain definition. This clever reformulation allows the algorithm to process the problem as if it were a smooth saddle-point problem, thereby avoiding the direct optimization of the non-smooth parts. This is achieved by defining new, augmented domains that implicitly incorporate the non-smooth functions. The algorithm then leverages the structure of the problem, particularly a specific form of the monotone operator, to maintain the optimal $O(1/t)$ convergence rate, which is theoretically the best possible for first-order methods in this setting.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and demonstrates its application to well-known problem structures. Numerical experiments are conducted on synthetic data generated to represent these problem structures.

Key Insights and Ideas

  • "Moving" non-smoothness into the domain: The most significant insight is the reformulation of composite optimization problems by implicitly incorporating non-smooth terms into the definition of the feasible set. This allows a smooth optimization framework to be applied.
  • Leveraging problem structure: The algorithm's efficiency hinges on exploiting the specific structure of the monotone operator, which arises from the problem's formulation. This structure allows the algorithm to "ignore" the non-smooth components during the core optimization steps.
  • Theoretical optimality preserved: The CoMP algorithm successfully inherits the optimal $O(1/t)$ convergence rate from the original Mirror Prox algorithm, even when dealing with more complex composite objective functions. This is a crucial theoretical guarantee.

Key Results

The paper presents theoretical convergence guarantees for the CoMP algorithm, showing it achieves an $O(1/t)$ rate for solving multi-term composite minimization and semi-separable problems. This rate is shown to be unimprovable for large-scale problems. The authors demonstrate the algorithm's applicability to:

  • Lasso-type problems: Problems involving combinations of $\ell_1$ and nuclear norm regularization.
  • Semi-separable structures: Problems relevant to alternating direction methods.

Numerical experiments on matrix completion and image decomposition tasks show that CoMP exhibits fast convergence, achieving high accuracy within a reasonable number of iterations and computational time, often outperforming standard solvers. For instance, in the matrix completion example, CoMP achieved relative accuracies of $1.1 \times 10^{-3}$ and $6.2 \times 10^{-6}$ in just 64 and 4096 steps, respectively, significantly faster than a state-of-the-art interior-point solver.

Limitations and Future Work

The authors acknowledge that the "exact penalty" approach used to ensure the algorithm's properties might involve conservative penalty parameters that could be adjusted online. They also note that while the algorithm achieves optimal theoretical rates, practical performance can still depend on the specific problem instance and the choice of proximal setups. Future work could explore more adaptive strategies for parameter tuning and investigate the algorithm's performance on a broader range of real-world applications. The paper also suggests extensions to handle more general structures and potentially improve practical efficiency.

Summary updated

Abstract

In the paper, we develop a composite version of Mirror Prox algorithm for solving convex-concave saddle point problems and monotone variational inequalities of special structure, allowing to cover saddle point/variational analogies of what is usually called "composite minimization" (minimizing a sum of an easy-to-handle nonsmooth and a general-type smooth convex functions "as if" there were no nonsmooth component at all). We demonstrate that the composite Mirror Prox inherits the favourable (and unimprovable already in the large-scale bilinear saddle point case) $O(1/\epsilon)$ efficiency estimate of its prototype. We demonstrate that the proposed approach can be naturally applied to Lasso-type problems with several penalizing terms (e.g. acting together $\ell_1$ and nuclear norm regularization) and to problems of the structure considered in the alternating directions methods, implying in both cases methods with the $O(\epsilon^{-1})$ complexity bounds.
BibTeX
@misc{he2013mirror,
  author = {Niao He and Anatoli B. Juditsky and Arkadi Nemirovski},
  title = {{Mirror Prox Algorithm for Multi-Term Composite Minimization and Alternating Directions}},
  year = {2013},
  eprint = {1311.1098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1311.1098},
}

Loading related content...

Figure