Mirror descent and nonlinear projected subgradient methods for convex optimization

By Amir Beck, Marc Teboulle. 2003

1,404 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Mathematical Optimization

Citations in the corpus

Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, background): “…Euclidean settings [61, 60] (where we wish to privatize vectors belonging to (cid:96) 2 balls) and the highly non-Euclidean scenarios that arise in high-dimensional estimation and optimization, e.g. mirror descent settings [60, 14] (where we wish to privatize vectors belonging to (cid:96) ∞ balls).”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, background): “The update (14) is in-fact a mirror descent update (Nemirovski and Yudin, 1978; Beck and Teboulle, 2003) using the potential function h i , and step size η .”
Smoothness, Low Noise and Fast Rates (2010, methodology): “A classic algorithm for this setting is Mirror Descent [4], which starts at some arbitrary w 1 ∈ W and updates w i +1 according to z i and a stepsize η (to be discussed later) as follows: For the Euclidean norm with F ( w ) = w 2 , the update (12) becomes projected online gradient descent [34]: wher”
GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values (2020, background): “Mirror descent (Beck & Teboulle, 2003) with generalized KL-divergence is also a possible way to ensure positivity, which works well in the tabular setting as Θ is a positive orthant.”
Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods (2019, background): “Therefore, while ideally one can apply standard first-order optimization algorithms, such as mirror descent [28], with the random estimate G to optimize policies, this often is not viable in practice.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “where gt is a (possibly stochastic) subgradient of the convex function to be minimized, DΦ is a Bregman divergence, D is a convex set and η > 0 is a stepsize (Nemirovski and Yudin, 1983; Beck and Teboulle, 2003).”
Hybrid Deterministic-Stochastic Methods for Data Fitting (2011, background): “The more general class of mirror-descent meth-ods [1], which are useful for problems with a certain geometry such as optimization with simplex constraints, also seem amenable to analysis in our controlled error scenario.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “This viewpoint was pio- 86 Linear bandits neered by Beck and Teboulle [2003] —see also Bartok et al. [2011] for more details.”
Natural Neural Networks (2015, methodology): “Our second contribution is in unifying many heuristics commonly used for training neural networks, under the roof of the natural gradient, while highlighting an important connection between model reparametriza-tions and Mirror Descent [3].”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “, [5], [31]–[33]).”
Structured Prediction Energy Networks (2015, background): “By learning the measurement matrix C 1 from data, the practitioner imposes minimal assumptions a-priori on the interaction structure between the labels, but can model sophisticated interactions by feeding C 1 ¯ y through a non-linear function.”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, background): “Proof Mirror descent (Nemirovski and Yudin, 1983; Beck and Teboulle, 2003) dates back to 1983, but this particular statement is taken from Lemma 2 of Srebro et al. (2011).”
Computational Optimal Transport (2018, background): “The best know example is mirror gradient descent [Beck and Teboulle, 2003], which is an explicit descent step of the form (9.”
A unified view of entropy-regularized Markov decision processes (2017, methodology): “A direct application of the Mirror Descent algorithm (Nemirovski and Yudin, 1983; Beck and Teboulle, 2003; Martinet, 1978; Rockafellar, 1976) to our case is deﬁned as where D R is the Bregman divergence associated with the convex regularization function R .”
Meta-Learning with Warped Gradient Descent (2019, background): “As noted by Desjardins et al. (2015), expressing preconditioning through interleaved projections can be seen as a form of Mirror Descent (Beck & Teboulle, 2003).”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “Mirror descent, ﬁrst introduced by Nemirovski & Yudin (1983), is one of the most widely used families of algorithms for optimization (Beck & Teboulle, 2003; Cesa-Bianchi et al., 2012; Zhou et al., 2017), which includes the popular gradient descent as a special case.”
Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization (2010, background): “Given stochastic mirror descent based on unbiased estimates of the gradient, it can be showed that (see e.g., Chapter 5.1 of NY [5] or Beck and Teboulle [23]) with the initialization x0 = argminx∈SΦ(x) and stepsizes ηt = 1/ √ t, the optimization error of the sequence {xt} is bounded as 1 T T∑ t=1 E ”