PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization

Digvijay Boob, Qi Deng, Guanghui Lan

arXiv:1908.02734v4math.OCcs.LG

TL;DR

Functional constrained optimization includes practical cases with nonconvex losses, for which direct approaches can be difficult. The paper combines ConEx with proximal-point subproblems and reports best-known convex rates and KKT convergence results for nonconvex methods.

  • Problem

    How to solve functional constrained problems when practical losses may be nonconvex, a setting the paper says can be difficult for direct approaches.

    Source: §1 · pp. 2, 4

  • Method

    For convex functional constraints, ConEx extrapolates using linearized constraints; for nonconvex problems, proximal-point updates create strongly convex subproblems, with inexact ConEx solves proposed for large-scale and stochastic cases.

    Source: §1 · p. 4, §3.3 · p. 28, §4 · p. 32

  • Results

    O(∆/ε) iterations yield an (ε, ε)-KKT point under the inexact method, while ConEx attains best-known rates across convex composite settings.

    Source: §1 · p. 4, §4 · p. 32

  • Takeaways & Limitations

    A strong-feasibility assumption for the inexact method alleviates the need to generate strictly feasible solutions.

    Source: §1 · p. 4

    The exact proximal-point variant needs exact subproblem solves to guarantee a strictly feasible sequence; inexact solves can make iterates infeasible for the original problem.

    Source: §3.1 · p. 23, §3.2 · p. 23

Abstract

from arXiv · show

Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in risk-averse machine learning, semisupervised learning, and robust optimization among others. In this paper, we first present a novel Constraint Extrapolation (ConEx) method for solving convex functional constrained problems, which utilizes linear approximations of the constraint functions to define the extrapolation (or acceleration) step. We show that this method is a unified algorithm that achieves the best-known rate of convergence for solving different functional constrained convex composite problems, including convex or strongly convex, and smooth or nonsmooth problems with a stochastic objective and/or stochastic constraints. Many of these rates of convergence were in fact obtained for the first time in the literature. In addition, ConEx is a single-loop algorithm that does not involve any penalty subproblems. Contrary to existing primal-dual methods, it does not require the projection of Lagrangian multipliers into a (possibly unknown) bounded set. Second, for nonconvex functional constrained problems, we introduce a new proximal point method that transforms the initial nonconvex problem into a sequence of convex problems by adding quadratic terms to both the objective and constraints. Under a certain MFCQ-type assumption, we establish the convergence and rate of convergence of this method to KKT points when the convex subproblems are solved exactly or inexactly. For large-scale and stochastic problems, we present a more practical proximal point method in which the approximate solutions of the subproblems are computed by the aforementioned ConEx method. To the best of our knowledge, most of these convergence and complexity results of the proximal point method for nonconvex problems also seem to be new in the literature.

1 Introduction

The introduction frames functional constraints as relevant to risk-averse and semi-supervised learning, then identifies gaps in stochastic convex and nonconvex constrained optimization. It presents ConEx for convex problems and proximal-point methods for nonconvex problems.

1 Introduction

  • Risk-averse learning can minimize a loss-risk measure such as CVaR subject to an acceptable expected-loss threshold, while semi-supervised learning can constrain proximity on unlabeled samples.The problem formulation covers convex and nonconvex settings, depending on assumptions on its component functions.Source: §1 · pp. 1–2
  • Existing convex methods face limits in accelerated smooth rates, unknown dual-multiplier bounds, penalty subproblems, or stochastic assumptions; methods for nonconvex functional constraints remain scarce and may not ensure feasibility.Prior stochastic approaches may require constraint evaluations, stochastic lower bounds, light-tail noise, or bounded constraint noise.Source: §1 · pp. 2–3
  • ConEx uses linearized constraint functions in its extrapolation step and is a single-loop primal-dual method requiring neither multiplier projection onto a bounded set nor penalty subproblems.It targets convex or strongly convex, smooth or nonsmooth problems with stochastic objectives and/or constraints.Source: §1 · p. 3
  • ConEx provides convergence and complexity guarantees across deterministic, semi-stochastic, and fully stochastic settings, including strongly convex last-iterate convergence and results without bounded or light-tailed stochastic subgradients.The introduction reports best-known rates across problem classes and identifies several new complexity results; smooth-case rates in Table 1 have a condition on B.Source: §1 · pp. 3–4, Table 1 · p. 3
  • For nonconvex functional constraints, proximal-point methods form strongly convex subproblems; under MFCQ, the inexact method converges to KKT points and takes O(1/ε) iterations for an appropriately defined (ε, ε^2)-KKT point.A large-scale and stochastic variant uses first-order methods such as ConEx to approximately solve subproblems, with an iteration bound depending on summed inexactness errors.Source: §1 · p. 4

1.1 Notation and terminologies

  • The notation section defines vector forms for constraints and component functions, dual norms, and the prox-function associated with a strongly convex smooth function.It also specifies conventions for subdifferentials, normal cones, positive-part notation, and smoothness.Source: §1.1 · p. 5

2 Constraint Extrapolation for Convex Functional Constrained Optimization

This section presents ConEx for convex functional constrained optimization as a single-loop primal-dual method that extrapolates using linearized constraint values. It analyzes convergence and complexity in convex and strongly convex settings, including ergodic optimality and infeasibility bounds and an iteration guarantee for an ε objective gap in the convex case.

2.1 The ConEx method

  • ConEx replaces exact constraint values in its extrapolation step with linearized values, using a stochastic approximation of the extrapolated constraints.The method’s constraint estimate is unbiased, and its primal iterates are combined using a weighted average.Source: §2.1 · pp. 6–7
  • Unlike existing primal-dual approaches, ConEx converges with an unbounded dual feasible set and does not require projecting multipliers onto a possibly unknown bounded set.The passage also contrasts this with the bounded-set projection and stepsize requirements of prior methods [19].Source: §2.1 · p. 6
  • The analysis provides convergence and iteration-complexity bounds for strongly convex and general convex objectives across deterministic, semi-stochastic, and fully stochastic settings.It covers smooth and nonsmooth composite problems; the strongly convex results also give convergence to the optimal solution and an (ε, ε)-optimality iteration guarantee.Source: §2.1 · pp. 9–10
  • The paper reports new complexity results separating the effects of Lipschitz constants and for fully stochastic constrained problems requiring only bounded second moments.The novelty claim applies to both the strongly convex and general convex analyses.Source: §2.1 · pp. 9–10
  • For smooth problems, choosing B ≥ ∥y*∥₂ + 1 yields the stated faster bounds; if B is smaller, ConEx still converges at the nonsmooth rate without knowing that dual bound.The method’s accelerated rates also hold when the constraints are merely convex, provided the objective is strongly convex.Source: §2.1 · pp. 9–10
  • Bounds (2.25) and (2.26) appear new; when B < ||y*||_2 + 1, H* > 0 and ConEx converges at nonsmooth-problem rates in all three described settings.A similar bound to (2.24) had been obtained using more complicated algorithms or a different criterion.Source: §2.1 · p. 11
  • Replacing H* with HB in the stepsize gives similar complexity bounds for most listed settings, but not smooth deterministic problems.For smooth deterministic problems HB = 0 while H* > 0; setting HB > 0 yields O(1/ε^2) rather than the faster O(1/ε), or a line search can seek an appropriate value.Source: §2.1 · p. 11

2.2 Convergence analysis of the ConEx method

  • The analysis uses a primal-dual gap for the saddle-point formulation to bound optimality and infeasibility of the ergodic solution separately.It converts expected gap bounds into ergodic bounds using convexity and non-random feasible test points.Source: §2.2 · pp. 11, 14, 15, 16
  • Under the stated step-size conditions, the analysis bounds the expected squared gradient-estimation error uniformly over iterations.The bound depends on constants determined by the step sizes; the analysis then selects policies for the strongly convex and convex cases that satisfy the conditions.Source: §2.2 · p. 18
  • The proof combines the T^(3/2)-order terms to obtain (2.12), then uses similar replacements in the relation as (2.79) to obtain (2.13) and concludes.Source: §2.2 · p. 19
  • For the convex case, the prescribed step sizes yield bounds (2.20)–(2.21) and an expected objective gap of at most ε.The proof derives the bounds and uses (2.20) and (2.22) to establish the objective-gap guarantee.Source: §2.2 · pp. 19–20

3 Proximal Point Methods for Nonconvex Functional Constrained Porblems

This section examines proximal point methods that transform nonconvex functional constrained problems into convex subproblems. It covers exact and inexact methods and their KKT and complexity guarantees under MFCQ conditions.

3 Proximal Point Methods for Nonconvex Functional Constrained Porblems

  • Under MFCQ, a local optimum satisfies the KKT condition, using subdifferentials that combine smooth nonconvex and nonsmooth convex components.The section defines Bψᵢ(x) = {∇fᵢ(x)} + Bχᵢ(x) for these composite functions.Source: §3 · pp. 20–21

3.1 Basic proximal point method

  • The exact method adds strongly convex proximal terms to the objective and constraints, yielding convex subproblems with unique global solutions when feasible.With a strictly feasible initial point, generated iterates remain strictly feasible and objective values decrease; the method either reaches a KKT point or produces a strictly decreasing objective sequence with a limit and vanishing successive steps.Source: §3.1 · pp. 21–22
  • Exact subproblem solves can be impractical, and the multiplier bound may not be uniform, so convergence of iterates to KKT points is not ensured by these results.The passage notes that multipliers may diverge as iterates approach boundary points.Source: §3.1 · p. 23

3.2 Inexact proximal point method under MFCQ

  • Inexact solves can lose feasibility, but sufficiently accurate subproblem solutions ensure strict feasibility of iterates and boundedness of the corresponding exact-solution multipliers.The inexact method permits approximate subproblem solutions; its feasibility result assumes the stated accuracy condition and Lipschitz continuity of the subproblem functions.Source: §3.2 · pp. 23–24
  • The objective values decrease monotonically and converge, while the iterates remain strictly feasible under the inexactness conditions.The strict-feasibility argument uses the initial strict feasibility and condition (3.13).Source: §3.2 · pp. 24–25
  • If a solution subsequence converges to a point satisfying MFCQ, its corresponding dual subsequence is bounded, and any dual limit point forms a KKT pair with that point.The result assumes the conditions of Proposition 3.7.Source: §3.2 · p. 25
  • Under Strong MFCQ, all limit points are critical KKT points, dual variables are uniformly bounded, and after K iterations the sequence contains an approximate KKT point.When subproblems are solved exactly, the method generates an ε_K-KKT point.Source: §3.2 · p. 26
  • The authors identify the MFCQ-based complexity analysis as, to their knowledge, the first of its kind; it suffices that every limit point satisfies MFCQ, and Strong MFCQ ensures this.The method generates strictly feasible approximate KKT points, although feasibility is not essential to the underlying optimality measure.Source: §3.2 · p. 27
  • For functional constrained problems, the proximal point complexity bound includes an unknown B that may depend on the solution path, unlike the typically initial-condition-based parameters for unconstrained problems.The comparison indicates difficulty in analyzing complexity for nonconvex optimization with nonconvex constraints.Source: §3.2 · p. 28
  • ConEx can eventually satisfy the inexactness criteria for convex subproblems, but its convergence guarantees do not yield a total complexity estimate purely in terms of initial distance.This motivates combining proximal point methods with first-order methods for large-scale and stochastic optimization.Source: §3.2 · p. 28, §3.3 · p. 28

3.3 Inexact proximal point under the strong feasibility assumption

  • Strong feasibility is a local, verifiable condition that provides a computable uniform dual bound and ensures proximal subproblem feasibility and uniformly bounded optimal dual variables.The associated convex proximal subproblem is always feasible and has a KKT solution with uniformly bounded dual variables.Source: §3.3 · pp. 28–29
  • Under Corollary 3.20’s settings, at most K = 2c1(∆f + B s∆0)/ε iterations yield an (ε, 2ε/(µ0 c1))-KKT point of Problem (1.1).Source: §3.3 · p. 31
  • For smooth nonconvex problems, the method reaches an (ε, 2ε/(µ0 c1))-KKT point in O(1/ε3/2), O(1/ε2), and O(1/ε3) iterations in deterministic, semi-stochastic, and fully-stochastic cases, respectively.For nonsmooth nonconvex problems, the corresponding bounds are O(1/ε2) for deterministic and semi-stochastic cases and O(1/ε3) for fully-stochastic cases.Source: §3.3 · p. 31

4 Conclusion

The paper presents ConEx for convex functional constraints and proximal point methods for nonconvex problems. It reports convergence and complexity results, including inexact methods for settings where high-accuracy subproblem solutions are difficult to obtain.

4 Conclusion

  • ConEx achieves best-known convergence rates across convex functional constrained composite problems, with new complexity results especially for stochastic settings or problems with smooth components.The method uses linear constraint approximations in its extrapolation step.Source: §4 · p. 32
  • For nonconvex functional constraints, proximal point methods use strongly convex subproblems and establish convergence to KKT points and iteration complexities under MFCQ-type assumptions.Source: §4 · p. 32
  • For large-scale and stochastic problems, inexact proximal point methods establish convergence under a strong feasibility assumption without requiring feasible solutions.ConEx can be used to solve their subproblems approximately.Source: §4 · p. 32

A Proof of Proposition 3.1

The proof constructs a strongly convex constrained problem from the original functions and uses its optimality conditions to establish the result. MFCQ supplies the contradiction needed to bound the constructed multipliers and recover stationarity and complementary slackness.

A Proof of Proposition 3.1

  • Adding a quadratic term to the functions produces convex functions and a constrained convex problem with the reference point as a feasible solution.The proof then minimizes a strongly convex regularized objective over a local neighborhood.Source: A Proof of Proposition 3.1 · p. 35
  • The local minimizers of the regularized problems converge to the reference point, allowing their first-order conditions to yield a multiplier sequence for the convex problem.The proof argues that this sequence is bounded by contradiction using MFCQ.Source: A Proof of Proposition 3.1 · pp. 35–36
  • A convergent multiplier subsequence gives stationarity, while continuity and the multiplier definition establish complementary slackness at the reference point.Source: A Proof of Proposition 3.1 · pp. 35–36

B Proof of Proposition 3.16

The proof transfers local optimality to a convexified problem and applies its KKT conditions. Because the convexification agrees with the original functions at the reference point, those conditions yield the desired KKT conditions there.

B Proof of Proposition 3.16

  • Near the reference point, feasibility for the convexified constraints implies feasibility for the original constraints, so local optimality transfers to the convex problem.Source: B Proof of Proposition 3.16 · p. 36
  • The reference point is therefore globally optimal for the convex problem, whose Slater condition gives multipliers satisfying its KKT conditions.Source: B Proof of Proposition 3.16 · p. 36
  • At the reference point, the convexified functions and their subdifferentials agree with the original ones, yielding KKT conditions for the original problem.Source: B Proof of Proposition 3.16 · p. 36
Loading 1908.02734v4…