Primal-dual subgradient methods for minimizing uniformly convex functions

By Anatoli Iouditski, Yurii E. Nesterov. 2010

92 citations recorded by the source corpus.

We discuss non-Euclidean deterministic and stochastic algorithms for optimization problems with strongly and uniformly convex objectives. We provide accuracy bounds for the performance of these algorithms and design methods which are adaptive with respect to the parameters of strong or uniform convexity of the objective: in the case when the total number of iterations $N$ is fixed, their accuracy coincides, up to a logarithmic in $N$ factor with the accuracy of optimal algorithms.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Adaptive Sensitive Reweighting to Mitigate Bias in Fairness-aware Classification (2018, background): “Convex functions, such as exp(βip), are Lipschitz-continuous in bounded sets [22].”
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2011, methodology): “To get the optimalO(1/T ) rate for any F , we might turn to the algorithms of [3] and [5].”
Linear Convergence with Condition Number Independent Access of Full Gradients (2013, methodology): “Compared to the optimization algorithms that only rely on stochastic gradients [9,10,21], EMGD is more efficient since it achieves a linear convergence rate.”
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization (2011, unknown): “It has been brought to our attention that Juditsky and Nesterov (2010) have recently published a technical report that has a very similar algorithm to ours, and also obtain an O( 1 T ) convergence rate.”
Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization (2010, background): “For a given tolerance δ ∈ (0 , ], we deﬁne, for each vertex α ∈ V , the function Depending on the result to be proven, our choice of the base functions { f + i , f − i } and the pre-factor c will ensure that each g α satisﬁes the appropriate Lipschitz and/or strong convexity properties over S .”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, background): “In the case of non-smooth and strongly convex, several works improve the results following from online regret bounds with a O ( 1 / T ) convergence rate (Hazan & Kale, 2014; Ghadimi & Lan, 2012; Iouditski & Nesterov, 2014).”
Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms (2013, background): “By the classic complexity theory for convex programming (see, e.g., Theorems 5.3.1 and 7.2.6 of [14], Theorem 2.1.13 of [16], [26] and [6]), to ﬁnd an (cid:15) -solution of (1.1), i.e., a point ¯ x ∈ X s.t.”