Source-linked AI summary
Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
Cong D. Dang, Guanghui Lan
TL;DR
Existing stochastic approximation can make large-scale problems costly when computing Bx requires O(n2) arithmetic operations. This paper introduces stochastic block mirror descent and establishes convergence rates for several convex and nonconvex stochastic optimization problems.
Problem
For problems F(x, ξ) = ψ(Bx, ξ), existing stochastic approximation requires O(n2) arithmetic operations to compute Bx, becoming prohibitive when n exceeds 10^6.
Source: §1 · p. 2Method
SBMD combines block-coordinate updates along partial stochastic subgradients with incremental block averaging, using randomized output selection for a nonconvex variant.
Source: §1 · p. 2, §2.1 · p. 5, §4 · p. 20Results
The paper establishes O(b/ϵ2) iterations for general nonsmooth convex problems and O(b/ϵ) for strongly convex problems, alongside rates or complexity bounds for smooth, composite, and nonconvex variants.
Source: §1 · pp. 2–3, §5 · p. 25Takeaways & Limitations
SBMD's iteration cost can be considerably smaller than mirror descent's, and total arithmetic cost can be comparable or smaller when its per-iteration cost is lower by O(b).
Source: §2.2 · p. 8, §5 · p. 25The composite-convex variant's treatment of stochastic noise assumes bounds parameterized by σ_i ≥ 0.
Source: §3 · p. 14
Abstract
from arXiv · showhide
In this paper, we present a new stochastic algorithm, namely the stochastic block mirror descent (SBMD) method for solving large-scale nonsmooth and stochastic optimization problems. The basic idea of this algorithm is to incorporate the block-coordinate decomposition and an incremental block averaging scheme into the classic (stochastic) mirror-descent method, in order to significantly reduce the cost per iteration of the latter algorithm. We establish the rate of convergence of the SBMD method along with its associated large-deviation results for solving general nonsmooth and stochastic optimization problems. We also introduce different variants of this method and establish their rate of convergence for solving strongly convex, smooth, and composite optimization problems, as well as certain nonconvex optimization problems. To the best of our knowledge, all these developments related to the SBMD methods are new in the stochastic optimization literature. Moreover, some of our results also seem to be new for block coordinate descent methods for deterministic optimization.
1. Introduction.
The paper introduces stochastic block mirror descent (SBMD), combining block-coordinate updates with incremental averaging to reduce iteration cost relative to mirror descent. It establishes convergence and complexity results for nonsmooth, strongly convex, composite, and nonconvex stochastic optimization.
1.1. Notation and terminology.
- The feasible set is a Cartesian product of closed convex blocks, with the block dimensions summing to the full dimension.This is the structure that permits block-coordinate updates.Source: §1 · p. 1
1. Introduction.
- Existing BCD methods mainly address deterministic problems, while sample-average approximation can require substantial memory and sample-dependent cost, and stochastic approximation updates the whole vector.These trade-offs motivate a stochastic method that also exploits block updates.Source: §1 · pp. 1–2
- SBMD incorporates block-coordinate decomposition into mirror descent, updating one randomly selected block along a stochastic (sub)gradient.The paper also introduces incremental block averaging, which updates only one block of the weighted sum per iteration.Source: §1 · p. 2
- For general nonsmooth convex problems, SBMD reaches an ǫ-solution in O(b/ǫ^2) iterations, or O(b/ǫ) when the objective is strongly convex.The paper also derives associated large-deviation results.Source: §1 · p. 2
- For smooth convex composite problems, modified SBMD improves complexity bounds’ dependence on gradient Lipschitz constants, with further improvement under strong convexity.For possibly nonconvex composite problems, a randomized output scheme supports complexity analysis for generating an approximate stationary point.Source: §1 · pp. 2–3
- The authors report new block-coordinate descent results for deterministic nonsmooth convex problems, including large-deviation bounds and O(b/ǫ) complexity for strongly convex cases.They also state that nonconvex BCD complexity had not been studied in the literature to their knowledge.Source: §1 · p. 3
2. The SBMD methods for nonsmooth convex optimization.
This section presents SBMD’s single-block stochastic updates and incremental block averaging, and establishes convergence and large-deviation guarantees for general and strongly convex nonsmooth problems. It also discusses iteration bounds for two parameter choices, including how domain shrinking can improve the strongly convex bound.
2.1. The SBMD algorithm for nonsmooth problems.
- SBMD updates one block using a partial stochastic subgradient and incrementally averages updated blocks; recursive gradient updates can reduce an example’s per-iteration cost from O(n^2) to O(n).The example’s cost can be reduced further when the data vector and matrix are sparse.Source: §2.1 · pp. 5–6
2.2. Convergence properties of SBMD for nonsmooth problems.
- For general nonsmooth convex problems, SBMD provides convergence and epsilon-solution iteration bounds; total arithmetic cost is comparable to or below mirror descent when each SBMD iteration costs O(b) less.The bounded-domain parameter setting differs from one that also applies to unbounded domains or unavailable block bounds.Source: §2.2 · p. 8
2.3. Convergence properties of SBMD for nonsmooth strongly convex problems.
- For strongly convex nonsmooth problems, under quadratic growth of the prox-functions and uniform block sampling, SBMD has an epsilon-solution iteration bound comparable to the optimal bound up to factor b.The paper states that such complexity results had not previously been obtained for block-coordinate-descent methods.Source: §2.3 · pp. 8, 10
2.4. Large-deviation properties of SBMD for nonsmooth problems.
- The large-deviation results cover general nonsmooth and strongly convex problems under a light-tail assumption, uniform block sampling, and a bounded feasible set.The paper notes that the light-tail assumption holds for deterministic problems with bounded subgradients.Source: §2.4 · pp. 10–11
- Under boundedness of X and assumptions (2.44) and (2.30), Corollary 2.7 gives probability bounds for general nonsmooth and strongly convex problems with their respective parameter choices.The bounds apply for any x ∈ X and λ > 0.Source: §2.4 · p. 12
- The iteration count for finding an (ε, λ)-solution is bounded for general nonsmooth problems, and the paper reports no prior such large-deviation results for BCD on general nonsmooth CP problems.Similar results had been established for smooth or some composite problems.Source: §2.4 · p. 13
- For nonsmooth strongly convex problems, the iteration bound is about the same as for nonsmooth problems without convexity, but domain shrinking can improve it to O(log(1/λ)/ε).The improvement is given as an example using a domain shrinking procedure.Source: §2.4 · p. 13
3. The SBMD algorithm for convex composite optimization.
The section develops a smooth/composite variant of SBMD and analyzes it for convex stochastic composite problems, both with and without strong convexity. Proper parameter choices improve the convergence bound’s dependence on gradient Lipschitz constants.
3. The SBMD algorithm for convex composite optimization.
- The variant exploits smoothness in convex composite stochastic problems, with a block-separable nonsmooth component and stochastic gradient estimates.The analysis also assumes Lipschitz-continuous gradients and, for stated results, the specified prox-function growth conditions.Source: §3 · pp. 13–14
- Properly choosing the step sizes, weights, and block probabilities improves the rate’s dependence on the gradient Lipschitz constants.Compared with directly applying Algorithm 1, the resulting bound allows the Lipschitz constant to be as large as O(√N) without affecting it, up to other constant factors.Source: §3 · pp. 14, 17
- Theorem 3.1 assumes Algorithm 2 indices are uniformly distributed and sequences γk and θk meet its stated conditions; under Assumptions (1.3) and (3.6), the result holds for any N ≥ 2.Source: §3 · p. 15
- For strongly convex composite problems, Theorem 3.3 and Corollary 3.4 provide convergence results under strong convexity and quadratic-growth assumptions.The section further states that the Lipschitz constant can be as large as O(√N) without affecting the rate, up to other constant factors.Source: §3 · pp. 17–19
4. SBMD Algorithm for nonconvex composite optimization.
For composite problems with a possibly nonconvex smooth component, the section introduces randomized output selection for SBMD and establishes convergence guarantees. It also gives deterministic and stochastic specializations, with the stochastic sample-complexity bound comparable up to a factor b^2 to bounds for methods without block decomposition.
4. SBMD Algorithm for nonconvex composite optimization.
- The composite projected gradient provides a first-order measure for evaluating candidate solutions in general nonconvex composite problems.For unconstrained problems with no nonsmooth term, it reduces to the ordinary gradient.Source: §4 · pp. 19–20
- Randomly selecting an iterate from the trajectory avoids computing the full gradient at every iteration, which can be expensive for large n.The section’s nonconvex setting retains a convex, separable nonsmooth component and quadratic-growth prox-functions.Source: §4 · pp. 19–20
- Theorem 4.3 establishes an expected convergence guarantee for the randomized output under the algorithm’s assumptions.The expectation is over block choices, stochastic gradients, and the random output index.Source: §4 · p. 22
- The deterministic and stochastic corollaries specialize the convergence result; the stochastic case uses uniformly sampled blocks and a fixed-size mini-batch.The supplied passages omit the displayed convergence bounds.Source: §4 · p. 24
- The stochastic sample-complexity bound is comparable, up to a factor b^2, to bounds for nonconvex stochastic methods without block decomposition.The paper notes that associated large-deviation results could be derived, but skips their development because it is more involved.Source: §4 · p. 25
5. Conclusions.
The conclusion reiterates SBMD’s convergence analyses across convex and nonconvex stochastic optimization and identifies contributions that also apply to deterministic block coordinate descent.
5. Conclusions.
- The paper presents SBMD variants for convex stochastic optimization and a randomized-output variant for nonconvex stochastic composite optimization, establishing convergence rates and worst-case complexity.The authors also identify new averaging/randomization schemes, large-deviation results, and analyses for deterministic block coordinate descent.Source: §5 · p. 25