Source-linked AI summary
On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging
Angelia Nedich, Soomin Lee
TL;DR
The paper studies stochastic subgradient mirror descent for constrained convex minimization, using weighted averages of the generated iterates. It reports best-known rates in strongly convex and general convex settings, and almost-sure subsequential convergence to an optimum for a non-summable stepsize.
Problem
The paper addresses stochastic constrained convex minimization, where subgradients may be evaluated with random error.
Source: §2 · pp. 3–4Method
The method combines stochastic subgradient mirror descent with weighted averages whose weights are chosen in terms of stepsizes.
Source: §2 · pp. 4, 6Results
The method recovers best-known rates for strongly convex and convex objectives, and its averages converge along a subsequence almost surely to an optimum with a non-summable stepsize.
Source: §1 · pp. 2–3Takeaways & Limitations
The proposed weights recover known rates with simpler algorithms and yield a new almost-sure subsequential convergence result for a non-summable stepsize.
Source: §1 · pp. 2–3, §6 · p. 24For the time-varying-stepsize case, the general-convex analysis requires a compact constraint set.
Source: §4 · p. 18
Abstract
from arXiv · showhide
This paper considers stochastic subgradient mirror-descent method for solving constrained convex minimization problems. In particular, a stochastic subgradient mirror-descent method with weighted iterate-averaging is investigated and its per-iterate convergence rate is analyzed. The novel part of the approach is in the choice of weights that are used to construct the averages. Through the use of these weighted averages, we show that the known optimal rates can be obtained with simpler algorithms than those currently existing in the literature. Specifically, by suitably choosing the stepsize values, one can obtain the rate of the order $1/k$ for strongly convex functions, and the rate $1/\sqrt{k}$ for general convex functions (not necessarily differentiable). Furthermore, for the latter case, it is shown that a stochastic subgradient mirror-descent with iterate averaging converges (along a subsequence) to an optimal solution, almost surely, even with the stepsize of the form $1/\sqrt{1+k}$, which was not previously known. The stepsize choices that achieve the best rates are those proposed by Paul Tseng for acceleration of proximal gradient methods.
1 Introduction
The paper develops a simpler stochastic subgradient mirror-descent method with weighted iterate averaging, motivated by prior work on averaging for fast convex optimization. It recovers best-known rates in two settings and establishes almost-sure subsequential convergence for a non-summable stepsize.
1 Introduction
- The work builds on research showing that averaging can benefit fast gradient and subgradient algorithms for convex optimization.Related work includes averaging methods for smooth, strongly convex, and general convex objectives.Source: §1 · pp. 1–2
- For strongly convex objectives with convex, closed constraint sets, the averaging algorithm achieves the best-known rate of 1/k per iteration k, matching,, and with a simpler algorithm.Source: §1 · p. 2
- For convex objectives over a compact constraint set, the method also attains the best-known convergence rate.The paper considers convex objectives that need not be differentiable.Source: §1 · pp. 2–3
- The weighted averages converge along a subsequence almost surely to an optimal solution even with a non-summable stepsize.The paper presents this as new; prior results for non-summable stepsizes established convergence of function values in expectation only.Source: §1 · p. 3
2 Stochastic Subgradient Mirror-Descent Algorithm
This section formulates stochastic subgradient mirror descent for constrained convex minimization and introduces weighted averages of its iterates. The weights are tied to stepsizes, and a weighted expected Bregman distance motivates the convergence analysis.
2 Stochastic Subgradient Mirror-Descent Algorithm
- The analysis assumes a convex, closed constraint set, a convex objective continuous on that set, and stochastic subgradients satisfying a boundedness condition.The paper notes that uniformly bounded exact subgradients satisfy the condition; bounded subgradients with bounded errors are another sufficient case.Source: §2 · pp. 3, 6
- Mirror descent generalizes the standard subgradient method by replacing the Euclidean norm with a Bregman distance induced by a strongly convex function.The method uses an inexact, potentially random subgradient in its update.Source: §2 · pp. 4–5
- The method averages iterates using nonnegative weights summing to one, with the weights defined in terms of the stepsizes.The averaged iterates are byproducts rather than inputs to the algorithm.Source: §2 · pp. 5–6
- A weighted expected Bregman distance motivates the choice of iterate averages and serves as a Lyapunov function for measuring algorithmic progress.The stepsize controls the weighting of the expected distance.Source: §2 · p. 6
- The basic iterate relation holds almost surely under the stochastic-subgradient assumption and underpins the later convergence analysis.The paper applies it to strongly convex objectives and to convex objectives on bounded constraint sets.Source: §2 · pp. 6–7
3 Strongly Convex Objective Function
For strongly convex objectives, the paper analyzes stochastic subgradient mirror descent with weighted iterate averages under specified Bregman-distance and stepsize conditions. It establishes optimal-order convergence rates for the averages and almost-sure convergence under the stated assumptions.
3 Strongly Convex Objective Function
- The guarantees assume a strongly convex objective, Assumption 1, and a Bregman distance satisfying property (13).The theorem uses either of two stepsize sequences; the paper notes these choices have no tunable parameters.Source: §3 · pp. 8, 11
- 1/k: the weighted averages achieve the optimal expected-distance convergence rate for stochastic subgradient methods on strongly convex functions.The averages also have bounds for expected distance and expected function values.Source: §3 · pp. 12–13
- The method obtains the optimal rate more simply than, while avoiding the sliding-window averaging used in.The paper notes that its result is less general than because it does not simultaneously handle objectives with Lipschitz gradients.Source: §3 · p. 12
- Under Theorem 1’s assumptions, both the iterates and their weighted averages converge almost surely to the optimal point.The argument also shows that the averages converge because they are convex combinations of iterates.Source: §3 · pp. 13–14
4 Compact Constraint Set
For compact constraint sets, weighted iterate averaging with a time-varying stepsize achieves the optimal O(1/k) expected function-value rate for general convex objectives. The averaged sequence also has almost-sure subsequential convergence to optimality, while compactness is required for the time-varying-stepsize analysis.
4 Compact Constraint Set
- The method averages iterates generated by stochastic subgradient mirror-descent, with bounded subgradients and stochastic-error conditions imposed for the compact-set analysis.The averages are byproducts of the algorithm rather than inputs to its updates.Source: §4 · p. 14
- The expected function value at the weighted average achieves the best-known O(1/k) rate for convex, potentially nondifferentiable objectives.The result assumes a compact constraint set and uses a time-varying stepsize.Source: §4 · p. 17
- Compactness is required for the time-varying-stepsize result; with a fixed iteration horizon and constant optimal stepsize, it is not needed.The paper motivates compactness by the need to ensure bounded iterates under the decreasing stepsize.Source: §4 · p. 18
- With no stochastic errors, every accumulation point of the weighted averages is optimal, although the raw iterates are not guaranteed to have optimal accumulation points.The stepsize αk = a/√(k+1) does not meet the standard conditions cited for convergence of the raw iterates.Source: §4 · pp. 18–19
- Almost surely, the weighted averages approach the optimal value and solution set along subsequences.The result concerns the averages, not necessarily convergence of every iterate.Source: §4 · p. 19
5 Numerical Results
The experiments compare SSMD with other methods on strongly convex and general convex utility-minimization instances. Performance is similar overall, with differences across instances and early-iteration behavior.
5 Numerical Results
- Four test instances share n = 100 and u = 10 but differ in R; SSMD and comparison algorithms were evaluated over 100 independent Monte-Carlo runs.Table 1 includes detailed descriptions of the instances and their corresponding initial points.Source: §5 · p. 21
5.1 Strongly Convex Objective Function
- After about 20 iterations, SSMD and AC-SA show almost the same performance; step-2 SSMD is slower initially when initial points are nonzero.The comparison uses average objective values over 100 Monte-Carlo runs.Source: §5.1 · p. 22
5.2 Compact Constraint Set
- Across the compact-set tests, the three methods perform similarly overall, with SSMD best on Tests 1–2 and AC-SA better on Test 4.PD performs better than SSMD and AC-SA on Test 4; its performance is also described as not very sensitive to initial points and problem instances.Source: §5.2 · pp. 23–24
6 Conclusion
The paper analyzes stochastic subgradient mirror-descent using weighted averages of its iterates. It reports best-known rates for strongly convex and convex objectives, new convergence properties for a stepsize proportional to 1/√(k+1), and simulations with behavior similar to accelerated stochastic subgradient and primal-dual averaging methods.
6 Conclusion
- Weighted iterate averages recover the best-known rates for strongly convex and convex functions, with new convergence properties for stepsizes proportional to 1/√(k+1).Simulations show behavior similar to accelerated stochastic subgradient and the primal-dual averaging method of Nestrov.Source: §6 · pp. 24–25