# Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems

Source: [Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems](<https://www.sota2.com/research/paper/68fa50e71e209131ce96f636>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T11:07:30.842Z

Authors: Niao He, Anatoli Juditsky, Arkadi Nemirovski

Published: 2013-11-05T15:54:35.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Personalized PageRank on bio-CE-HT](<https://www.sota2.com/research/sota/personalized-pagerank-on-bio-ce-ht.md>): Personalized PageRank; bio-CE-HT; Execution Time: 370.5.

- [Personalized PageRank on bio-CE-LC](<https://www.sota2.com/research/sota/personalized-pagerank-on-bio-ce-lc.md>): Personalized PageRank; bio-CE-LC; Execution Time: 4.74.

- [Personalized PageRank on econ-beaflw](<https://www.sota2.com/research/sota/personalized-pagerank-on-econ-beaflw.md>): Personalized PageRank; econ-beaflw; Execution Time: 116.13.

- [Personalized PageRank on DD242](<https://www.sota2.com/research/sota/personalized-pagerank-on-dd242.md>): Personalized PageRank; DD242; Execution Time: 79.16.

- [Personalized PageRank on DD68](<https://www.sota2.com/research/sota/personalized-pagerank-on-dd68.md>): Personalized PageRank; DD68; Time: 67.73.

- [Personalized PageRank on peking-1](<https://www.sota2.com/research/sota/personalized-pagerank-on-peking-1.md>): Personalized PageRank; peking-1; Execution Time: 243.45.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1311.1098>)

[PDF](<https://arxiv.org/pdf/1311.1098.pdf>)