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

Digvijay Boob; Guanghui Lan; Qi Deng

REVIEW 3 major objections 3 minor 2 cited by

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

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read ConEx reaches the best-known convergence rates for convex functional constrained optimization, and a proximal point variant reaches ε-KKT points in O(1/ε) iterations.

desk verdict The ConEx half is genuinely new and mostly checks out, but the inexact proximal point rates have a squared-distance-versus-distance mismatch that breaks Corollary 3.19 as written. read the letter →

arxiv 1908.02734 v4 pith:W6W2NXSX submitted 2019-08-07 math.OC cs.LG

Digvijay Boob , Qi Deng , Guanghui Lan This is my paper · ORCID

classification math.OCcs.LG MSC 90C2590C2690C3090C15

keywords functionalconstrainedoptimizationconstraintextrapolationstochasticfirst-ordermethodscompositeconvexproximalpointmethodnonconvexKKTconditionsprimal-dual

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Functional constrained optimization—minimizing an objective subject to inequality constraints that are themselves general functions rather than simple boxes—shows up in risk-averse machine learning, semisupervised learning, and robust optimization. This paper claims that a single primal-dual algorithm, Constraint Extrapolation (ConEx), attains the best-known convergence rates across the whole convex spectrum: objective and constraints each convex or strongly convex, smooth or nonsmooth, and evaluated deterministically, with a stochastic objective, or with both stochastic. Several of these rates, notably the fully stochastic ones, are claimed to be new. The same paper gives a proximal point method that converts a nonconvex functional constrained problem into a sequence of strongly convex subproblems and proves an O(1/ε) iteration bound to an approximate KKT point when the subproblem dual variables are uniformly bounded. If these claims hold, a much wider class of constrained stochastic optimization problems can be solved with a simple loop that needs no penalty subproblems and no projection of dual variables onto an unknown bounded set.

What carries the argument

Two mechanisms carry the argument. Constraint extrapolation is the step s_t = (1+θ_t)[χ(x_t)+ℓ_F(x_t)] − θ_t[χ(x_{t-1})+ℓ_F(x_{t-1})], with ℓ_F(x_t) the stochastic linear approximation of the constraint vector at the previous point; the dual update y_{t+1} = [y_t + s_t/τ_t]_+ then stays finite without any projection onto a bounded set. The primal update is a prox step using the Bregman divergence W associated with the prox-function ω. The proximal point machinery adds 2μ_i W(x, x_{k-1}) to each constraint function, forcing every subproblem to be strongly convex in both objective and constraints. A three-point inequality and the saddle-point gap function Q(z, z̄) = L(x, ȳ) − L(x̄, y) convert the algorithm's primal-dual gap into separate bounds on the optimality gap and the constraint violation.

What would settle it

Take a smooth deterministic convex functional constrained problem with a known optimal dual multiplier y*, run ConEx with B set to half of (||y*||_2 + 1), and measure the iteration count needed to reach an (ε, ε)-approximate solution. The paper predicts the rate degrades from O(1/ε) to O(1/$ε^{2}$); if the observed count instead stays O(1/ε), the claimed threshold on B is wrong.

Watch

Extended reading notes

Core claim

ConEx linearizes the constraint functions—replacing ψ(x_t) with χ(x_t) + ℓ_F(x_t), where ℓ_F is a stochastic linear approximation built from the previous iterate—and uses this linearized value inside the extrapolation step of a primal-dual iteration. This substitution makes the dual update well behaved even though the dual feasible set is unbounded, so the method never projects multipliers onto a ball whose radius depends on the unknown optimal multiplier. The paper proves unified iteration complexity bounds for strongly convex and convex, smooth and nonsmooth, deterministic, semi-stochastic, and fully stochastic cases, and identifies which of these rates are new. For nonconvex problems it introduces exact and inexact proximal point methods in which each subproblem is made strongly convex by adding quadratic terms to both the objective and the constraints; under constraint-qualification assumptions the exact scheme converges to KKT points, and under uniform boundedness of the dual sequence the same scheme needs O(1/ε) subproblem solves to produce an ε-KKT point.

Load-bearing premise

The fast rates depend on constants chosen before the run: ConEx needs the user-set B to be at least one plus the unknown norm of an optimal dual multiplier, and the nonconvex method needs the dual multipliers of all subproblems to stay uniformly bounded.

Editorial extensions

If this is right

For convex functional constrained problems, one single-loop algorithm now covers all combinations of strongly convex or convex, smooth or nonsmooth, and deterministic, semi-stochastic, or fully stochastic settings, at the best-known rates, with several fully stochastic rates claimed for the first time.
Users no longer need penalty subproblems or a projection of dual multipliers onto a bounded set whose radius is usually unknown; the price is a user-chosen parameter B, and too small a B degrades the smooth deterministic rate from O(1/ε) to O(1/ε^2).
For nonconvex functional constrained problems, the exact proximal point method gives an O(1/ε) guarantee to an ε-KKT point when the subproblem dual sequence is uniformly bounded.
The inexact proximal point method, with ConEx solving its subproblems, gives total complexities O(1/ε^{3/2}), O(1/ε^2), and O(1/ε^3) for smooth deterministic, semi-stochastic, and fully stochastic nonconvex settings, respectively.
Starting from a strictly feasible point, every iterate of the exact proximal point method remains strictly feasible, so each subproblem satisfies the constraint qualification needed for dual variables to exist.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper leaves implicit that the unknown B threshold could be handled in practice by a restarting line search on the measurable constraint violation ||[ψ(x)]_+||_2: if the violation plateaus above the target, double B and restart, which would preserve the smooth deterministic O(1/ε) rate without knowing the norm of the optimal multiplier in advance.
Because the key trick is replacing function values with linearized values inside the extrapolation, a natural extension is to other first-order primal-dual or extragradient schemes for variational inequalities where the operator norm or dual radius is unknown; the paper only demonstrates the device for functional constraints.
The fully stochastic rates suggest a direct testable application to the motivating example of risk-averse learning with a CVaR objective and an expectation constraint: such problems should exhibit sample complexity O(1/ε^2) without light-tail noise assumptions, unlike level-set methods that require stochastic lower bounds on the optimal value.
The nonconvex O(1/ε) result is conditional on uniform boundedness of the dual sequence; a practical algorithm would need a cheap check for this condition, for example by tracking the dual iterates during ConEx solves and restarting the proximal loop if they exceed a threshold, though the paper does not analyze such a restart rule.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. First, the Constraint Extrapolation (ConEx) method is the real news and it largely holds up. Using linearized constraints to define the extrapolation step is a clean construction, and the unified rate table — deterministic, semi-, and fully-stochastic; smooth, nonsmooth; convex and strongly convex — is what the paper claims. The fully-stochastic bounds under bounded second moments were genuinely first. Second, the inexact proximal point half has a real gap that affects the headline complexity claims: the proof of Theorem 3.17 delivers only a bound on E||x_k - x*_k||^2, and the theorem then uses that same quantity as the delta-tolerance in the (epsilon,delta)-KKT definition. Definition 3.2 measures deviation by ||x - p x|| <= delta, not its square, so the stated s_epsilon_K does not follow. The stress-test note is right.

Credit where due. The B >= ||y*||_2 + 1 caveat on the smooth deterministic O(1/epsilon) rate is real but honestly handled — the paper states plainly that a small B degrades the rate to O(1/epsilon^2) and that the HB substitution provably fails in exactly that case. The suggested line search is not analyzed; that is a minor gap. The exact proximal point results (Theorem 3.13, O(1/epsilon) to an epsilon-KKT point under uniform dual boundedness, with MFCQ-type sufficiency conditions) are coherent. The (3.28)-(3.29) criteria requiring the unknown x*_k are acknowledged as hard to verify, which softens but does not remove the practical limitation.

The problem shows up in Corollary 3.19. With s_delta_k = O(epsilon), the guaranteed distance is at best sqrt(2epsilon/(mu0 c1)) by Jensen, not 2epsilon/(mu0 c1), and the stated O(1/epsilon^{3/2}), O(1/epsilon^2), O(1/epsilon^3) totals for the inexact method do not follow as written. The repair is conceptually simple: either define the stochastic KKT notion with a squared-distance delta (consistent with the already-squared stationarity residual), or square the subproblem tolerances — in which case the final rates degrade, e.g., to O(1/epsilon^2) for the deterministic smooth case. Either way, the authors owe the reader a corrected statement.

The citation pattern is normal; the machinery is the authors' own three-point-lemma toolkit, but no rate is assumed as input. Who gets value: anyone working on constrained stochastic optimization or first-order primal-dual methods — the ConEx rate table is a reference point even if the prox half needs revision.

Recommendation: send to a serious referee, with the inexact proximal point claims the focus of the revision. This is not a desk reject.

Referee Report

3 major / 3 minor

Summary. The paper studies convex and nonconvex functional constrained composite optimization. For the convex case it proposes ConEx, a single-loop primal-dual method using linearized constraint extrapolation, and proves complexity bounds for deterministic, semi-stochastic, and fully-stochastic settings, with smooth or nonsmooth objectives and constraints. For the nonconvex case it proposes exact and inexact proximal point methods that add quadratic proximal terms to both objective and constraints; under Slater-type, MFCQ, or strong-feasibility assumptions it claims asymptotic convergence and O(1/epsilon) rates to epsilon-KKT points, with ConEx used as the subproblem solver in the inexact variant.

Significance. If the results hold, the ConEx method is a valuable unified contribution: it attains several rates that appear to be new, especially for fully stochastic functional constraints, and it avoids projection of the dual iterates onto a known bounded set. The exact proximal point analysis for nonconvex functional constraints under a range of constraint qualifications is also a substantial contribution. The proofs are detailed and largely internally consistent, and the convex part of the paper is explicit about the role of the user-chosen constant B. However, two load-bearing issues in the inexact proximal point part—the mismatch between the squared-distance bound and the distance criterion in Definition 3.2, and the insufficient strict-feasibility conditions in Proposition 3.15—mean that the stated complexity guarantees for the inexact method are not currently established. These are fixable within the scope of the manuscript, but they affect central claims.

major comments (3)

[Section 3.2, Theorem 3.17 and display before (3.41)] The proof of Theorem 3.17 bounds the expected squared distance, E||x_pk - x*_pk||^2 <= 2*Omega_K/(mu_0*K), but Definition 3.2 in (3.3) uses ||x - px||_2 <= delta as the deviation criterion, and a stochastic reading of that definition requires E||x - px||_2 <= delta. Jensen's inequality gives only E||x_pk - x*_pk||_2 <= sqrt(2*Omega_K/(mu_0*K)), which is much larger than 2*Omega_K/(mu_0*K) for small tolerances. Consequently, the claimed s_epsilon_K in (3.41), the (epsilon, 2*epsilon/(mu_0*c1))-KKT conclusion of Corollary 3.19, and the final O(1/epsilon^{3/2}), O(1/epsilon^2), and O(1/epsilon^3) complexities in Remark 3.20 are not established as written. The fix is either to state that the stochastic KKT criterion in Definition 3.2 uses squared distance, or to change the subproblem tolerances to s_delta_k = O(epsilon^2) and re-derive the ConEx subproblem costs accordingly.
[Proposition 3.15, conditions (3.28)-(3.29)] The strict-feasibility and descent conditions in Proposition 3.15 contain a similar square-root mismatch. The proof combines the Lipschitz bound psi_i(x_k;x_{k-1}) <= M_i*||x_k - x*_k|| with the lower bound sqrt(2*mu_i*W(x_k,x_{k-1})) > sqrt(M_i)*||x_k - x*_k||. This yields only 2*mu_i*W > M_i*||x_k - x*_k||^2, not 2*mu_i*W > M_i*||x_k - x*_k||, so strict feasibility of x_k does not follow; the same issue affects the descent inequality in part b). The correct condition would require a tolerance of the form sqrt(M_i/mu_i)*sqrt(||x_k - x*_k||) + ||x_k - x*_k|| < ||x_{k-1} - x*_k||, i.e., subproblem accuracy of order O(epsilon^2) rather than O(epsilon). Since Theorem 3.16 and the subsequent convergence analysis rely on these conditions, this is a load-bearing gap that needs to be repaired or the complexity statements adjusted.
[Section 2.1, Theorem 2.3 and discussion after (2.22)] The headline O(1/epsilon) complexity for smooth deterministic convex problems in Table 1 is conditional on the user choosing B >= ||y*||_2 + 1, where y* is an unknown optimal Lagrange multiplier. If B is smaller, the bound in (2.21)-(2.22) degrades to the nonsmooth O(1/epsilon^2) rate, and the manuscript proves that replacing H* by HB in the stepsize policy (2.19) fails for smooth deterministic problems. The suggested line search is not analyzed. Since this is one of the main claimed new rates, the paper should either provide an implementable adaptive procedure with a proven rate or explicitly state that the smooth deterministic row of Table 1 is conditional on knowledge of an upper bound on ||y*||_2.

minor comments (3)

[Proof of Theorem 3.13] The proof cites relation (3.39), which is defined only later in Section 3.2; the intended reference appears to be relation (3.16) of the exact proximal point analysis. Please correct the cross-reference.
[Section 3 heading] The section heading contains a typo: 'Porblems' should be 'Problems'.
[References] The reference to Ma, Lin, and Yang is incomplete: it lacks a venue, year, or arXiv identifier.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the ConEx and proximal-point convergence proofs are derived in-paper, and the inexact-proximal δ issue is a correctness gap, not a circularity.

full rationale

This paper's central claims are self-contained derivations. The ConEx rates (Theorems 2.1 and 2.3) are obtained in Section 2.2 from the primal-dual gap bound of Lemma 2.5, the conversion Lemma 2.7, and the stochastic-noise bound of Lemma 2.9; none of these lemmas assume the target rate as an input. The stepsize policies (2.10) and (2.19) are explicit in problem data (L0, Lf, M, σ, DX, B, etc.) and are not calibrated to the ε appearing in the conclusions. The exact proximal point theorem (Theorem 3.13) derives ε_K from the sufficient-descent and dual-boundedness estimates (3.25)-(3.26). The inexact result (Theorem 3.17) assumes the subproblem solver returns a (δk, sδk)-optimal solution in the sense of Definition 2.1; this is an input hypothesis, not a restatement of the (ε_K, s_ε_K)-KKT conclusion. The acknowledged limitations — that (3.28)-(3.29) involve the inaccessible x*_k, that the smooth rate requires B ≥ ||y*||2+1, and that a line search is suggested but not analyzed — are assumption/verifiability issues, not circular reductions. Self-citations (e.g., [20] for the three-point lemma and [24] for proximal-point subproblem analysis) are used for context or for lemmas that are reproved in the text; no load-bearing step reduces to an unverified self-citation. No uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via citation. The paper is therefore not circular, notwithstanding a separate correctness concern about matching a squared-distance bound to the ||x−px|| tolerance in Definition 3.2; that concern does not make the derivation circular.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new physical entities. The hand-chosen parameters B and µ_i are algorithmic; the central complexity exponents are independent of them, but the quality of constants and the validity of smooth rates depend on B relative to ||y*||. The main assumptions are standard Slater/MFCQ-type constraint qualifications and bounded-variance stochastic oracles.

free parameters (2)

B (ConEx multiplier bound) = user-specified, must be ≥ ||y*||_2 + 1 for smooth rates
Appears in stepsize definitions (2.10), (2.19); too-small B degrades the smooth deterministic rate from O(1/ε) to O(1/ε²) (Section 2.1).
proximal coefficients µ_0,...,µ_m = positive user-specified values
Algorithm 2 adds 2µ_i W(x,x_{k-1}) to objective and constraints; the rate constants and feasibility conditions (3.21) depend on these choices, though exponents do not.

assumptions (6)

domain assumption Existence of an optimal Lagrange multiplier y* for the convex problem (2.2).
Stated in the introduction to Section 2; the saddle-point analysis of ConEx relies on this multiplier.
domain assumption Strict feasibility of the initial point x0 for the exact proximal point method.
Theorem 3.3 and Proposition 3.5 depend on strict feasibility to guarantee Slater's condition for subproblems and to bound the dual sequence.
domain assumption Uniform boundedness of the dual sequence (Assumption 3.9) or MFCQ at every limit point for the O(1/ε) rate.
Theorem 3.13 and Theorem 3.17 require sup_k ||y_k||_1 ≤ B; without this bound only asymptotic convergence is shown.
domain assumption Stochastic oracle conditions (2.9): unbiased estimators with bounded second moments.
All stochastic convergence claims are built on these variance assumptions.
domain assumption The prox operator for χ0 and weighted χ_i is efficiently computable (2.3).
ConEx line 5 and the definition of the stochastic oracle assume the prox operator in (2.3) can be computed.
standard math Standard convex analysis facts: subgradient properties, the three-point lemma, and Bregman divergence inequalities.
These are standard background; the three-point lemma is restated and proven as Lemma 2.4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization." pith.science (2026). https://pith.science/paper/W6W2NXSX

@misc{pith2026190802734,
  author       = {Pith},
  title        = {Pith review of: Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W6W2NXSX}},
  note         = {Machine review of arXiv:1908.02734}
}

read the original abstract

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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
math.OC 2019-08 conditional novelty 7.0 of 10

An inexact proximal-point penalty algorithm finds ε-stationary points of non-convex constrained problems in O~(ε^{-5/2}) steps with convex constraints and O~(ε^{-3}) to O~(ε^{-4}) steps with non-convex constraints.
Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints
math.OC 2019-08 conditional novelty 6.0 of 10

A proximally constrained subgradient method finds a nearly stationary point for weakly convex objectives with weakly convex constraints in O(1/epsilon^4) deterministic and O~(1/epsilon^6) stochastic iterations.

Reference graph

Works this paper leans on

49 extracted references · 41 canonical work pages · cited by 2 Pith papers

[1]

Variance reduction for faster non-convex optimization

Allen-Zhu, Z., and Hazan, E. Variance reduction for faster non-convex optimization. International Conference on Machine Learning (2016), 699–707

work page 2016
[2]

Andreani, R., Haeser, G., and Mart ´ınez, J. M. On sequential optimality conditions for smooth constrained optimization. Optimization 60 , 5 (2011), 627–641

work page 2011
[3]

M., Ramos, A., and Silva, P

Andreani, R., Mart´ınez, J. M., Ramos, A., and Silva, P. J. S. Strict constraint qual- iﬁcations and sequential optimality conditions for constrained optim ization. Mathematics of Operations Research 43 (2018), 693–717

work page 2018
[4]

Y., Burke, J

Aravkin, A. Y., Burke, J. V., Drusvyatskiy, D., Friedlander , M. P., and Roy, S. Level-set methods for convex optimization. Mathematical Programming (2018), 1–32

work page 2018
[5]

Non-euclidean restricted memory level method for large-scale convex optimization

Ben-Tal, A., and Nemirovski, A. Non-euclidean restricted memory level method for large-scale convex optimization. Mathematical Programming 102 (2005), 407–456

work page 2005
[6]

Bertsekas, D. P. Nonlinear programming. Athena Scientiﬁc, 1999

work page 1999
[7]

Bertsekas, D. P. Convex optimization algorithms . Athena Scientiﬁc Belmont, 2015

work page 2015
[8]

I., and Toint, P

Cartis, C., Gould, N. I., and Toint, P. L. On the complexity of ﬁnding ﬁrst-order critical points in constrained nonlinear optimization. Mathematical Programming 144 , 1 (2014), 93–106

work page 2014

Show all 49 references

[9]

A ﬁrst-order primal-dual algorithm for convex problems with applications to imaging

Chambolle, A., and Pock, T. A ﬁrst-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40 , 1 (2011), 120–145

2011
[10]

Optimal primal-dual methods for a class of saddle point problems

Chen, Y., Lan, G., and Ouyang, Y. Optimal primal-dual methods for a class of saddle point problems. SIAM Journal on Optimization 24 , 4 (2014), 1779–1814

2014
[11]

Proximally guided stochastic subgradient method for nons- mooth, nonconvex problems

Davis, D., and Grimmer, B. Proximally guided stochastic subgradient method for nons- mooth, nonconvex problems. arXiv preprint arXiv: 1707.03505v4 (2017)

2017 arXiv
[12]

Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and itera tion complexity

F acchinei, F., Kungurtsev, V., Lampariello, L., and Scutar i, G. Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and itera tion complexity. arXiv preprint arXiv:1709.03384 (2017)

2017 arXiv
[13]

J., Lin, Z., and Zhang, T

F ang, C., Li, C. J., Lin, Z., and Zhang, T. Spider: Near-optimal non- convex optimiza- tion via stochastic path-integrated diﬀerential estimator. Advances in Neural Information Processing Systems, 687–697
[14]

Un-regularizing: approximate prox- imal point and faster stochastic algorithms for empirical risk minimiza tion

Frostig, R., Ge, R., Kakade, S., and Sidford, A. Un-regularizing: approximate prox- imal point and faster stochastic algorithms for empirical risk minimiza tion. In International Conference on Machine Learning (2015), pp. 2540–2548

2015
[15]

Stochastic ﬁrst- and zeroth-order methods for nonconvex stochastic programming

Ghadimi, S., and Lan, G. Stochastic ﬁrst- and zeroth-order methods for nonconvex stochastic programming. 2341–2368
[16]

Accelerated gradient methods for nonconvex nonlinear and stochastic programming

Ghadimi, S., and Lan, G. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming 156 , 1-2 (2016), 59–99

2016
[17]

New proximal point algorithms for convex minimization

G¨uler, O. New proximal point algorithms for convex minimization. SIAM Journal on Optimization 2 , 4 (1992), 649–664

1992
[18]

Y., and Aybat, N

Hamedani, E. Y., and Aybat, N. S. A primal-dual algorithm for general convex-concave saddle point problems. arXiv preprint arXiv:1803.01401 (2018)

2018 arXiv
[19]

G., and Monteiro, R

Kong, W., Melo, J. G., and Monteiro, R. D. Complexity of a quadratic penalty accel- erated inexact proximal point method for solving linearly constraine d nonconvex composite programs. arXiv preprint arXiv:1802.03504 (2018)

2018 arXiv
[20]

Lectures on Optimization Methods for Machine Learning

Lan, G. Lectures on Optimization Methods for Machine Learning . 2019. 32

2019
[21]

Communication-eﬃcient algorithms for decentralized and stochastic optimization

Lan, G., Lee, S., and Zhou, Y. Communication-eﬃcient algorithms for decentralized and stochastic optimization. Mathematical Programming (2018)

2018
[22]

Lan, G., and Monteiro, R. D. C. Iteration-complexity of ﬁrst-order penalty methods for convex programming. Mathematical Programming 138 (2013), 115–139

2013
[23]

Lan, G., and Monteiro, R. D. C. Iteration-complexity of ﬁrst-order augmented la- grangian methods for convex programming. Mathematical Programming 155(1-2) (2016), 511–547

2016
[24]

Accelerated stochastic algorithms for nonconvex ﬁnite-sum and multi-block optimization

Lan, G., and Yang, Y. Accelerated stochastic algorithms for nonconvex ﬁnite-sum and multi-block optimization. arXiv preprint arXiv:1805.05411 (2018)

2018 arXiv
[25]

An optimal randomized incremental gradient method

Lan, G., and Zhou, Y. An optimal randomized incremental gradient method. Math. Program. 171, 1-2 (2018), 167–215

2018
[26]

Algorithms for stochastic optimization with expectation con- straints

Lan, G., and Zhou, Z. Algorithms for stochastic optimization with expectation con- straints. arXiv preprint arXiv:1604.03887 (2016)

2016 arXiv
[27]

S., and Nesterov, Y

Lemar´ echal, C., Nemirovski, A. S., and Nesterov, Y. E. New variants of bundle methods. 111–148
[28]

Level-set methods for ﬁnite-sum constrained convex optimization

Lin, Q., Ma, R., and Yang, T. Level-set methods for ﬁnite-sum constrained convex optimization. In Proceedings of the 35th International Conference on Machin e Learning (2018), vol. 80, pp. 3112–3121

2018
[29]

A level-set method for convex optimization with a feasible solution path

Lin, Q., Nadarajah, S., and Soheili, N. A level-set method for convex optimization with a feasible solution path. SIAM Journal on Optimization 28 , 4 (2018), 3290–3311

2018
[30]

Proximally constrained methods for weakly convex optimization with weakly convex constraints

Ma, R., Lin, Q., and Yang, T. Proximally constrained methods for weakly convex optimization with weakly convex constraints
[31]

The fritz john necessary optimality conditions in the presence of equality and inequality constraints

Mangasarian, O., and Fromovitz, S. The fritz john necessary optimality conditions in the presence of equality and inequality constraints. Journal of Mathematical Analysis and Applications 17 (1967), 37–47

1967
[32]

M., and Svaiter, B

Mart´ınez, J. M., and Svaiter, B. F. A practical optimality condition without constraint qualiﬁcations for nonlinear programming. Journal of Optimization Theory and Applications 118, 1 (2003), 117–133

2003
[33]

Prox-method with rate of convergence o(1/t) for variational ine quali- ties with lipschitz continuous monotone operators and smooth conv ex-concave saddle point problems

Nemirovski, A. Prox-method with rate of convergence o(1/t) for variational ine quali- ties with lipschitz continuous monotone operators and smooth conv ex-concave saddle point problems. SIAM Journal on Optimization 15 , 1 (2004), 229–251

2004
[34]

Lectures on convex optimization

Nesterov, Y. Lectures on convex optimization . Springer, 2018

2018
[35]

M., Liu, J., Scheinberg, K., and c, M

Nguyen, L. M., Liu, J., Scheinberg, K., and c, M. T. A novel method for machine learning problems using stochastic recursive gradient. Proceedings of the 34th International Conference on Machine Learning 70 (2017), 2613–2621

2017
[36]

D., and Razaviyayn, M

Nouiehed, M., Sanjabi, M., Lee, J. D., and Razaviyayn, M. Solving a class of non- convex min-max games using iterative ﬁrst order methods. arXiv preprint arXiv:1902.08297 (2019)

2019 arXiv
[37]

H., Nguyen, L

Pham, N. H., Nguyen, L. M., Phan, D. T., and Tran-Dinh, Q. Proxsarah: An eﬃcient algorithmic framework for stochastic composite nonconve x optimization. arXiv preprint arXiv:1902.05679 (2019)

2019 arXiv
[38]

A general method of solving extremum problems

Polyak, B. A general method of solving extremum problems. Soviet Mathematics Doklady 8(3) (1967), 593–597

1967
[39]

Quoc Tran Dinh, Suat Gumussoy, W. M. M. D. Combining convex-concave decom- positions and linearization approaches for solving bmis, with applicatio n to static output feedback. 33
[40]

Non-convex min-max optimization: Provable algorithms and applications in machine learning

Rafique, H., Liu, M., Lin, Q., and Yang, T. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060 (2018)

2018 arXiv
[41]

J., Hefny, A., Sra, S., P ´ocz´os, B., and Smola, A

Reddi, S. J., Hefny, A., Sra, S., P ´ocz´os, B., and Smola, A. J. Stochastic vari- ance reduction for nonconvex optimization. International Conference on Machine Learning (2016), 314–323

2016
[42]

T., and Uryasev, S

Rockafellar, R. T., and Uryasev, S. Optimization of conditional value-at-risk. Journal of Risk 2 (2000), 21–41

2000
[43]

Lectures on Stochastic Program- ming: Modeling and Theory, Second Edition

Shapiro, A., Dentcheva, D., and Ruszczynski, A. Lectures on Stochastic Program- ming: Modeling and Theory, Second Edition . Society for Industrial and Applied Mathemat- ics, Philadelphia, PA, USA, 2014

2014
[44]

Penalty methods with stochastic approximation for stochastic nonlinear programming

W ang, X., Ma, S., and Yuan, Y. Penalty methods with stochastic approximation for stochastic nonlinear programming. Mathematics of Computation 86 (306) (2017), 1793– 1820

2017
[45]

Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization

W ang, Z., Ji, K., Zhou, Y., Liang, Y., and Tarokh, V. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. arXiv preprint arXiv:1810.10690

arXiv
[46]

Iteration complexity of inexact augmented lagrangian methods for constrained convex programming

Xu, Y. Iteration complexity of inexact augmented lagrangian methods for constrained convex programming. Mathematical Programming (2019)

2019
[47]

Online convex optimization with stochastic constraints

Yu, H., Neely, M., and Wei, X. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems (2017), 1428–1438

2017
[48]

Stochastic nested variance reduction for nonconvex optimization

Zhou, D., Xu, P., and Gu, Q. Stochastic nested variance reduction for nonconvex optimization. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems (USA, 2018), NIPS’18, Curran Associates Inc., pp. 3925–3936. A Proof of Proposition 3.2 Le...

2018
[49]

Let xk :“ argminxPSXX Ψ kpxq

Let S “ tx : ‖x ´x˚‖2 ă εu for some ε ą 0 such that any x P S which is feasible for ( A.1) satisﬁes sψ0pxq ě sψ0px˚q. Let xk :“ argminxPSXX Ψ kpxq. Note that as k Ñ 8 then due to the optimality of xk and existence of x˚ P S XX, we have limkÑ8 sψpxkq ď 0. Since lim kÑ8xk is fea...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Variance reduction for faster non-convex optimization

Allen-Zhu, Z., and Hazan, E. Variance reduction for faster non-convex optimization. International Conference on Machine Learning (2016), 699–707

work page 2016

[2] [2]

Andreani, R., Haeser, G., and Mart ´ınez, J. M. On sequential optimality conditions for smooth constrained optimization. Optimization 60 , 5 (2011), 627–641

work page 2011

[3] [3]

M., Ramos, A., and Silva, P

Andreani, R., Mart´ınez, J. M., Ramos, A., and Silva, P. J. S. Strict constraint qual- iﬁcations and sequential optimality conditions for constrained optim ization. Mathematics of Operations Research 43 (2018), 693–717

work page 2018

[4] [4]

Y., Burke, J

Aravkin, A. Y., Burke, J. V., Drusvyatskiy, D., Friedlander , M. P., and Roy, S. Level-set methods for convex optimization. Mathematical Programming (2018), 1–32

work page 2018

[5] [5]

Non-euclidean restricted memory level method for large-scale convex optimization

Ben-Tal, A., and Nemirovski, A. Non-euclidean restricted memory level method for large-scale convex optimization. Mathematical Programming 102 (2005), 407–456

work page 2005

[6] [6]

Bertsekas, D. P. Nonlinear programming. Athena Scientiﬁc, 1999

work page 1999

[7] [7]

Bertsekas, D. P. Convex optimization algorithms . Athena Scientiﬁc Belmont, 2015

work page 2015

[8] [8]

I., and Toint, P

Cartis, C., Gould, N. I., and Toint, P. L. On the complexity of ﬁnding ﬁrst-order critical points in constrained nonlinear optimization. Mathematical Programming 144 , 1 (2014), 93–106

work page 2014