PaperlayerView exact revision on arXiv

Source-linked AI summary

Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications

Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, Yongxin Chen

arXiv:1902.08294v2math.OCstat.ML

TL;DR

Existing min-max theory largely targets special convex-concave structures, limiting guidance for signal-processing and communication problems with non-convexity. The paper proposes HiBSA for one-sided non-convex min-max problems, using alternating descent and ascent steps with regularization and penalty sequences, and reports convergence and effective numerical performance in robust learning and wireless communication problems.

  • Problem

    Existing analyses for successive approximation methods rely on consistent descent, whereas min-max problems require ascent steps for the inner maximization, especially in non-convex SPCOM settings.

  • Method

    HiBSA alternates gradient descent-type updates for multiple non-convex minimization blocks with gradient ascent-type updates for a concave maximization problem, stabilized by regularization and penalty sequences.

  • Results

    HiBSA converges to properly defined first-order stationary solutions with quantifiable global rates and effectively solves robust learning and wireless communication min-max problems in numerical tests.

  • Takeaways & Limitations

    The results support HiBSA as an effective algorithmic approach for one-sided non-convex min-max problems arising in robust machine learning and wireless communications.

Abstract

from arXiv · show

The min-max problem, also known as the saddle point problem, is a class of optimization problems which minimizes and maximizes two subsets of variables simultaneously. This class of problems can be used to formulate a wide range of signal processing and communication (SPCOM) problems. Despite its popularity, most existing theory for this class has been mainly developed for problems with certain special convex-concave structure. Therefore, it cannot be used to guide the algorithm design for many interesting problems in SPCOM, where various kinds of non-convexity arise. In this work, we consider a block-wise one-sided non-convex min-max problem, in which the minimization problem consists of multiple blocks and is non-convex, while the maximization problem is (strongly) concave. We propose a class of simple algorithms named Hybrid Block Successive Approximation (HiBSA), which alternatingly perform gradient descent-type steps for the minimization blocks and gradient ascent-type steps for the maximization problem. A key element in the proposed algorithm is the use of certain regularization and penalty sequences, which stabilize the algorithm and ensure convergence. We show that HiBSA converges to some properly defined first-order stationary solutions with quantifiable global rates. To validate the efficiency of the proposed algorithms, we conduct numerical tests on a number of problems, including the robust learning problem, the non-convex min-utility maximization problems, and certain wireless jamming problem arising in interfering channels.

I. INTRODUCTION

The paper studies one-sided non-convex min-max problems motivated by SPCOM applications, where the minimization variables are block-wise non-convex and the maximization variable is concave. Existing convex-concave theory and specialized heuristics do not cover many such problems.

  • Problem formulation: The generic saddle problem minimizes over multiple blocks x_i and maximizes over y on convex feasible sets.The objective combines a continuously differentiable function with convex, possibly non-smooth terms.
  • Problem formulation: One-sided non-convexity means f(x,y) is non-convex in x but (strongly) concave in y.
  • SPCOM applications: The framework captures distributed non-convex optimization with heterogeneous non-smooth regularizers and partial-consensus constraints.These features fall outside assumptions used by several existing distributed non-convex optimization methods.
  • SPCOM applications: Applications include robust learning over multiple domains, power control, coordinated MISO beamforming, and wireless jamming.The robust-learning formulation accounts for the worst distribution over domains, while wireless formulations involve non-convex rates and jammer power allocation.
  • SPCOM applications: For general multi-channel or MIMO interference channels, the corresponding optimization problem is NP-hard and available heuristics often target special cases.Approximation procedures can also introduce significant rate losses.
  • Research gap: Convex-concave min-max methods do not directly guide algorithms for the non-convex setting considered here.Only limited prior work addresses non-convex min-max problems under specialized assumptions or formulations.

C. Contribution of this work

The paper proposes HiBSA, a block-alternating successive-approximation method for one-sided non-convex min-max problems, and develops convergence guarantees for several problem classes. Regularization and penalty sequences address instability introduced by alternating descent and ascent updates.

  • Algorithm: HiBSA updates minimization variables block by block using approximation functions and updates the maximization variable with an ascent step.The method is designed for objectives allowing non-convexity, non-smoothness, and nonlinear variable coupling.
  • Problem classes: The paper studies three min-max problem classes distinguished by variable coupling and whether the y problem is strongly concave or merely concave.
  • Algorithm: The block successive-approximation strategy supports effective subproblem solution and integration of minimization algorithms such as BSUM.
  • Theory: The paper rigorously analyzes alternating block successive approximation for one-sided non-convex min-max problems and provides convergence guarantees with specified stationarity criteria.The supplementary material includes an alternative double-loop algorithm for concave maximization.
  • Stabilization: Regularization and penalty sequences are selected to stabilize the method and establish convergence, including for concave but not strongly concave maximization problems.The proximal term is motivated by an unstable gradient descent-ascent example.
  • Stabilization: Without the stabilizing terms, alternating gradient descent-ascent can fail because the associated linear dynamics are unstable.For almost any randomly generated A, the iterates do not converge to a point satisfying ATy*=0 and Ax*=0.

III. THEORETICAL PROPERTIES OF HIBSA

HiBSA uses first-order stationarity conditions for non-convex one-sided min-max problems and relates them to established formulations. These conditions support equivalence results for KKT-based and smooth reformulations.

  • HiBSA targets first-order stationary solutions because non-convexity prevents using distance to a saddle point as the classical optimality measure.
  • The stationarity condition reduces to ordinary first-order stationarity when the regularizers and maximization block are absent.
  • For concave maximization blocks, the condition is connected to projected-gradient stationarity, while strong concavity yields an O(ε) relation to another criterion.
  • Problems (2) and (3) are equivalent: their KKT points and first-order stationary solutions correspond in both directions.
  • The min-utility maximization formulation and its smooth reformulation have the same first-order stationary solutions.

B. Convergence analysis: f(x, y) strongly concave in y

For objectives strongly concave in y, HiBSA is analyzed through descent estimates and a decreasing potential function. Under the stated assumptions and parameter conditions, the analysis yields a convergence guarantee.

  • B. Convergence analysis: f(x, y) strongly concave in y: The strongly concave-y case is analyzed separately using descent lemmas for the x and y updates.
  • B. Convergence analysis: f(x, y) strongly concave in y: The jamming problem is stated to satisfy the strong-concavity assumption used in this convergence analysis.
  • B. Convergence analysis: f(x, y) strongly concave in y: A potential function is introduced to combine the descent properties of the block updates.
  • B. Convergence analysis: f(x, y) strongly concave in y: Theorem 1 gives a convergence guarantee for HiBSA when γr = 0 and βr = β > 0 under Assumptions A, B, and C-1.

C. Convergence analysis: f(x, y) concave in y

When f is concave but not strongly concave in y, HiBSA uses diminishing regularization for the y update and increasing penalties for the x updates. This strategy addresses the analytical difficulty caused by absent strong concavity and supports a convergence result under parameter conditions.

  • C. Convergence analysis: f(x, y) concave in y: Without strong concavity in y, directly alternating gradient-type updates may fail to converge to interesting solutions.
  • C. Convergence analysis: f(x, y) concave in y: HiBSA regularizes the y update with diminishing γr and the x updates with increasing βr.
  • C. Convergence analysis: f(x, y) concave in y: The regularized y update maximizes a strongly concave version of the objective, making that subproblem relatively easy despite f being merely concave in y.
  • C. Convergence analysis: f(x, y) concave in y: A descent lemma and a consistently decreasing potential function support the convergence analysis under the stated assumptions.
  • C. Convergence analysis: f(x, y) concave in y: Theorem 2 provides a convergence guarantee when Assumptions A, B, C-2, and C-3 hold, with γr satisfying the required sequence conditions.
  • C. Convergence analysis: f(x, y) concave in y: For the generic objective, the exact strongly concave maximization step may lack a closed-form solution; a finite-gradient-ascent extension is provided in supplementary material.

D. Convergence analysis: f(x, y) linear in y

For the linear-in-y case, the strongly concave approximation enables a simple gradient update for y while retaining HiBSA’s convergence analysis. Numerical experiments apply HiBSA to robust learning, jammer power control, and coordinated beamforming.

  • The linear-in-y formulation includes robust learning, min-utility maximization, and the paper’s Example 1 as special cases.
  • Strong concavity of the approximation function Uy enables a simple gradient step for y instead of solving a y-subproblem at every iteration.
  • HiBSA retains a convergence guarantee under Assumptions A, B, C-3, and C-4, with T(ε) defined as in Theorem 1.
  • Robust learning over multiple domains: On MNIST, HiBSA, multistep GDA, and multitask learning achieve approximately the same test accuracy.
  • Power control in the presence of a jammer: In the jammer experiment, HiBSA converges after initial oscillation to a lower sum-rate and effectively reduces the system’s total sum rate.

APPENDIX

The appendix derives descent and optimality-gap bounds by combining blockwise optimality conditions, proximal nonexpansiveness, concavity, strong concavity, and Lipschitz assumptions. These bounds establish sufficient descent of a potential function and the stated iteration complexity.

  • Because direct combination of the x- and y-descent lemmas does not clarify objective behavior, the proof introduces a potential function that decreases after each update round.
  • Sufficient descent of the potential function follows after combining the blockwise inequalities and choosing the regularization parameters so the relevant coefficient is positive.
  • The analysis bounds each x-block’s optimality gap using the block update’s optimality condition, proximal nonexpansiveness, and Lipschitz-gradient assumptions.
  • The y-update analysis uses its optimality condition, proximal nonexpansiveness, and Assumption A.3 to obtain a corresponding bound.
  • The resulting complexity bound follows by summing the optimality-gap inequality through T(ε) iterations and dividing by ε^2.
  • The potential function is lower bounded by the objective because its coefficient on the squared y-step is positive under the stated condition.

E. Proof of Lemma 4

The proof of Lemma 4 analyzes the y-update through its optimality condition and the strong concavity and Lipschitz properties of the objective.

  • The y-update optimality condition introduces a subgradient of the feasible-set indicator and g at the new iterate.
  • The proof bounds the y-step using concavity, the recurrence established earlier, the quadrilateral identity, and Young’s inequality.
  • Combining the derived inequalities completes the proof of Lemma 4.

F. Proof of Lemma 5

The proof of Lemma 5 derives a recurrence for successive y-iterate differences and verifies the parameter condition needed for the descent argument.

  • The proof formulates the y-update optimality conditions at consecutive iterations and uses subgradient monotonicity to relate successive y-steps.
  • The resulting inequality is used to analyze the size of the difference between consecutive iterates through the auxiliary quantity v^{r+1}.
  • The recurrence uses decreasing penalty parameters, concavity in y, Young’s inequality, and the quadrilateral identity.
  • Condition γ^r ≤ ρ/4 follows from condition (36), completing the proof.

G. Proof of Theorem 2

The proof combines descent, boundedness, and parameter-sequence estimates to derive the desired convergence bound. It concludes by applying the resulting inequality with suitable regularization choices.

  • The penalty sequence is chosen nondecreasing and above the block-gradient Lipschitz constants, satisfying the stated assumption.
  • The proof combines bounds from intermediate inequalities to obtain an overall estimate of the descent.
  • Boundedness of the maximization variable and compactness of its feasible set provide constants used in the convergence estimates.
  • Summing the estimates over iterations and applying the selected parameter sequences yields the desired result.

I. PRELIMINARIES

The preliminaries formulate the block-wise one-sided non-convex min-max problem and introduce a modified HiBSA method that approximates maximization updates with finite gradient-ascent steps. The analysis assumes compact convex feasible sets, smooth coupling, and suitable surrogate properties.

  • The problem has multiple minimization blocks with convex possibly nonsmooth regularizers and a maximization variable over convex compact feasible sets.
  • Finite gradient-ascent updates replace exact maximization solves, requiring access only to gradients with respect to the primal and maximization variables.
  • The modified HiBSA method updates each minimization block and then performs a finite number of updates for the maximization block.
  • The assumptions require compact convex feasible sets, lower boundedness, Lipschitz gradients, and strongly convex surrogate functions with gradient consistency and tight upper bounds.
  • The convergence target is an ǫ-stationary condition expressed through a defined gap function.

II. CONVERGENCE ANALYSIS

The convergence analysis establishes descent properties for the regularized block updates and controls the inexact maximization updates. Under the assumptions, HiBSA reaches an ǫ-stationary point with quantified outer-iteration and gradient-complexity bounds.

  • The regularized maximization objective is strongly concave in y with modulus γr and has y-gradient Lipschitz constant Ly + γr.
  • The smoothed minimization objective σγr(x) has Lipschitz-continuous block gradients, enabling descent estimates for the minimization updates.
  • The analysis combines block optimality bounds, maximization-error bounds, and parameter choices to obtain an overall descent estimate.
  • A finite number of proximal gradient-ascent steps produces a maximization iterate satisfying the required accuracy condition.
  • Theorem 1 states that HiBSA reaches an ǫ-stationary point after T(ǫ) outer iterations, with Jr inner ascent steps and a quantified total gradient-computation bound.
Loading 1902.08294v2…