Mirror Prox algorithm for multi-term composite minimization and semi-separable problems

DOI10.1007/S10589-014-9723-3zbMATH Open1321.65105arXiv1311.1098OpenAlexW2154319048WikidataQ57392873 ScholiaQ57392873MaRDI QIDQ2350862FDOQ2350862

Authors: Niao He, Anatoli Juditsky, Arkadi Nemirovski 

Publication date: 25 June 2015

Published in: Computational Optimization and Applications (Search for Journal in Brave)

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 $el{l}_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(epsilo{n}^{-1})$ complexity bounds.

Full work available at URL: https://arxiv.org/abs/1311.1098

Recommendations

• Mirror-Descent Methods in Mixed-Integer Convex Optimization
• Large-scale semidefinite programming via a saddle point mirror-prox algorithm
• The multiproximal linearization method for convex composite problems
• A proximal multiplier method for separable convex minimization
• Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle
• A proximal method for composite minimization
• Mirror descent and convex optimization problems with non-smooth inequality constraints
• A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
• A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
• PARTIAL PROXIMAL METHOD OF MULTIPLIERS FOR CONVEX PROGRAMMING PROBLEMS

zbMATH Keywords

algorithmsnuclear norm regularizationproximal methodsvariational problemsminimization problemscomplexity boundcomposite optimizationalternating directions methodmonotone variational inequalitiesconvex-concave saddle point problemslasso-type problemmulti-term penalty

Mathematics Subject Classification ID

Convex programming (90C25) Complexity and performance of numerical algorithms (65Y20) Large-scale problems in mathematical programming (90C06) Minimax problems in mathematical programming (90C47) Variational inequalities (49J40) Numerical methods for variational inequalities and related problems (65K15)

Cites Work

• NESTA: A fast and accurate first-order method for sparse recovery
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Smooth minimization of non-smooth functions
• Robust principal component analysis?
• Gradient methods for minimizing composite functions
• Fast alternating linearization methods for minimizing the sum of two convex functions
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• A Review of Image Denoising Algorithms, with a New One
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Dual norms and image decomposition models
• Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
• New variants of bundle methods
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Accuracy certificates for computational problems with convex structure
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Alternating Projection-Proximal Methods for Convex Programming and Variational Inequalities
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• Fast multiple-splitting algorithms for convex optimization
• Modelling of landslides with the material-point method
• Fast first-order methods for composite convex optimization with backtracking
• Structured sparsity via alternating direction methods
• An accelerated linearized alternating direction method of multipliers

Cited In (18)

• Efficient proximal point algorithm for convex composite optimization
• Optimal subgradient methods: computational properties for large-scale linear inverse problems
• Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization
• A primal-dual algorithm with line search for general convex-concave saddle point problems
• Point process estimation with Mirror Prox algorithms
• Proximal primal-dual best approximation algorithm with memory
• A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints
• A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems
• On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
• Mirror-Descent Methods in Mixed-Integer Convex Optimization
• Complementary composite minimization, small gradients in general norms, and applications
• A unified approach for minimizing composite norms
• Optimal convergence rates for convex distributed optimization in networks
• Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems
• The multiproximal linearization method for convex composite problems
• A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
• Accelerated gradient sliding for structured convex optimization
• A distributed ADMM-like method for resource sharing over time-varying networks

Uses Software

• CVX
• Mosek
• NESTA

This page was built for publication: Mirror Prox algorithm for multi-term composite minimization and semi-separable problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350862)