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

This paper introduces a novel Stochastic Successive Upper-bound Minimization (SSUM) method for tackling nonsmooth, nonconvex optimization problems, which are common in areas like wireless communication network design. SSUM offers a computationally efficient way to find good solutions by iteratively minimizing approximations of the objective function, and it's proven to converge to stationary points.

What Problem Does This Paper Address?

Many real-world optimization problems, especially in fields like wireless communications, involve objective functions that are both nonsmooth (meaning they have sharp corners or discontinuities) and nonconvex (meaning they have multiple local optima, making it hard to find the absolute best solution). A common approach to handle these is the Sample Average Approximation (SAA) method, which approximates the expected value of a function by averaging over a sample of random variables. However, SAA can be computationally very expensive because it requires solving a complex optimization problem at each step. This paper aims to bridge this gap by proposing a more efficient method, SSUM, that can handle these challenging optimization landscapes.

Methods

The core of this paper is the Stochastic Successive Upper-bound Minimization (SSUM) method. SSUM is an inexact version of the SAA method. Instead of minimizing the full sample average at each iteration, SSUM minimizes an approximate ensemble average. This approximation is crucial: it must be a "locally tight upper-bound" of the original function and, importantly, be easier to optimize. The authors provide a rigorous mathematical framework and prove that SSUM converges to a stationary point of the original problem, even for nonsmooth and nonconvex objectives. They also show how SSUM can be extended to handle problems with non-smooth components, making it more versatile.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic design, with numerical experiments presented to validate the proposed method.

Key Insights and Ideas

  • Bridging the Gap: SSUM effectively bridges the gap between computationally expensive SAA and simpler but potentially less accurate methods by introducing a clever approximation strategy.
  • Nonsmooth & Nonconvex Power: The SSUM framework is shown to be powerful enough to handle both nonsmoothness and nonconvexity simultaneously, which is a significant challenge in optimization.
  • Practical Applicability: The method is not just theoretical; it's demonstrated to be effective in practical applications like transceiver design in wireless networks, where these types of optimization problems are prevalent.
  • Stochastic Gradient Connection: The paper reveals that the traditional stochastic gradient (SG) method for smooth minimization is a special case of SSUM, providing a unifying perspective.

Key Results

The paper establishes the theoretical convergence of the SSUM algorithm to the set of stationary points of the optimization problem under certain assumptions. Numerical experiments are presented for the wireless network transceiver design problem, showing that the SSUM-based "Stochastic WMMSE" algorithm significantly outperforms other existing algorithms (like standard stochastic gradient) in terms of achievable ergodic sum rate. The paper also demonstrates the applicability of SSUM to online dictionary learning.

Limitations and Future Work

  • Boundedness Assumption: The theoretical convergence proof for SSUM relies on the feasible set $X$ being bounded. While the authors note that the result can still hold if the iterates remain within a bounded set, this is a practical consideration.
  • Assumption Requirements: The SSUM algorithm's convergence relies on specific assumptions about the approximation function (e.g., being a locally tight upper-bound and strongly convex). Satisfying these assumptions in practice might require careful design of the approximation.
  • Future Directions: The paper suggests extending the SSUM framework to other problems and exploring its use with different types of nonsmooth and nonconvex functions. The numerical experiments also hint at the potential for further performance improvements by exploring variations of the SSUM algorithm.

Summary updated

Abstract

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.
BibTeX
@article{razaviyayn2016stochastic,
  author = {Meisam Razaviyayn and Maziar Sanjabi and Zhi-Quan Luo},
  title = {{A Stochastic Successive Minimization Method for Nonsmooth Nonconvex Optimization with Applications to Transceiver Design in Wireless Communication Networks}},
  journal = {Math. Program.},
  year = {2016},
  doi = {10.1007/s10107-016-1021-7},
}
Figure