Mirror descent and nonlinear projected subgradient methods for convex optimization.

DOI10.1016/S0167-6377(02)00231-6MaRDI QIDQ1811622zbMATH OpenFDO

Authors Amir Beck, Marc Teboulle

Publication date 17 June 2003

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0167-6377(02)00231-6

zbMATH Keywords

Complexity analysisconvergenceGlobal rate ofMirror descent algorithmsNonlinearNonsmooth convex minimizationProjected subgradient methodsprojectionsRelative entropy

Mathematics Subject Classification ID

Convex programming (90C25) Methods of reduced gradient type (90C52)

Recommendations

• Mirror descent and convex optimization problems with non-smooth inequality constraints
• Mirror descent and constrained online optimization problems
• Algorithms of inertial mirror descent in stochastic convex optimization problems
• Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
• Unifying mirror descent and dual averaging

Cites work

• An Interior Proximal Algorithm and the Exponential Multiplier Method for Semidefinite Programming
• An iterative row-action method for interval convex programming
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Entropic Proximal Mappings with Applications to Nonlinear Programming
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• scientific article; zbMATH DE number 3365044 (Why is no real title available?)
• Incremental subgradient methods for nondifferentiable optimization
• Monotone Operators and the Proximal Point Algorithm
• On the Optimum Rate of Transmitting Information
• Proximal Minimization Methods with Generalized Bregman Functions
• The ordered subsets mirror descent optimization method with applications to tomography
• Variational Analysis

Cited in

(only showing first 100 items - show all)

• Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities
• Subgradient methods for saddle-point problems
• Primal-dual subgradient methods for convex problems
• Optimal distributed stochastic mirror descent for strongly convex optimization
• Algorithms of inertial mirror descent in convex problems of stochastic optimization
• A simplified view of first order methods for optimization
• A fast dual proximal gradient algorithm for convex minimization and applications
• Stochastic mirror descent method for distributed multi-agent optimization
• Generalized mirror descents with non-convex potential functions in atomic congestion games: continuous time and discrete time
• Iterative regularization via dual diagonal descent
• Scale-free online learning
• Distributed constrained optimization via continuous-time mirror design
• Learning in games with continuous action sets and unknown payoff functions
• Level-set methods for convex optimization
• Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
• An efficient approach to solve the large-scale semidefinite programming problems
• On the convergence time of a natural dynamics for linear programming
• Inertial alternating generalized forward-backward splitting for image colorization
• Point process estimation with Mirror Prox algorithms
• Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
• Mirror descent and constrained online optimization problems
• Natural gradient for combined loss using wavelets
• A Laplacian approach to _1-norm minimization
• Fastest rates for stochastic mirror descent methods
• Infinite-dimensional gradient-based descent for alpha-divergence minimisation
• Inverse reinforcement learning in contextual MDPs
• Acceptable set topic modeling
• Curiosities and counterexamples in smooth convex optimization
• A distributed Bregman forward-backward algorithm for a class of Nash equilibrium problems
• Network manipulation algorithm based on inexact alternating minimization
• On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
• Interior quasi-subgradient method with non-Euclidean distances for constrained quasi-convex optimization problems in Hilbert spaces
• Optimal complexity and certification of Bregman first-order methods
• Sparse optimization on measures with over-parameterized gradient descent
• Global convergence of model function based Bregman proximal minimization algorithms
• Hessian informed mirror descent
• Laplacian-optimized diffusion for semi-supervised learning
• Multi-view clustering via multi-manifold regularized non-negative matrix factorization
• Large-scale distributed sparse class-imbalance learning
• Mirror descent algorithms for minimizing interacting free energy
• Near-optimal discrete optimization for experimental design: a regret minimization approach
• A gradient descent perspective on Sinkhorn
• Bundle methods for sum-functions with ``easy components: applications to multicommodity network design
• Projected subgradient minimization versus superiorization
• Convergence of online mirror descent
• Mass-spring-damper networks for distributed optimization in non-Euclidean spaces
• Multi-manifold matrix decomposition for data co-clustering
• A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, variance reduction, and variational bounds
• Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
• Optimal subgradient methods: computational properties for large-scale linear inverse problems
• A telescopic Bregmanian proximal gradient method without the global Lipschitz continuity assumption
• On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity
• Analysis of singular value thresholding algorithm for matrix completion
• Quasi-monotone subgradient methods for nonsmooth convex minimization
• On the efficiency of a randomized mirror descent algorithm in online optimization problems
• On risk concentration for convex combinations of linear estimators
• A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs
• Mirror descent and convex optimization problems with non-smooth inequality constraints
• An optimal subgradient algorithm with subspace search for costly convex optimization problems
• A simple convergence analysis of Bregman proximal gradient algorithm
• Convergence of the exponentiated gradient method with Armijo line search
• Augmented Lagrangian method with alternating constraints for nonlinear optimization problems
• Recursive aggregation of estimators by the mirror descent algorithm with averaging
• Nonmonotone projected gradient methods based on barrier and Euclidean distances
• Interior projection-like methods for monotone variational inequalities
• Solving variational inequalities with monotone operators on domains given by linear minimization oracles
• A penalty algorithm for solving convex separable knapsack problems
• Zeroth-order feedback optimization for cooperative multi-agent systems
• Perturbed Fenchel duality and first-order methods
• Event-triggered distributed online convex optimization with delayed bandit feedback
• A subgradient method based on gradient sampling for solving convex optimization problems
• A family of subgradient-based methods for convex optimization problems in a unifying framework
• Learning in games via reinforcement and regularization
• Subgradient and bundle methods for nonsmooth optimization
• Comparing different nonsmooth minimization methods and software
• Stochastic block mirror descent methods for nonsmooth and stochastic optimization
• Projection algorithms for nonconvex minimization with application to sparse principal component analysis
• A dual method for minimizing a nonsmooth objective over one smooth inequality constraint
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Limited memory discrete gradient bundle method for nonsmooth derivative-free optimization
• New results on subgradient methods for strongly convex optimization problems with a unified analysis
• A weighted mirror descent algorithm for nonsmooth convex optimization problem
• Techniques for gradient-based bilevel optimization with non-smooth lower level problems
• Generalized mirror descents in congestion games
• Problems of differential and topological diagnostics. II: Problem of differential diagnostics
• Problems of differential and topological diagnostics. III: The checking problem
• Block coordinate proximal gradient methods with variable Bregman functions for nonsmooth separable optimization
• The cyclic block conditional gradient method for convex optimization problems
• A derivative-free comirror algorithm for convex optimization
• Training effective node classifiers for cascade classification
• Accelerated training of max-margin Markov networks with kernels
• An incremental mirror descent subgradient algorithm with random sweeping and proximal step
• Re-examination of Bregman functions and new properties of their divergences
• A survey of algorithms and analysis for adaptive online learning
• Distributed Bayesian learning with stochastic natural gradient expectation propagation and the posterior server
• Efficient sampling from time-varying log-concave distributions
• scientific article; zbMATH DE number 6860836 (Why is no real title available?)
• Generalized conditional gradient for sparse estimation
• An alternating extragradient method with non Euclidean projections for saddle point problems
• A generalized online mirror descent with applications to classification and regression

This page was built for publication: Mirror descent and nonlinear projected subgradient methods for convex optimization.

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