Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions

By Gong-hwai Chen, Marc Teboulle. 1993

How researchers see this paper

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

Citations in the corpus

Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “To prove Theorem 9 and Theorem 10 we need the following standard Lemma, which can be found in Chen and Teboulle (1993), Lan et al.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, methodology): “ the last inequality used (z) x(k+ 1) + s(k+ 1);z x(k+ 1) + 2 z x(k+ 1) 2; by the (strong) convexity of . We now use the following well-known three point identity of the Bregman distance function [43] to rewrite the left-hand side of (8): r!(a) r !(b);c b = D !(a;b) D !(a;c) + D !(b;c): From this ”
A Modern Introduction to Online Learning (2019, background): “=1 x iln x i y i , that is the Kullback-Leibler divergence between the discrete distributions xand y. We also have the following lemma that links the Bregman divergences between 3 points. Lemma 6.6 ([Chen and Teboulle, 1993]). Let B the Bregman divergence w.r.t. : X!R. Then, for any three points x;y”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, background): “This function was studied by Bregman [24] and many others; see [8,11,33,48,70,132] and references therein.”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, unknown): “Lemma 3 (Three Point Property (Bubeck, 2015; Orabona, 2019)) .”
Network optimization : continuous and discrete models (1998, methodology): “Literature surveys are given by Dreyfus [1969], Deo and Pang [1984], and Gallo and Pallottino [1988]. The latter reference also contains codes for the most popular shortest path methods, and extensive computational comparisons.”
Solving variational inequalities with monotone operators on domains given by Linear Minimization Oracles (2013, background): “Observe that the optimality conditions in the optimization problem specifying v = Prox y (ξ) imply that which, using a remarkable identity [5] V y (v), z − v (cid:9) = V y ( z ) − V v ( z ) − V y (v), can be rewritten equivalently as”
Interior Gradient and Proximal Methods for Convex and Conic Optimization (2006, methodology): “As we shall see below, the requested properties for the function H associated with d naturally emerge from the analysis of the classical PA as given in [24] and later extended for various speciﬁc classes of IPA in [16, 44, 5].”
Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems (2004, methodology): “The prox-method with general prox-term (“with Bregman distances”) for convex minimization and solving variational inequalities was investigated in many papers (see [4, 16, 6] and references therein).”
Coordinate descent with arbitrary sampling I: algorithms and complexity† (2014, unknown): “3 ([2, 43]).”
Learning in games with continuous action sets and unknown payoff functions (2016, background): “10) This so-called “reciprocity condition” is well known in the theory of Bregman functions [1,9,20]: essentially, it means that the sublevel sets of D(p, ·) are neighborhoods of p inX .”
An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization (2016, unknown): “Using the well-known three point identity of the Bregman distance function [45], we have”
A Lyapunov Analysis of Momentum Methods in Optimization (2016, methodology): “…these minor modifications, the algorithm can be understood as the explicit Euler method applied to (13a) and the implicit Euler method applied to (13b) (where now we take eβt = Ak+1, while leaving our identification for d dte βt unchanged): Algorithm 2 The Quasi-Monotone (Sub)gradient Method γk ≡…”
An introduction to continuous optimization for imaging (2016, methodology): “Convergence of these algorithms under various conditions on ψ are studied in a few important papers; see in particular the papers of Eckstein (1993), Teboulle (1992), Chen and Teboulle (1993), Kiwiel (1997), Beck and Teboulle (2003) and Auslender and Teboulle (2004).”