PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization

An Liu, Vincent Lau, Borna Kananian

arXiv:1801.08266v2cs.IT

TL;DR

The paper addresses non-convex stochastic optimization when both objectives and constraints involve expectations over random states. It proposes CSSCA, which alternates convex surrogate-based objective and feasibility updates, establishes stationary-point convergence under conditions, and supports parallel implementation for large-scale problems.

  • Problem

    Existing methods largely assume deterministic convex constraints, leaving stochastic non-convex constraints and large-scale parallel settings insufficiently addressed.

  • Method

    CSSCA replaces objective and constraint functions with convex surrogates, performing objective updates when feasible and feasibility updates otherwise.

  • Results

    Under technical conditions and a feasible initial point, CSSCA converges almost surely to a stationary point of the original problem.

  • Takeaways & Limitations

    Parallel CSSCA decomposes surrogate minimization into independent subproblems, supporting large-scale stochastic optimization in machine learning and signal processing.

Abstract

from arXiv · show

This paper proposes a constrained stochastic successive convex approximation (CSSCA) algorithm to find a stationary point for a general non-convex stochastic optimization problem, whose objective and constraint functions are non-convex and involve expectations over random states. Most existing methods for non-convex stochastic optimization, such as the stochastic (average) gradient and stochastic majorization-minimization, only consider minimizing a stochastic non-convex objective over a deterministic convex set. The proposed CSSCA algorithm can also handle stochastic non-convex constraints in optimization problems, and it opens the way to solving more challenging optimization problems that occur in many applications. The algorithm is based on solving a sequence of convex objective/feasibility optimization problems obtained by replacing the objective/constraint functions in the original problems with some convex surrogate functions. The CSSCA algorithm allows a wide class of surrogate functions and thus provides many freedoms to design good surrogate functions for specific applications. Moreover, it also facilitates parallel implementation for solving large scale stochastic optimization problems, which arise naturally in today's signal processing such as machine learning and big data analysis. We establish the convergence of CSSCA algorithm with a feasible initial point, and customize the algorithmic framework to solve several important application problems. Simulations show that the CSSCA algorithm can achieve superior performance over existing solutions.

I. INTRODUCTION

The paper targets non-convex stochastic optimization with expectation-based, non-convex constraints, where existing methods largely assume deterministic convex feasible sets. It introduces CSSCA, a convergent and parallelizable framework for broader problems and application settings.

  • Motivation: Stochastic optimization remains less mature than deterministic optimization, especially for large-scale problems requiring distributed computation.
  • Research gap: Existing non-convex stochastic optimization methods largely assume deterministic convex constraints, excluding expectation-based non-convex constraints.
  • Core contribution: CSSCA replaces non-convex objective and constraint functions with convex surrogate functions and targets stationary points of the original problem.
  • Convergence: The method establishes almost-sure convergence from a feasible initial point by combining asymptotic surrogate consistency with strong convexity.
  • Parallelization: Parallel CSSCA decomposes surrogate minimization into independent subproblems solved by computation nodes for large-scale machine-learning and signal-processing problems.
  • Applications: The framework is applied to wireless-communication problems, where application-specific surrogate design is identified as important.

III. CONSTRAINED STOCHASTIC SUCCESSIVE CONVEX APPROXIMATION

CSSCA addresses stochastic non-convex constraints by iteratively constructing convex surrogates and choosing between objective and feasibility updates. Under surrogate regularity and step-size conditions, the resulting method is designed to converge from a feasible starting point.

  • Challenges: The main challenges are maintaining almost-sure feasibility and stationarity when constraints are stochastic, non-convex, and difficult to evaluate accurately.
  • Surrogate construction: At each iteration, CSSCA updates convex surrogate functions using the current iterate and a newly observed random state.
  • Algorithm updates: If the surrogate convex approximation is feasible, the algorithm performs an objective update; otherwise, it performs a feasibility update minimizing constraint violations.
  • Step sizes: The step-size sequence decreases to zero while satisfying Σγ_t = ∞ and Σ(γ_t)^2 < ∞.
  • Implementation: Algorithm 1 initializes at a point in X, alternates surrogate-based optimization and feasibility handling, then updates the iterate before repeating.
  • Assumptions: Convergence requires surrogate functions with asymptotic consistency, strong convexity, Lipschitz continuity, and uniformly bounded derivatives.

1) Recursive Surrogate Function:

The recursive surrogate construction uses convex sample approximations and running updates to represent stochastic objective and constraint functions. Its flexible form includes common Lipschitz-gradient surrogates while allowing less restrictive designs.

  • Sample surrogate: A sample surrogate function is a strongly convex approximation of a stochastic function around the current iterate.
  • Consistency conditions: The surrogate matches the original function and gradient when its two iterate arguments coincide, while remaining Lipschitz and uniformly bounded under the stated assumptions.
  • Construction: A first-order surrogate combines the function value and gradient at y with a quadratic regularization term τ_i∥x−y∥^2.
  • Flexibility: Unlike the Lipschitz-gradient stochastic-MM surrogate, the proposed form does not require τ_i to be large enough to upper-bound the sample function, increasing design freedom.
  • Recursive update: The structured surrogate recursively updates approximations of expected function values and gradients using stochastic samples.
  • Structured design: Including a convex component of the original sample objective can reduce approximation error and potentially accelerate initial convergence.

3) Validity of the above Surrogate Functions:

The paper establishes validity conditions for recursive and structured surrogate functions, then proves CSSCA convergence under feasible initialization and regularity conditions. It also analyzes infeasible starts, deterministic specialization, and stochastic implementation trade-offs.

  • Surrogate validity: Under Assumptions 1, 4, and 5, the recursive surrogate functions satisfy Assumptions 2 and 3.This is stated as Proposition 1.
  • Surrogate validity: Under Assumption 5, the structured surrogate functions satisfy Assumptions 2 and 3.This is stated as Proposition 2.
  • Assumptions: The surrogate conditions required for convergence are Assumptions 1–3; Assumptions 4 and 5 ensure that the two example surrogates satisfy Assumption 3.The step-size conditions include a typical choice ρt = O(t^-κ1), γt = O(t^-κ2), with 0.5 < κ1 < κ2 ≤ 1.
  • Convergence challenges: CSSCA may require feasible updates because stochastic non-convex constraints can make iterates infeasible, complicating convergence analysis.The algorithm may oscillate between feasible and objective updates, while its limiting point averages outputs from both update types.
  • Convergence: Starting from a feasible point, every limiting point of Algorithm 1 is a stationary point almost surely when the Slater condition holds and the initial step size is sufficiently small.The paper notes that small initial steps are needed for the convergence proof, although simulations show practical convergence with larger initial steps.
  • Infeasible initialization: With an infeasible initial point, Algorithm 1 may converge either to a stationary point of the original problem or to an undesired stationary set.The feasible update can still yield a solution of the original problem unless the initial point is close to an undesired point; multiple random starts may help.
  • Implementation trade-offs: Using multiple state samples can reduce surrogate randomness and potentially iterations, but increases per-iteration complexity.This gives CSSCA a tunable trade-off between randomness and computational cost.

V. PARALLEL IMPLEMENTATION FOR DECOUPLED CONSTRAINTS

The paper distributes CSSCA across nodes when variables and constraints are partitioned into independent blocks. Surrogate updates, objective updates, constraint updates, and iterate updates then decompose into parallel subproblems.

  • Problem structure: The distributed formulation partitions x into K blocks, with the k-th constraint group depending only on block xk.Each group contains mk constraints, and the formulation includes multi-agent optimization problems as special cases.
  • Surrogate updates: Constraint surrogate updates for block xk can be performed distributively at node k.The construction uses recursively updated, block-decoupled sample surrogates for the constraint functions.
  • Objective update: The objective update decomposes into K independent subproblems that the K nodes solve in parallel.The objective surrogate is chosen in a decoupled form over the variable blocks.
  • Constraint and iterate updates: The constraint update likewise decomposes into K independent subproblems solved in parallel, with the global optimal value given by α = min_k αk.The combined solution is formed from the blockwise solutions, and each node optimizes its own block in the subsequent iterate update.

VI. APPLICATIONS

The applications section applies CSSCA to stochastic optimization problems in wireless systems and compares it with SAA and online primal-dual methods. In MIMO transmit signal design, CSSCA reaches the same feasible solution quality as SAA with substantially less CPU time.

  • CSSCA is applied to MIMO transmit signal design with imperfect CSI, where the objective is deterministic convex and the constraints are expected non-convex functions.
  • The proposed surrogate functions decompose each constraint into convex and non-convex components and linearize the non-convex component using its gradient.
  • CSSCA uses recursive calculations and observed channel-error samples to implement the surrogate updates for the MIMO problem.
  • CSSCA and SAA converge to the same average transmit power while satisfying all target average rates with high accuracy.
  • CSSCA requires much less CPU time than SAA to reach good convergence accuracy, while the online primal-dual method fails to converge properly and has much higher average transmit power.

B. Robust Beamforming Design

For robust beamforming, CSSCA smooths the chance constraint and constructs recursive convex surrogates for the resulting stochastic constraints. It achieves lower transmit power than the Bernstein baseline while retaining a similar feasibility rate.

  • The chance constraint is smoothed with a parameter-controlled approximation before being represented as an expected stochastic constraint.
  • CSSCA uses multiple system-state samples at each iteration to construct recursive sample surrogate functions for the beamforming variables.
  • CSSCA and Bernstein achieve similar feasibility rates, both slightly below the combined Bernstein-bisection method.
  • The combined method uses the lowest average transmit power, while CSSCA uses less average transmit power than Bernstein.
  • CSSCA supports arbitrary channel-estimation-error distributions, whereas the Bernstein methods are limited to Gaussian error distributions.

HF F HF F HHH

In massive MIMO hybrid beamforming, CSSCA and SAA attain the same sum rate with the average-power constraint satisfied accurately. CSSCA is more efficient and can update online as new channel samples arrive.

  • The convex subproblems for CSSCA can be solved using quadratic programming and Lagrange-dual methods with closed-form primal updates.
  • CSSCA and SAA converge to the same sum rate while satisfying the average-power constraint with high accuracy.
  • CSSCA is much more efficient than SAA, showing similar order-wise CPU-time differences across the application figures.
  • Unlike offline SAA, CSSCA updates the RF precoder whenever a new channel sample is obtained, avoiding the initial sample-collection phase.

APPENDIX

The appendix supplies probabilistic convergence tools used to establish the behavior of CSSCA's iterates. A key lemma shows that an auxiliary sequence and projected sequence asymptotically coincide almost surely under stated conditions.

  • Lemma 2 considers measurable vector sequences, projection onto a convex closed set, and step-size conditions governing their updates.
  • If all accumulation points of the auxiliary sequence lie in the feasible set almost surely and its normalized increments vanish, the projected sequence converges to it almost surely.
  • The paper uses Lemma 2 to prove a subsequent key lemma for the CSSCA convergence analysis.
  • The proof verifies the technical assumptions through Lipschitz continuity and error terms that vanish asymptotically.

B. Proof of Lemma 1

Under Assumption 2, the relevant function families are equicontinuous, bounded, and defined on compact X. Arzela–Ascoli then provides uniformly continuous limiting surrogate functions along a subsequence.

  • Assumption 2 makes the function families equicontinuous.
  • Boundedness and compact domain X enable an Arzela–Ascoli subsequence argument.
  • The subsequence yields uniformly continuous functions ˆf_i(x) satisfying (13), from which (14) follows via Lemma 3.

C. Proof of Theorem 1

Theorem 1’s proof establishes that Algorithm 1 remains in a suitable sublevel set, approaches feasibility, and ultimately yields a limiting point satisfying the original problem’s KKT conditions.

  • The algorithm converges toward feasibility, with the gap between the auxiliary and actual iterates vanishing almost surely.
  • Lemma 4 confines the iterates to a compact sublevel set disjoint from the infeasible region, almost surely.
  • For any limiting subsequence satisfying Slater’s condition, the surrogate KKT conditions transfer to the original problem.
  • The proof concludes that every relevant limiting point satisfies the KKT condition of Problem (1).

D. Proof of Lemma 4

Lemma 4 proves almost-sure feasibility convergence and shows that the auxiliary optimizer and current iterate asymptotically coincide. The proof combines constraint descent, strong convexity, and surrogate stability.

  • Whenever f(x_t) ≥ ε after a sufficiently large iteration, the constraint measure decreases almost surely.
  • The proof treats limiting subsequences through two convex optimization cases, using Slater’s condition to obtain KKT multipliers.
  • lim sup_t→∞ f(x_t) ≤ 0 almost surely, establishing asymptotic feasibility.
  • The auxiliary solution ̄x_t and iterate x_t satisfy lim_t→∞ ||̄x_t − x_t|| = 0 almost surely.
  • Strong convexity and Lipschitz continuity bound changes in the auxiliary optimizer when surrogate functions change.
Loading 1801.08266v2…