Pith. sign in

REVIEW 3 major objections 6 minor 69 references

Retrospective Approximation Sequential Quadratic Programming for Stochastic Optimization with General Deterministic Nonlinear Constraints

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

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

Pith's one-line read This paper establishes that a retrospective-approximation SQP framework achieves optimal gradient-evaluation and linear-solve complexity for stochastic equality-constrained problems, and extends the same RA mechanism to general nonlinear…

desk verdict A genuinely useful RA-SQP framework with optimal complexity for equality-constrained stochastic optimization; the main caveat is a strong boundedness assumption and a practical inner-iteration cap that the theory does not cover. read the letter →

arxiv 2505.19382 v1 pith:FYL6WMT4 submitted 2025-05-26 math.OC

Albert S. Berahas , Raghu Bollapragada , Shagun Gupta This is my paper · ORCID
classification math.OC MSC 90C3090C1590C55
keywords stochasticoptimizationsequentialquadraticprogrammingretrospectiveapproximationnonlinearconstraintssampleaveragecomplexityanalysisadaptivesamplingconstrained
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

This paper is trying to establish that stochastic optimization with deterministic nonlinear constraints does not require redesigning optimization algorithms for noise. Its Retrospective Approximation (RA) framework repeatedly builds deterministic sample-average approximations of the objective, solves each to a controlled accuracy with an ordinary deterministic solver, and warm-starts the next, larger subproblem. For equality-constrained problems the paper proves that when the inner solver is a line-search SQP method, reaching $\epsilon$-KKT error takes $O(\epsilon^{-4})$ gradient evaluations and $O(\epsilon^{-2})$ SQP linear-system solves, which it identifies as optimal in both measures; for finite-sum objectives the gradient count is $O(|S|\epsilon^{-2})$, matching a deterministic solver on the full problem. For general nonlinear constraints the same RA loop is paired with robust-SQP subproblems that remain feasible and detect infeasible stationary points, with linear convergence across outer iterations. If the guarantees hold, uncertainty can be confined to a sequence of accuracy-controlled subproblems, so standard deterministic machinery like line search, quasi-Newton Hessian approximations, and inexact solves carries over unchanged.

What carries the argument

Retrospective Approximation (RA), in this paper the double loop in Framework 1.1: an outer loop constructs deterministic subsampled problems of increasing size, and an inner loop solves each to a specified tolerance using a deterministic solver. The load-bearing identity is the recursive KKT-error bound of Lemma 2.2, $\|T(x_{k,N_k},\lambda_{k,N_k})\| \le \gamma_k \|T(x_{k-1,N_{k-1}},\lambda_{k-1,N_{k-1}})\| + \epsilon_k + \|\nabla f(x_{k,N_k})-g_{S_k}(x_{k,N_k})\| + \gamma_k\|\nabla f(x_{k,0})-g_{S_k}(x_{k,0})\|$, which converts subproblem accuracy and batch-size control into geometric decay of the true error. For the SQP instance the central operational object is the KKT linear system (2.14), solved exactly or under inexactness conditions (2.18)-(2.19); for general constraints the mechanism is the two-step robust subproblem (3.1)-(3.2), which keeps every subproblem feasible and flags infeasible stationary points.

What would settle it

Run Algorithm 2.2 on a smooth equality-constrained stochastic problem satisfying Assumptions 2.4, 2.5 and 2.8, tracking gradient evaluations and exact SQP linear-system solves to a KKT error of $\epsilon$; if the asymptotic exponents exceed 4 or 2 respectively as the tolerance tightens, the optimal-complexity claim is false, and so is any run in which the 500-iteration inner cap engages before termination test (2.3) is satisfied.

Watch

Extended reading notes

Core claim

At its center, the RA-SQP framework is a double loop in which outer iteration $k$ draws a sample set $S_k$, forms the sample-average approximation (1.6), and asks an inner deterministic solver to satisfy a relative KKT-error test such as (2.3); the inner solver's output becomes the warm start for outer iteration $k+1$. The engine is a recursive bound on the true problem's KKT error across outer iterations (Lemma 2.2), which expresses the new error as a contraction of the old error plus gradient errors at the start and end of the inner loop. If batch sizes are chosen by a norm test (Condition 2.1) so those gradient errors decay geometrically, the outer iterates converge linearly (Theorem 2.5), and if the inner solver has the standard sublinear rate $\epsilon^{-2}$ (Assumption 2.7), the total inner-iteration count is $O(\epsilon^{-2})$. Since the subsampled gradients cost $1/|S_k|$ per evaluation, the expectation-objective total is $O(\epsilon^{-4})$ gradient evaluations; the SQP instance (Algorithm 2.2) realizes this with $O(\epsilon^{-2})$ linear-system solves because each inner iteration solves one system (2.14), optionally inexactly. For general constraints, Algorithm 3.1 replaces (1.5) with robust two-step subproblems (3.1)-(3.2) that first minimize linearized constraint violation and then optimize a quadratic model subject to that violation level; the paper proves well-posedness and linear outer convergence, with a possible return of an infeasible stationary point.

Load-bearing premise

The load-bearing premise is that every run of the algorithm stays inside a closed bounded convex set on which each subsampled objective is smooth with bounded gradients and bounded Hessian approximations; the paper itself caps inner iterations at 500 because in extreme cases this assumption may fail.

Editorial extensions

If this is right

  • For expectation-form equality-constrained problems, a user of Algorithm 2.2 can budget $O(\epsilon^{-4})$ gradient evaluations and $O(\epsilon^{-2})$ SQP linear-system solves to reach an $\epsilon$-stationary point; the paper argues no existing method for this class achieves both counts simultaneously.
  • For finite-sum equality-constrained problems, gradient complexity is $O(|S|\epsilon^{-2})$, the same order as running a deterministic SQP on the full dataset, so the RA overhead does not asymptotically increase deterministic cost.
  • Any deterministic solver with a sublinear inner-loop rate can be dropped into Framework 2.1 and inherits the outer-loop linear convergence, so the choice between SQP, projection, or penalty inner solvers can be made on subproblem cost rather than on stochastic design.
  • For general constraints, Algorithm 3.1 either converges to a first-order stationary point or terminates by identifying an infeasible stationary point, and its deterministic subproblems let quasi-Newton Hessian updates and inexact solves be applied in the stochastic setting.
  • The active-set experiments suggest that RA stabilizes the working set across outer iterations once the batch is large enough, which is a prerequisite for practical active-set SQP methods on stochastic problems.

Reading between the lines

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

  • The recursive bound (2.9) is generic enough that the same proof template should transfer to other stationarity measures, such as projected gradients for bound-constrained problems, whenever the inner solver can certify a rate of decrease in that measure; the paper does not state this extension.
  • The paper's 500-iteration inner cap (Section 4.2) is an implicit admission that Assumption 2.8 can fail in practice; a run that repeatedly hits the cap before satisfying (2.3) advances the outer loop on unsolved subproblems, so the complexity theorem silently stops applying, and tracking cap hits per outer iteration would make this failure observable.
  • The trade-off identified in Theorem 2.5, where solving subproblems more accurately permits slower batch growth, suggests an online autotuning rule in which $\gamma_k$ is adjusted from observed KKT decay rather than fixed; that is an implementation idea the paper leaves implicit.
  • For general constraints, the absence of a bound relating true search-direction norm to KKT residual means the linear outer rate does not automatically imply linear decay of stationarity error; plotting KKT residual against outer iterations on the benchmark suite would measure that gap.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper proposes a Retrospective Approximation (RA) framework for stochastic optimization problems with deterministic nonlinear equality constraints (Section 2) and general nonlinear constraints (Section 3). In the equality-constrained setting, Framework 2.1 decouples uncertainty from optimization by solving a sequence of increasingly accurate deterministic subsampled problems with any deterministic solver, with adaptive batch-size selection and termination criteria based on KKT residuals. The paper proves outer-loop linear convergence under an adaptive sampling condition (Theorem 2.5) and total work-complexity bounds: O(epsilon^{-2}) inner iterations and O(epsilon^{-4}) gradient evaluations in expectation, and O(|S|epsilon^{-2}) gradient evaluations for finite sums (Theorem 2.8). Algorithm 2.2 instantiates the framework with a line-search SQP method and claims optimal complexity in both gradient evaluations and SQP linear system solves (Theorem 2.10). For general constraints, Algorithm 3.1 uses robust-SQP subproblems, with convergence results (Theorems 3.4 and 3.5) but no explicit complexity bound. Numerical experiments on logistic regression and CUTEst problems compare the proposed algorithms with stochastic SQP, adaptive-sampling SQP, and robust SQP baselines.

Significance. If the results hold, this is the first algorithm for equality-constrained stochastic optimization that simultaneously attains O(epsilon^{-4}) gradient-evaluation complexity and O(epsilon^{-2}) linear-system-solve complexity, which the paper correctly identifies as the gap between prior stochastic SQP methods. The paper also extends the RA paradigm to general nonlinear deterministic constraints, which is a meaningful step because RA decouples stochasticity from the deterministic solver and enables the use of advanced deterministic techniques such as L-BFGS and inexact solves. The theoretical analysis is detailed, with full proofs for most claims, and the numerical study is extensive, including performance profiles on hundreds of CUTEst problems and comparisons with established baselines. The code release promise and the explicit discussion of assumptions are strengths. However, the central complexity claims rest on Assumptions 2.5 and 2.8, both of which are strong and may fail in practically relevant regimes; additionally, the proof of Lemma 3.3 contains an incorrect displayed inequality. These issues are load-bearing and require revision.

major comments (3)
  1. [§2.4 (Assumption 2.8) and §4.2/4.3] The optimal-complexity claims for Algorithm 2.2 (Theorems 2.8 and 2.10) are proved only for runs in which every inner loop terminates by satisfying (2.3); Theorem 2.10 invokes Assumption 2.8 to guarantee this via Assumption 2.2. The paper itself states immediately after Assumption 2.8 that 'in extreme cases, this assumption may not hold for every subsampled problem,' and Section 4.2 caps the number of inner iterations per outer iteration at 500 for that reason, with the same cap used for Algorithm 3.1 in Section 4.3. When the cap binds, the inner loop exits without satisfying the KKT-residual criterion (2.3) or the search-direction criterion (3.9). Consequently, Lemma 2.2's recursive bound, the outer linear convergence of Theorem 2.5, and the O(epsilon^{-4}) gradient and O(epsilon^{-2}) linear-solve guarantees in Theorem 2.8 do not apply to the algorithm as implemented. The paper should clearly state that the complexity theorems cover the idealized algorithm with no cap, and that the 500-iteration cap is a heuristic safeguard whose effect on the guarantees is not analyzed; alternatively, it should provide conditions under which the cap is provably inactive.
  2. [§3.2, proof of Lemma 3.3] The two displayed optimality inequalities used to bound the search-direction error have the wrong sign. For a convex quadratic program with objective (d + H^{-1}g)^T H (d + H^{-1}g) minimized over a convex set, the projection inequality is (d - d^*)^T H (d^* + H^{-1}g) >= 0 for all d in the feasible set, not <= 0 as printed. The displayed inequalities are therefore not consequences of [4, Proposition 1.1.9] in the form given. The final conclusion ||d^{true}_{k,j} - d_{k,j}|| <= mu_H^{-1} ||nabla f(x_{k,j}) - g_{S_k}(x_{k,j})|| is standard and can be obtained by adding the two correctly stated optimality conditions, but the proof as written needs repair. Because Lemma 3.3 underpins Theorems 3.4 and 3.5, this is a load-bearing proof issue, not merely a typo.
  3. [Assumption 2.5 and Theorem 2.8 (part 2)] The variance lower bound Var(nabla F(x_{k,0}, xi) | F_k) >= kappa_G^2 kappa_sigma^2 is imposed at every outer iteration and is used in the proofs of Theorem 2.5 (part 2) and Theorem 2.8 (part 2) to control the batch-size growth and to derive the O(epsilon^{-4}) gradient-evaluation complexity. In many stochastic optimization problems, especially under interpolation or when the gradient noise vanishes at the optimizer, the variance tends to zero as x_{k,0} approaches the solution; this would violate the assumption precisely in the regime where the complexity bound matters. The paper's remark that 'as better solutions are found, the batch size eventually increases' is a heuristic argument, not a theorem. The paper should either identify a concrete class of problems on which the lower bound provably holds, or state how the complexity rates degrade when the lower bound fails and the batch-size sequence is chosen by a fallback rule.
minor comments (6)
  1. [Theorem 2.10] The statement of Theorem 2.10 says 'Then Algorithm 3.1 is well-posed'; in Section 2.4 this should refer to Algorithm 2.2, not Algorithm 3.1.
  2. [Paragraph after Corollary 2.6] The text refers to 'Theorem 2.6 establishes linear convergence' but the statement is Corollary 2.6; the cross-reference should be corrected.
  3. [Figure 5 caption] The caption contains a typo: 'feaibility' should be 'feasibility'.
  4. [§4.2 and §4.3] The 500-iteration cap on inner iterations is introduced as a practical safeguard, but no theorem is stated for the capped algorithm. A one-sentence clarification that the theoretical results assume the cap is never active would prevent a reader from interpreting the numerical results as covered by Theorem 2.8 when the cap binds.
  5. [Assumption 2.8] The notation kappa_H is used for the Hessian norm bound, and later kappa_HJ appears as a different constant; to avoid confusion, use distinct symbols or explicitly state the relationship between them.
  6. [Abstract and Section 1] The phrase 'withs.t.c E(x) = 0' in the abstract and in the problem statement (1.1) is missing a space; the formatting should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity claims derive from explicit recursions and independent SQP convergence analyses, not from self-imported conclusions.

full rationale

I traced the derivation chain and found no step in which a claimed prediction is equivalent to an input by construction. The outer-loop recursion in Lemma 2.2 follows from the triangle inequality together with the stated termination criterion (2.3), which measures the subsampled KKT residual and is not defined in terms of the true-problem quantity being bounded. The batch-size conditions (Conditions 2.1, 2.2, 2.3, 3.1) are sufficient conditions whose satisfiability is demonstrated explicitly in Lemmas 2.7 and 3.7; the linear-rate theorems (Theorems 2.5, 2.13, 3.5) are algebraic combinations of these bounds with the displayed parameter inequalities. The central complexity claim rests on Assumption 2.7, an O(eps^-2) inner-loop sublinear rate, and this assumption is not imported from the authors' own RA papers as a black box: Theorem 2.10 establishes it by invoking the independently authored analyses of Curtis-O'Neill-Robinson [19] and Byrd-Curtis-Nocedal [8], with Assumption 2.8 supplying the smoothness/boundedness conditions under which those published results apply. Citations to the authors' earlier RA work [40,41] are contextual, for the G_S metric and CLT-scaling terminology, and the paper re-derives its recursions rather than treating those works as the source of the main theorems. The compactness assumption and the implementation's 500-iteration cap are robustness limitations that restrict the regime in which the theorems are proved, but they do not make the theorems definitionally depend on the outcome they predict. The numerical comparisons are against external baselines and standard benchmark sets. Overall, the derivation is self-contained conditional on its stated assumptions.

Assumptions & free parameters 5 free parameters · 10 assumptions · 0 invented entities

The central claims rest on a set of standard smoothness and constraint-qualification assumptions, plus several domain assumptions specific to the RA-SQP construction. The most notable are the variance lower bound (Assumption 2.5), which the paper itself calls counterintuitive, and the closed bounded iterate assumption (Assumptions 2.8 and 3.1), which is stronger than in prior stochastic SQP work. No new physical or mathematical entities are postulated; the algorithms are constructed from existing SQP and RA components.

free parameters (5)
  • adaptive sampling theta = 0.5
    Chosen by hand for all experiments; smaller than typical values in prior work to allow larger batch adjustments. Not required by the theory, only by the practical implementation in Section 4.1.
  • batch growth limit beta = 5
    Chosen by hand to limit batch size growth between outer iterations; not load-bearing for the theory.
  • initial batch size = 32
    Default starting sample size for all algorithms; the theory requires only a finite starting size.
  • termination criterion gamma = 0.5 (for ||d||), 0.1 (for Delta l)
    User-defined contraction parameter; the theory requires gamma < 1 or gamma < (1-eta_d)/(1+eta_d) for inexact solves.
  • tolerance epsilon_k = 1e-6
    Additional tolerance in termination criteria; must decay to zero in the theory.
assumptions (10)
  • standard math Assumption 2.1: smoothness, LICQ, bounded-below objective over an open convex set
    Standard regularity conditions in constrained optimization; also used in the cited SQP literature.
  • domain assumption Assumption 2.2: inner loop terminates finitely for every outer iteration
    Guarantees the outer loop is well-defined. In practice capped at 500 inner iterations.
  • standard math Assumption 2.3: gradients of the true objective are bounded over the iterates
    Common in stochastic constrained optimization; ensures the gradient error bounds can be applied.
  • standard math Assumption 2.4: component gradients are bounded relative to the true gradient
    Similar to conditions in Friedlander-Schmidt and prior RA papers.
  • domain assumption Assumption 2.5: CLT scaling of gradient error and variance lower bound
    The variance lower bound is nonstandard and counterintuitive; the paper argues it is not a practical barrier and is only needed for the adaptive batch-size rule, not for prescribed sequences.
  • standard math Assumption 2.6: deterministic bound on the true gradient norm
    Used to derive sufficiently large batch sizes that satisfy Condition 2.1.
  • domain assumption Assumption 2.7: inner solver has sublinear O(epsilon^{-2}) convergence
    Borrowed from deterministic SQP worst-case complexity (Curtis et al. [19], Byrd et al. [8]); not proved in this paper.
  • domain assumption Assumption 2.8: iterates stay in a closed bounded convex set, all subsampled problems smooth, Hessian approximations bounded and positive definite in the null space
    Acknowledged as stronger than prior stochastic SQP assumptions; the paper states it may not hold for every subsampled problem and imposes an inner-iteration cap in practice.
  • domain assumption Assumption 3.1: analogue of 2.8 for inequality-constrained setting
    Same role for Algorithm 3.1; common in robust SQP literature.
  • standard math Assumption 3.2: extended Mangasarian-Fromovitz constraint qualification
    Standard constraint qualification ensuring bounded merit parameters and convergence to feasible or infeasible stationary points.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Retrospective Approximation Sequential Quadratic Programming for Stochastic Optimization with General Deterministic Nonlinear Constraints." pith.science (2026). https://pith.science/paper/FYL6WMT4

@misc{pith2026250519382,
  author       = {Pith},
  title        = {Pith review of: Retrospective Approximation Sequential Quadratic Programming for Stochastic Optimization with General Deterministic Nonlinear Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FYL6WMT4}},
  note         = {Machine review of arXiv:2505.19382}
}
read the original abstract

In this paper, we propose a framework based on the Retrospective Approximation (RA) paradigm to solve optimization problems with a stochastic objective function and general nonlinear deterministic constraints. This framework sequentially constructs increasingly accurate approximations of the true problems which are solved to a specified accuracy via a deterministic solver, thereby decoupling the uncertainty from the optimization. Such frameworks retain the advantages of deterministic optimization methods, such as fast convergence, while achieving the optimal performance of stochastic methods without the need to redesign algorithmic components. For problems with general nonlinear equality constraints, we present a framework that can employ any deterministic solver and analyze its theoretical work complexity. We then present an instance of the framework that employs a deterministic Sequential Quadratic Programming (SQP) method and that achieves optimal complexity in terms of gradient evaluations and linear system solves for this class of problems. For problems with general nonlinear constraints, we present an RA-based algorithm that employs an SQP method with robust subproblems. Finally, we demonstrate the empirical performance of the proposed framework on multi-class logistic regression problems and benchmark instances from the CUTEst test set, comparing its results to established methods from the literature.

Figures

Figures reproduced from arXiv: 2505.19382 by the authors.

Figure 1
Figure 1. Constraint violation (∥c(x)∥∞) and Lagrangian gradient norm (∥∇xL(x, λ∗ )∥∞) with op￾timized dual variable λ ∗ , with respect to number of gradient evaluations and number of MINRES iterations for stochastic SQP ( “S-SQP” [2]), adaptive sampling SQP (“AS-SQP” [1]), deterministic SQP (“SQP” [2, 42]) and our proposed algorithms “RA-SQP ∥d∥”, “RA-SQP ∆l”, and “RA-SQP ∆l Inexact” over the multi-class logistic regression … view at source ↗
Figure 2
Figure 2. Constraint violation (∥c(x)∥∞) and Lagrangian gradient norm (∥∇xL(x, λ∗ )∥∞) with op￾timized dual variable λ ∗ , with respect to number of gradient evaluations and number of MINRES iterations for stochastic SQP ( “S-SQP” [2]), adaptive sampling SQP (“AS-SQP” [1]), deterministic SQP (“SQP” [2, 42]) and our proposed algorithms “RA-SQP ∥d∥”, “RA-SQP ∆l”, and “RA-SQP ∆l Inexact” over the multi-class logistic regression … view at source ↗
Figure 3
Figure 3. Constraint violation (∥c(x)∥∞) and Lagrangian gradient norm (∥∇xL(x, λ∗ )∥∞) with optimized dual variable λ ∗ , with respect to number of gradient evaluations and number of MINRES iterations for “RA-SQP ∆l” with and without L-BFGS approximations and exact and inexact SQP linear system solutions over the multi-class logistic regression problem (4.1) with equality regularization constraints for the mnist dataset (nf =… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Number of Inner Iterations (Nk) and Batch Size (|Sk|) with respect to outer iterations and number of gradient evaluations for “RA-SQP ∆l” with and without L-BFGS approximations and exact and inexact SQP linear system solutions over the multi-class logistic regression p…
Figure 5
Figure 5. Figure 5: Performance profiles for feaibility and stationarity errors with respect to number of [PITH_FULL_IMAGE:figures/full_fig_p048_5.png]
Figure 6
Figure 6. Figure 6: Constraint violation (∥[cI (x)]+∥∞) and KKT residual (4.3) with respect to number of gradient evaluations and number of Barrier iterations for stochastic SQP ( “S-SQP” [21]), robust stochastic SQP ( “Robust-S-SQP” [54]), deterministic robust SQP (“Robust-SQP-l∞” and “R…
Figure 7
Figure 7. Figure 7: Constraint violation (∥[cI (x)]+∥∞) and KKT residual (4.3) with respect to number of gradient evaluations and number of Barrier iterations for stochastic SQP ( “S-SQP” [21]), robust stochastic SQP ( “Robust-S-SQP” [54]), deterministic robust SQP (“Robust-SQP-l∞” and “R…
Figure 8
Figure 8. Figure 8: Performance profiles for feasibility and stationarity errors with respect to number of [PITH_FULL_IMAGE:figures/full_fig_p052_8.png]
Figure 9
Figure 9. Figure 9: Constraint violation and optimal set similarity with respect to number of outer iterations [PITH_FULL_IMAGE:figures/full_fig_p054_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 56 canonical work pages

  1. [1]

    An adaptive sampling sequen- tial quadratic programming method for equality constrained stochastic optimization.arXiv preprint arXiv:2206.00712, 2022

    Albert S Berahas, Raghu Bollapragada, and Baoyu Zhou. An adaptive sampling sequen- tial quadratic programming method for equality constrained stochastic optimization.arXiv preprint arXiv:2206.00712, 2022

    arXiv 2022

  2. [2]

    Sequential quadratic optimization for nonlinear equality constrained stochastic optimization.SIAM Journal on Optimization, 31(2):1352–1379, 2021

    Albert S Berahas, Frank E Curtis, Daniel Robinson, and Baoyu Zhou. Sequential quadratic optimization for nonlinear equality constrained stochastic optimization.SIAM Journal on Optimization, 31(2):1352–1379, 2021

    2021

  3. [3]

    Albert S Berahas, Miaolan Xie, and Baoyu Zhou. A sequential quadratic programming method with high-probability complexity bounds for nonlinear equality-constrained stochastic opti- mization.SIAM Journal on Optimization, 35(1):240–269, 2025

    work page 2025

  4. [4]

    Athena Scientific, Belmont, Mas- sachusetts, 2009

    Dimitri Bertsekas.Convex optimization theory, volume 1. Athena Scientific, Belmont, Mas- sachusetts, 2009

    work page 2009

  5. [5]

    Adaptive sampling strategies for stochastic optimization.SIAM Journal on Optimization, 28(4):3312–3343, 2018

    Raghu Bollapragada, Richard Byrd, and Jorge Nocedal. Adaptive sampling strategies for stochastic optimization.SIAM Journal on Optimization, 28(4):3312–3343, 2018

    work page 2018

  6. [6]

    A robust sequential quadratic programming method

    James V Burke and Shih-Ping Han. A robust sequential quadratic programming method. Mathematical Programming, 43(1):277–303, 1989

    work page 1989

  7. [7]

    Sample size selection in optimization methods for machine learning.Mathematical programming, 134(1):127–155, 2012

    Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning.Mathematical programming, 134(1):127–155, 2012

    work page 2012

  8. [8]

    An inexact sqp method for equality constrained optimization.SIAM Journal on Optimization, 19(1):351–369, 2008

    Richard H Byrd, Frank E Curtis, and Jorge Nocedal. An inexact sqp method for equality constrained optimization.SIAM Journal on Optimization, 19(1):351–369, 2008

    work page 2008

Show all 69 references
  1. [9]

    An inexact newton method for nonconvex equality constrained optimization.Mathematical programming, 122(2):273–299, 2010

    Richard H Byrd, Frank E Curtis, and Jorge Nocedal. An inexact newton method for nonconvex equality constrained optimization.Mathematical programming, 122(2):273–299, 2010

    2010

  2. [10]

    On the global convergence of trust region algorithms using inexact gradient information.SIAM Journal on Numerical Analysis, 28(1):251–265, 1991

    Richard G Carter. On the global convergence of trust region algorithms using inexact gradient information.SIAM Journal on Numerical Analysis, 28(1):251–265, 1991

    1991

  3. [11]

    LIBSVM: A library for support vector machines.ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011

    Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines.ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm. 55

    2011

  4. [12]

    Constraint-aware deep neural network compression

    Changan Chen, Frederick Tung, Naveen Vedula, and Greg Mori. Constraint-aware deep neural network compression. InProceedings of the European Conference on Computer Vision (ECCV), pages 400–415, 2018

    2018

  5. [13]

    Retrospective approximation algorithms for stochastic root finding

    Huifen Chen and Bruce W Schmeiser. Retrospective approximation algorithms for stochastic root finding. InProceedings of Winter Simulation Conference, pages 255–261. IEEE, 1994

    1994

  6. [14]

    Stochastic root finding via retrospective approximation

    Huifen Chen and Bruce W Schmeiser. Stochastic root finding via retrospective approximation. IIE Transactions, 33(3):259–275, 2001

    2001

  7. [15]

    An interior-point algorithm for continuous nonlinearly constrained optimization with noisy function and derivative evaluations

    Frank E Curtis, Shima Dezfulian, and Andreas Waechter. An interior-point algorithm for continuous nonlinearly constrained optimization with noisy function and derivative evaluations. arXiv preprint arXiv:2502.11302, 2025

    2025 arXiv

  8. [16]

    Single-loop deterministic and stochastic interior- point algorithms for nonlinearly constrained optimization.arXiv preprint arXiv:2408.16186, 2024

    Frank E Curtis, Xin Jiang, and Qi Wang. Single-loop deterministic and stochastic interior- point algorithms for nonlinearly constrained optimization.arXiv preprint arXiv:2408.16186, 2024

    2024 arXiv

  9. [17]

    A stochastic- gradient-based interior-point algorithm for solving smooth bound-constrained optimization problems.arXiv preprint arXiv:2304.14907, 2023

    Frank E Curtis, Vyacheslav Kungurtsev, Daniel P Robinson, and Qi Wang. A stochastic- gradient-based interior-point algorithm for solving smooth bound-constrained optimization problems.arXiv preprint arXiv:2304.14907, 2023

    2023 arXiv

  10. [18]

    A matrix-free algorithm for equality constrained optimization problems with rank-deficient jacobians.SIAM Journal on Optimiza- tion, 20(3):1224–1249, 2010

    Frank E Curtis, Jorge Nocedal, and Andreas W¨ achter. A matrix-free algorithm for equality constrained optimization problems with rank-deficient jacobians.SIAM Journal on Optimiza- tion, 20(3):1224–1249, 2010

    2010

  11. [19]

    Worst-case complexity of an sqp method for nonlinear equality constrained stochastic optimization.Mathematical Programming, 205(1):431–483, 2024

    Frank E Curtis, Michael J O’Neill, and Daniel P Robinson. Worst-case complexity of an sqp method for nonlinear equality constrained stochastic optimization.Mathematical Programming, 205(1):431–483, 2024

    2024

  12. [20]

    Frank E Curtis, Daniel P Robinson, and Baoyu Zhou. Inexact sequential quadratic optimiza- tion for minimizing a stochastic objective function subject to deterministic nonlinear equality constraints.arXiv preprint arXiv:2107.03512, 2021

    2021 arXiv

  13. [21]

    Sequential quadratic optimization for stochastic optimization with deterministic nonlinear inequality and equality constraints.SIAM Journal on Optimization, 34(4):3592–3622, 2024

    Frank E Curtis, Daniel P Robinson, and Baoyu Zhou. Sequential quadratic optimization for stochastic optimization with deterministic nonlinear inequality and equality constraints.SIAM Journal on Optimization, 34(4):3592–3622, 2024

    2024

  14. [22]

    Variable-number sample-path optimization.Mathematical Programming, 117(1-2):81–109, 2009

    Geng Deng and Michael C Ferris. Variable-number sample-path optimization.Mathematical Programming, 117(1-2):81–109, 2009

    2009

  15. [23]

    On the convergence of interior-point meth- ods for bound-constrained nonlinear optimization problems with noise.arXiv preprint arXiv:2405.11400, 2024

    Shima Dezfulian and Andreas W¨ achter. On the convergence of interior-point meth- ods for bound-constrained nonlinear optimization problems with noise.arXiv preprint arXiv:2405.11400, 2024

    2024 arXiv

  16. [24]

    Benchmarking optimization software with performance profiles.Mathematical programming, 91:201–213, 2002

    Elizabeth D Dolan and Jorge J Mor´ e. Benchmarking optimization software with performance profiles.Mathematical programming, 91:201–213, 2002

    2002

  17. [25]

    Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems.SIAM Jour- nal on Optimization, 34(2):2007–2037, 2024

    Yuchen Fang, Sen Na, Michael W Mahoney, and Mladen Kolar. Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems.SIAM Jour- nal on Optimization, 34(2):2007–2037, 2024. 56

    2007

  18. [26]

    Hybrid deterministic-stochastic methods for data fitting.SIAM Journal on Scientific Computing, 34(3):A1380–A1405, 2012

    Michael P Friedlander and Mark Schmidt. Hybrid deterministic-stochastic methods for data fitting.SIAM Journal on Scientific Computing, 34(3):A1380–A1405, 2012

    2012

  19. [27]

    Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization.Mathematical Programming, 155(1- 2):267–305, 2016

    Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization.Mathematical Programming, 155(1- 2):267–305, 2016

    2016

  20. [28]

    S2mpj and cutest optimization problems for matlab, python and julia.arXiv preprint arXiv:2407.07812, 2024

    Serge Gratton and Philippe L Toint. S2mpj and cutest optimization problems for matlab, python and julia.arXiv preprint arXiv:2407.07812, 2024

    2024 arXiv

  21. [29]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024

    2024

  22. [30]

    A globally convergent method for nonlinear programming.Journal of opti- mization theory and applications, 22(3):297–309, 1977

    Shih-Ping Han. A globally convergent method for nonlinear programming.Journal of opti- mization theory and applications, 22(3):297–309, 1977

    1977

  23. [31]

    eg-vssa: An extragradient variable sample-size stochastic approximation scheme: Error analysis and complexity trade-offs

    Afrooz Jalilzadeh and Uday V Shanbhag. eg-vssa: An extragradient variable sample-size stochastic approximation scheme: Error analysis and complexity trade-offs. In2016 Winter Simulation Conference (WSC), pages 690–701. IEEE, 2016

    2016

  24. [32]

    End-to-end constrained optimization learning: A survey.arXiv preprint arXiv:2103.16378, 2021

    James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey.arXiv preprint arXiv:2103.16378, 2021

    2021 arXiv

  25. [33]

    An optimal method for stochastic composite optimization.Mathematical Programming, 133(1-2):365–397, 2012

    Guanghui Lan. An optimal method for stochastic composite optimization.Mathematical Programming, 133(1-2):365–397, 2012

    2012

  26. [34]

    Springer, Atlanta, USA, 2020

    Guanghui Lan.First-order and stochastic optimization methods for machine learning, volume 1. Springer, Atlanta, USA, 2020

    2020

  27. [35]

    A survey on datasets for fairness-aware machine learning.Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(3):e1452, 2022

    Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning.Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(3):e1452, 2022

    2022

  28. [36]

    A survey on bias and fairness in machine learning.ACM computing surveys (CSUR), 54(6):1–35, 2021

    Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning.ACM computing surveys (CSUR), 54(6):1–35, 2021

    2021

  29. [37]

    An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians.Mathematical Programming, 199(1-2):721–791, 2023

    Sen Na, Mihai Anitescu, and Mladen Kolar. An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians.Mathematical Programming, 199(1-2):721–791, 2023

    2023

  30. [38]

    Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programming.Mathematical Programming, 202(1):279–353, 2023

    Sen Na, Mihai Anitescu, and Mladen Kolar. Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programming.Mathematical Programming, 202(1):279–353, 2023

    2023

  31. [39]

    A primal dual formulation for deep learning with constraints.Advances in Neural Information Processing Systems, 32, 2019

    Yatin Nandwani, Abhishek Pathak, and Parag Singla. A primal dual formulation for deep learning with constraints.Advances in Neural Information Processing Systems, 32, 2019

    2019

  32. [40]

    PhD thesis, Purdue University, 2023

    David Newton.Retrospective approximation for smooth stochastic optimization. PhD thesis, Purdue University, 2023. 57

    2023

  33. [41]

    A retrospec- tive approximation approach for smooth stochastic optimization.Mathematics of Operations Research, 2024

    David Newton, Raghu Bollapragada, Raghu Pasupathy, and Nung Kwan Yip. A retrospec- tive approximation approach for smooth stochastic optimization.Mathematics of Operations Research, 2024

    2024

  34. [42]

    Numerical optimization 2nd edition springer.New York, 2006

    J Nocedal and SJ Wright. Numerical optimization 2nd edition springer.New York, 2006

    2006

  35. [43]

    Fast unconstrained optimization via hessian averaging and adaptive gradient sampling methods.arXiv preprint arXiv:2408.07268, 2024

    Thomas O’Leary-Roseberry and Raghu Bollapragada. Fast unconstrained optimization via hessian averaging and adaptive gradient sampling methods.arXiv preprint arXiv:2408.07268, 2024

    2024 arXiv

  36. [44]

    PhD thesis, Ph

    EO Omojokun.Trust region algorithm for optimization with equalities and inequalities con- straints. PhD thesis, Ph. D Thesis, University of Cororado at Boulder, 1989

    1989

  37. [45]

    A two stepsize sqp method for nonlinear equality constrained stochastic optimization.arXiv preprint arXiv:2408.16656, 2024

    Michael J O’Neill. A two stepsize sqp method for nonlinear equality constrained stochastic optimization.arXiv preprint arXiv:2408.16656, 2024

    2024 arXiv

  38. [46]

    On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization.Operations Research, 58(4-part-1):889– 901, 2010

    Raghu Pasupathy. On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization.Operations Research, 58(4-part-1):889– 901, 2010

    2010

  39. [47]

    An introspective on the retrospective-approximation paradigm

    Raghu Pasupathy. An introspective on the retrospective-approximation paradigm. InProceed- ings of the 2011 Winter Simulation Conference (WSC), pages 412–421. IEEE, 2011

    2011

  40. [48]

    Adaptive sequential sample average approximation for solving two-stage stochastic linear programs.SIAM Journal on Optimization, 31(1):1017–1048, 2021

    Raghu Pasupathy and Yongjia Song. Adaptive sequential sample average approximation for solving two-stage stochastic linear programs.SIAM Journal on Optimization, 31(1):1017–1048, 2021

    2021

  41. [49]

    Large-scale portfolio optimization.Management science, 30(10):1143–1160, 1984

    Andre F Perold. Large-scale portfolio optimization.Management science, 30(10):1143–1160, 1984

    1984

  42. [50]

    Optimal control of uncertain systems using sample average approximations.SIAM Journal on Control and Optimization, 54(1):1–29, 2016

    Chris Phelps, Johannes O Royset, and Qi Gong. Optimal control of uncertain systems using sample average approximations.SIAM Journal on Control and Optimization, 54(1):1–29, 2016

    2016

  43. [51]

    Efficient sample sizes in stochastic nonlinear programming.Journal of Computational and Applied Mathematics, 217(2):301–310, 2008

    E Polak and JO Royset. Efficient sample sizes in stochastic nonlinear programming.Journal of Computational and Applied Mathematics, 217(2):301–310, 2008

    2008

  44. [52]

    A fast algorithm for nonlinearly constrained optimization calculations

    Michael JD Powell. A fast algorithm for nonlinearly constrained optimization calculations. In Numerical Analysis: Proceedings of the Biennial Conference Held at Dundee, June 28–July 1, 1977, pages 144–157. Springer, 2006

    1977

  45. [53]

    A recursive quadratic programming algorithm that uses differentiable exact penalty functions.Mathematical programming, 35:265–278, 1986

    Michael JD Powell and YJMP Yuan. A recursive quadratic programming algorithm that uses differentiable exact penalty functions.Mathematical programming, 35:265–278, 1986

    1986

  46. [54]

    Songqiang Qiu and Vyacheslav Kungurtsev. A sequential quadratic programming method for optimization with stochastic objective functions, deterministic inequality constraints and robust subproblems.arXiv preprint arXiv:2302.07947, 2023

    2023 arXiv

  47. [55]

    Explicitly imposing constraints in deep networks via conditional gradients gives improved generalization and faster convergence

    Sathya N Ravi, Tuan Dinh, Vishnu Suresh Lokhande, and Vikas Singh. Explicitly imposing constraints in deep networks via conditional gradients gives improved generalization and faster convergence. InProceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages...

    2019

  48. [56]

    Geometry aware con- strained optimization techniques for deep learning

    Soumava Kumar Roy, Zakaria Mhammedi, and Mehrtash Harandi. Geometry aware con- strained optimization techniques for deep learning. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 4460–4469, 2018

    2018

  49. [57]

    Optimal design with proba- bilistic objective and constraints.Journal of Engineering Mechanics, 132(1):107–118, 2006

    Johannes O Royset, Armen Der Kiureghian, and Elijah Polak. Optimal design with proba- bilistic objective and constraints.Journal of Engineering Mechanics, 132(1):107–118, 2006

    2006

  50. [58]

    SIAM, Philadelphia, PA, 2021

    Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski.Lectures on stochastic pro- gramming: modeling and theory. SIAM, Philadelphia, PA, 2021

    2021

  51. [59]

    Stochastic optimal power flow based on conditional value at risk and distributional robustness.International Journal of Electrical Power & Energy Systems, 72:116–125, 2015

    Tyler Summers, Joseph Warrington, Manfred Morari, and John Lygeros. Stochastic optimal power flow based on conditional value at risk and distributional robustness.International Journal of Electrical Power & Energy Systems, 72:116–125, 2015

    2015

  52. [60]

    Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, St´ efan J

    Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, St´ efan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson,...

    2020

  53. [61]

    PhD thesis, Naval Postgraduate School, 2009

    David A Vondrak and R Kevin Wood.Adaptive Selections of Sample Size and Solver Iterations in Stochastic Optimization with Application to Nonlinear Commodity Flow Problems. PhD thesis, Naval Postgraduate School, 2009

    2009

  54. [62]

    Penalty methods with stochastic approximation for stochastic nonlinear programming.Mathematics of computation, 86(306):1793–1820, 2017

    Xiao Wang, Shiqian Ma, and Ya-xiang Yuan. Penalty methods with stochastic approximation for stochastic nonlinear programming.Mathematics of computation, 86(306):1793–1820, 2017

    2017

  55. [63]

    Physics-constrained machine learning of evapotran- spiration.Geophysical Research Letters, 46(24):14496–14507, 2019

    Wen Li Zhao, Pierre Gentine, Markus Reichstein, Yao Zhang, Sha Zhou, Yeqiang Wen, Changjie Lin, Xi Li, and Guo Yu Qiu. Physics-constrained machine learning of evapotran- spiration.Geophysical Research Letters, 46(24):14496–14507, 2019. A Technical Results We present some techn...

    2019

  56. [64]

    For the finite-sum problem(1.2): For allk≥0, if termination criterion parameters are chosen as0≤γ k ≤γ < 1−ηd 1+ηd ,ϵ k =ω∥∇f(x k,0)−g Sk (xk,0)∥+ ˆωβk withω,ˆω≥0and Condition 2.2 parameters are chosen such thata 1 = 1 1−ηd h γ(1 +η d) +θ ω+ (γ+ ˆθ) 1+ηd κHJ i <1, then, the tr...

  57. [65]

    60 Proof.The proof follows a similar procedure to Theorem 2.5

    For the expectation problem(1.3): For allk≥0, if Assumption 2.5 holds, the termination cri- terion parameters are chosen as0≤γ k ≤˜γ <1−ηd 1+ηd ,ϵ k = ˜ω q Var(∇F(xk,0)|Fk) |Sk| where˜ω≥0and Condition 2.2 parameters are chosen such that˜a1 = 1 1−ηd h ˜γ(1 +ηd) + ˜θ ˜ω+1+ηd κHJ...

  58. [66]

    For the finite-sum problem(1.2): If the batch size is selected as|S k|=⌈(1−β k)|S|⌉withβ∈ (0,1)and termination criterion parameters are chosen as0≤ {γ k} ≤γ <1,ϵk =ω 1− |Sk| |S| withω≥0, then the true search direction norm converges to zero at a linear rate across outer iterat...

  59. [67]

    Proof.The proof follows from the same procedure as Theorem 2.6

    For the expectation problem(1.3): If Assumption 2.5 is satisfied, the sample set size is chosen as|S k+1|= l |Sk| ˜β2 m with ˜β∈(0,1)and the termination criterion parameters are chosen such that0≤ {γk} ≤˜γ <1,ϵk = ˜ω√ |Sk| where˜ω≥0, then the true search direction norm converg...

  60. [68]

    For the finite-sum problem(1.2): Fork≥0, Condition 3.1 is satisfied if |Sk| ≥ |S| 1− r θ2∥dtrue k,0 ∥2+a2β2k 4(ω2 1 κ2g+ω2 2 ) ! with ˆθ= 1. 62

  61. [69]

    For the expectation problem(1.3): Fork≥0, Condition 3.1 is satisfied if |Sk| ≥ ˜ω2 1 κ2 g+˜ω2 2 ˜θ2∥dtrue k,0 ∥2+˜a2 ˜β2k . Proof.Similar to the procedure employed in Theorem 2.7, for the finite-sum problem (1.2), from Assumption 2.4 ∥∇f(x k,0)−g Sk (xk,0)∥ 2 ≤4 1− |Sk| |S| 2 ...

Pith tools

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