Source-linked AI summary
A Stochastic Successive Minimization Method for Nonsmooth Nonconvex Optimization with Applications to Transceiver Design in Wireless Communication Networks
Meisam Razaviyayn, Maziar Sanjabi, Zhi-Quan Luo
TL;DR
SAA can be expensive because it requires minimizing an ensemble average at each step. The paper proposes SSUM, which minimizes locally tight upper-bound approximations, and reports better ergodic sum-rate performance for stochastic wireless beamforming while establishing convergence results.
Problem
SAA requires minimizing an ensemble average at each iteration, which can be expensive, especially when the subproblem is nonconvex or nonsmooth.
Source: §1 · p. 2Method
SSUM minimizes an approximate ensemble average using locally tight upper-bound approximations, and the paper analyzes its convergence and applies the framework to wireless design and online dictionary learning.
Source: §1 · p. 2Results
For stochastic wireless beamforming, experiments indicate SSUM significantly outperforms existing algorithms in achievable ergodic sum rate; the paper also extends SG convergence to nonsmooth nonconvex objectives.
Source: §1 · p. 3Takeaways & Limitations
The paper establishes SSUM convergence and shows its use in wireless sum-rate maximization and online dictionary learning.
Source: §1 · p. 2The convergence analysis relies on regularity and boundedness assumptions, including boundedness of the feasible set or of the iterates.
Source: §2 · p. 5
Abstract
from arXiv · showhide
Consider the problem of minimizing the expected value of a cost function parameterized by a random variable. The classical sample average approximation (SAA) method for solving this problem requires minimization of an ensemble average of the objective at each step, which can be expensive. In this paper, we propose a stochastic successive upper-bound minimization method (SSUM) which minimizes an approximate ensemble average at each iteration. To ensure convergence and to facilitate computation, we require the approximate ensemble average to be a locally tight upper-bound of the expected cost function and be easily optimized. The main contributions of this work include the development and analysis of the SSUM method as well as its applications in linear transceiver design for wireless communication networks and online dictionary learning. Moreover, using the SSUM framework, we extend the classical stochastic (sub-)gradient (SG) method to the case of minimizing a nonsmooth nonconvex objective function and establish its convergence.
1 Introduction
SAA can be costly when its per-iteration subproblem is nonsmooth or nonconvex, motivating SSUM, which minimizes locally tight upper-bound approximations. The paper analyzes SSUM and applies it to wireless sum-rate maximization and online dictionary learning, while extending stochastic gradient methods to nonsmooth nonconvex objectives.
1 Introduction
- SAA can be difficult and expensive because each step may require solving a nonconvex or nonsmooth subproblem.The paper addresses this by minimizing an approximation of the random cost at each step.Source: §1 · p. 2
- SSUM minimizes locally tight upper-bound approximations of each sampled cost, extending successive upper-bound minimization to stochastic optimization.The paper also establishes SSUM convergence and applies the framework to wireless sum-rate maximization and online dictionary learning.Source: §1 · p. 2
- For stochastic wireless beamforming, experiments indicate SSUM significantly outperforms existing algorithms in achievable ergodic sum rate, and the framework extends SG convergence to nonsmooth nonconvex objectives.The paper also identifies the traditional SG method for unconstrained smooth minimization as a special case of SSUM.Source: §1 · p. 3
2 Stochastic Successive Upper-bound Minimization
SSUM updates the iterate by minimizing an average of approximations that are locally tight upper bounds, with conditions imposed to support convergence. Under the stated assumptions, its iterates converge almost surely to stationary points.
2 Stochastic Successive Upper-bound Minimization
- SSUM replaces each sampled cost with an approximation around the preceding iterate and minimizes the resulting ensemble average.The approximation must match the original function at the expansion point, upper-bound it locally, and yield a uniformly strongly convex surrogate.Source: §2 · pp. 4–5
- The convergence analysis requires regularity and boundedness assumptions, and the surrogate can be chosen strongly convex even when the original smooth component is nonconvex.The authors state that the assumptions can be met in many cases through an appropriate approximation function.Source: §2 · p. 5
- Under Assumptions A and B, SSUM iterates converge almost surely to the set of stationary points of the expected objective.The theorem's stated assumptions include boundedness conditions; the authors note that bounded iterates suffice in place of a bounded feasible set.Source: §2 · pp. 6, 8
3 Applications: Transceiver Design and Online Dictionary Learning
The section applies SSUM to expected sum-rate maximization in wireless networks and online dictionary learning. Its wireless experiments favor Stochastic WMMSE, while the dictionary-learning application depends on stated uniqueness and boundedness assumptions.
3.1 Expected Sum-Rate Maximization for Wireless Networks
- Stochastic WMMSE directly maximizes ergodic sum rate, is fully distributed, and has per-iteration complexity comparable to the deterministic counterpart [20].Its updates for P=(W,U,Z) are closed form, while the V update uses a one-dimensional search; two recursively updated matrices encode the information needed for precoder updates.Source: §3.1 · pp. 9, 12
- The stochastic formulation maximizes expected network sum rate using partial channel estimates for selected links and statistical models for the remaining links.The approach addresses the practical difficulty of obtaining full, rapidly changing channel-state information at base stations.Source: §3.1 · pp. 8, 10
3.2 Numerical Experiments
- Stochastic WMMSE significantly outperforms one-sample WMMSE, mean WMMSE, and stochastic gradient in expected sum rate in the 3%-estimated-channel experiment.Diminishing-step stochastic gradient was sensitive to step-size selection and usually slow; constant step sizes typically led to divergence.Source: Figure 1 · p. 14, §3.2 · p. 14
- Figure 2 compares expected sum rate over iterations at η=12, when about 6% of the channels are estimated.The remaining channels are represented using path-loss information and Rayleigh fading.Source: §3.2 · pp. 13–14, Figure 2 · p. 15
3.3 Online Dictionary Learning
- SSUM applies to online dictionary learning under uniqueness and boundedness assumptions, and its sparse formulation with γ=0 recovers the algorithm in [40].The boundedness conditions apply to the feasible dictionary set and signal vectors.Source: §3.3 · pp. 15–16
4 Stochastic (Sub-)Gradient Method and its Extensions
The section places stochastic gradient methods within the SSUM framework, showing that several classical methods are special cases and extending the framework to nonsmooth nonconvex objectives. It also describes diminishing-step-size updates and an auxiliary-iterate update for nonsmooth objectives.
4 Stochastic (Sub-)Gradient Method and its Extensions
- SSUM encompasses the classical stochastic gradient, incremental gradient, and stochastic sub-gradient methods as special cases.The section also presents an extension of these methods using the SSUM framework.Source: §4 · p. 16
- For finite sample sets, incremental gradient uses a randomly selected sample per iteration, making updates cheaper than batch gradients when the set is large.The incremental method is the SG algorithm applied to the empirical expectation.Source: §4 · pp. 16–17
- An SSUM variant can be interpreted as stochastic gradient with diminishing step sizes, while constant-step SG may diverge even for a convex objective.With the stated constant choice of α_i = L, the step size is γ_r = 1/(rL).Source: §4 · p. 17
- For a nonsmooth objective with deterministic g2(x), the SSUM update differs from classical stochastic sub-gradient methods.The objective considered is E[g1(x, ξ)] + g2(x).Source: §4 · p. 18
- Under Theorem 1’s assumptions, the SSUM update guarantees convergence for nonconvex nonsmooth objectives, including when g2(x) = λ∥x∥1.For this l1 example, the update uses a soft-shrinkage operator.Source: §4 · p. 18
Appendix
The appendix develops the convergence proof using quasi-martingale arguments, a zero-one law, and bounds derived from the stated assumptions. The supplied passages report almost-sure convergence and identify a first-order optimality condition used in the proof.
Appendix
- The proof invokes the quasi-martingale convergence theorem to establish convergence of the stochastic process.The appendix describes this proof strategy as similar to that used for online learning algorithms.Source: Appendix · pp. 18, 20
- The appendix reports almost-sure convergence of the iterates and uses a first-order optimality condition because each iterate minimizes the corresponding surrogate.The proof also invokes assumptions B3 and B5 in bounding successive surrogate values.Source: Appendix · pp. 19, 22
- The Hewitt-Savage zero-one law turns the permutable event into a probability-one event in the convergence argument.The appendix combines this with a Markov-inequality bound.Source: Appendix · pp. 20–21