Pith. sign in

REVIEW 26 references

ProxSTORM -- A Stochastic Trust-Region Algorithm for Nonsmooth Optimization

T0 review · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read ProxSTORM proves a stochastic trust-region method converges globally and needs O(ε^{-2}) iterations to reach ε-stationarity.

arxiv 2510.03187 v2 pith:HACSSUY3 submitted 2025-10-03 math.OC

Robert J. Baraldi , Aurya Javeed , Drew P. Kouri , Katya Scheinberg This is my paper · ORCID
classification math.OC MSC 90C1590C2665K05
keywords stochastictrust-regionmethodnonsmoothoptimizationcompositeproximalgradientglobalconvergenceexpectedcomplexitymartingaleanalysisSTORM
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

The paper develops ProxSTORM, a stochastic trust-region algorithm for minimizing the sum of a smooth, possibly nonconvex stochastic function and a convex, possibly nonsmooth deterministic function. Its central claim is that, under probabilistic accuracy assumptions on the random models and computed reductions, the trust-region radius collapses to zero almost surely, the proximal-gradient measure ∥h(X_k)∥ converges to zero, and the expected number of iterations to reach ∥h(X_k)∥ ≤ ε is O(ε^{-2}). If correct, ProxSTORM is the first stochastic trust-region method with these guarantees for the composite nonsmooth problem, and it reduces to the earlier STORM method when the nonsmooth term vanishes. The proof works by showing that a weighted combination of objective value and trust-region radius decreases in expectation at each iteration, then converting that decrease into global convergence and a stopping-time complexity bound. A sympathetic reader would care because the result extends the theoretical comfort zone of stochastic trust-region methods to a problem class that includes ℓ1-regularized training and PDE-constrained topology optimization under uncertainty.

What carries the argument

The central mechanism is the Lyapunov function Ψ_k = ν(f(X_k) + φ(X_k)) + (1 − ν)Δ_k². Theorem 3 shows E[Ψ_{k+1} − Ψ_k | F_{k−1}] ≤ −ΘΔ_k² under Assumptions 1–6. The proof partitions the probability space into events where the random model gradient is accurate (I_k), where the computed reduction is accurate (J_k), and where the true proximal gradient is large (B_k). Nonexpansiveness of the proximal map transfers gradient accuracy of the model to accuracy of the proximal-gradient stationarity measure, Lemma 9 forces a successful step when ∥h(X_k)∥ is large and both accuracy events hold, and a submartingale driven by 2·1_{I_k∩J_k} − 1 converts the almost-sure decay of Δ_k into lim inf and then

What would settle it

Construct or identify a stochastic model and computed-reduction pair satisfying Assumptions 1–4 and 6 but violating Assumption 5, and run ProxSTORM with dynamic sampling; if the trust-region radius does not converge to zero or liminf ∥h(X_k)∥ > 0 with positive probability, the expected-decrease theorem fails. A more direct check is to evaluate E[−A_k 1_{S_k ∩ J_k^c} | F_{k−1/2}] on the topology example with a small fixed sample size and compare it against the claimed c1Δ_k² + c2∥h(X_k)∥Δ_k upper bound.

Watch

Extended reading notes

Core claim

The core discovery is that the STORM martingale argument extends to the composite problem f + φ when the stationarity measure is the proximal gradient h(x) = (x − prox_{rφ}(x − r∇f(x)))/r and the algorithm accepts steps only when the computed reduction is a sufficient fraction of predicted reduction and the trust-region radius is small relative to ∥h_k∥. Under Assumptions 1–6, ProxSTORM achieves lim_{k→∞} ∥h(X_k)∥ = 0 with probability one and E[T_ε] = O(ε^{-2}), where T_ε is the first iteration with ∥h(X_k)∥ ≤ ε. The novelty is not the algorithm template, which combines existing trust-region elements, but the proof that stochastic model inaccuracy and computed-reduction inaccuracy can be han

Load-bearing premise

The proof stands or falls on Assumption 5: when a step is accepted even though the computed reduction is inaccurate, the true objective must not increase faster than a quadratic in the trust-region radius plus a linear term in the stationarity measure; the paper does not show this bound holds in its own numerical experiments.

Editorial extensions

If this is right

  • If ProxSTORM's guarantees hold, stochastic trust-region methods become viable for composite objectives f + φ with the same O(ε^{-2}) expected-iteration bound that holds for smooth stochastic first-order methods.
  • When φ ≡ 0, ProxSTORM recovers STORM's convergence and complexity results, while simplifying the computed-reduction accuracy condition by measuring it relative to predicted reduction rather than Δ_k².
  • The almost-sure collapse of the trust-region radius to zero implies the algorithm must reject steps infinitely often, a stochastic analogue of Robbins–Monro conditions.
  • Limit-type convergence means that every convergent realization eventually drives the proximal-gradient norm to zero, a stronger guarantee than typical stochastic first-order methods provide.
  • The expected iteration count to first satisfy ∥h(X_k)∥ ≤ ε is proportional to ε^{-2}, with constants tracked explicitly in terms of model curvature, accuracy probabilities, and acceptance parameters.

Reading between the lines

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

  • The numerical demonstrations use a fixed sample size per iteration, whereas Appendix A shows the analysis requires sample sizes growing as Δ_k → 0; the experiments should therefore be read as heuristic evidence rather than verification of the assumptions.
  • Because Assumption 5 is only shown to follow from the deterministic inexactness condition |cred − ared| ≤ κ_obj (min{pred, θ})^μ when θ_k → 0, a testable extension is to combine ProxSTORM's acceptance rule with a deterministic error indicator that drives θ_k to zero, removing one stochastic assumption.
  • The proof's reliance on prox nonexpansiveness suggests the analysis may transfer to Hilbert or Banach settings where the proximal mapping is firmly nonexpansive, potentially covering a broader class of PDE-constrained stochastic optimization problems.
  • A natural next experiment is to measure the empirical sample-size trajectory implied by the dynamic-sampling routine in Appendix A and compare it with fixed-budget ProxSTORM runs, testing whether dynamic sampling changes the observed ε-stationarity iteration count.
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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation found; the algorithm and proof are genuine extensions with independently stated assumptions and a transferred, published complexity theorem.

full rationale

The paper's derivation is not circular. ProxSTORM's central result (Theorem 19) is an expected-complexity bound obtained by importing a published generic stochastic-trust-region theorem, [2, Theorem 2], and verifying its conditions for the new algorithm: Theorem 3 supplies the Lyapunov decrease and Proposition 20 supplies the radius condition. The citation is therefore a real transfer result, not a restatement of the target conclusion, and the assumptions (Assumptions 3-5, especially the new Assumption 5 on the expected increase on inaccurate successful steps) are nontrivial inputs rather than renamed versions of the convergence claim. Proposition 2 shows Assumption 5 is implied by a standard smooth descent inequality or by the usual stochastic inexactness condition, so it is not tailored to force the theorem. The paper also explicitly acknowledges that the fixed-sample numerical experiments deviate from the sampling assumptions and provides Appendix A for dynamic sampling; the numerics are not presented as the proof of any theorem. No equation in the manuscript reduces to its own input by construction, and no load-bearing argument depends on an unverified self-citation.

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

No new physical or mathematical entities; Assumption 5 is an assumption on existing quantities, not an entity. The proof relies on standard martingale and prox-nonexpansivity results, plus the probabilistic oracle assumptions and the new Assumption 5.

free parameters (5)
  • α, β (accuracy probabilities) = not specified; must be 'sufficiently close to one' and satisfy (39), (41)
    Introduced ad hoc to make the Lyapunov decrease and complexity proof work; they are existence parameters, not data-fitted.
  • Θ, ζ, ν (analysis constants) = existential; constrained by (20), (26), (41)
    Chosen to partition the probability space and balance positive/negative Lyapunov increments; no independent physical/statistical meaning.
  • c1, c2 (Assumption 5 constants) = existential; in the smooth case c1=L/2(1-β), c2=(1-β)
    Bound the expected objective increase on accepted steps with inaccurate computed reductions; load-bearing for Theorem 3.
  • κgrad, κbmh, κfcd (model and subproblem constants) = not fixed; bound gradient-model error, curvature, Cauchy decrease
    Introduced in Assumptions 2–3 and condition (S2); user or analysis must know finite bounds.
  • η1, η, η2, γ, δmax (algorithm hyperparameters) = experiments: η1=0.5, η2=5e-5, γ=5, δmax=1e10
    User-specified trust-region parameters; standard hyperparameters, not fitted to the objective.
assumptions (8)
  • domain assumption Assumption 1: f is L-smooth on dom φ, φ is proper closed convex, f+φ is bounded below.
    Defines the problem class (1); the proximal mapping of φ is assumed computable.
  • domain assumption Assumption 2: 1+b_k ≤ κbmh uniformly (bounded model curvature).
    Restricts admissible stochastic models; standard for trust-region analysis.
  • domain assumption Assumption 3: P(I_k|F_{k-1}) ≥ α for I_k={∥∇M_k(X_k)-∇f(X_k)∥≤κgradΔ_k}.
    Probabilistic oracle for model gradient accuracy; required for Lemma 1 and Propositions 5/6.
  • domain assumption Assumption 4: P(J_k|F_{k-1/2}) ≥ β for J_k={|A_k-C_k|≤ηP_k}.
    Probabilistic oracle for computed-reduction accuracy; required for acceptance control.
  • ad hoc to paper Assumption 5: E[-A_k 1_{S_k∩J_k^c}|F_{k-1/2}] ≤ c1Δ_k²+c2∥h(X_k)∥Δ_k.
    New, tailored to the proof; bounds the bad-event objective increase. Not verified numerically.
  • ad hoc to paper Assumption 6: α and β satisfy (39) and (41).
    Existence of sufficiently high accuracy probabilities; used in Theorem 3.
  • standard math Submartingale convergence theorem and nonexpansivity of prox.
    Used in Corollary 14, Theorem 17, and Appendix B.
  • standard math Theorem 2 of Blanchet et al. [2] for expected complexity.
    Black-box stopping-time bound; prior published result by overlapping authors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of ProxSTORM -- A Stochastic Trust-Region Algorithm for Nonsmooth Optimization." pith.science (2026). https://pith.science/paper/HACSSUY3

@misc{pith2026251003187,
  author       = {Pith},
  title        = {Pith review of: ProxSTORM -- A Stochastic Trust-Region Algorithm for Nonsmooth Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HACSSUY3}},
  note         = {Machine review of arXiv:2510.03187}
}
read the original abstract

We develop a stochastic trust-region algorithm for minimizing the sum of a Lipschitz-smooth but possibly nonconvex function and a convex but possibly nonsmooth function. Such a problem class arises in many applications, including data science, operations research, and PDE-constrained optimization. This algorithm, which we call ProxSTORM, generalizes STORM [15,11]-a stochastic trust-region algorithm for the unconstrained optimization of smooth functions-and the inexact deterministic proximal trust-region algorithm in [5]. In the absence of a nonsmooth term, we recover the original STORM algorithm, moreover, we improve and simplify certain aspects of STORM analysis, while maintaining STORM martingale framework arguments to prove global convergence and an expected complexity bound. We demonstrate ProxSTORM capabilities on neural network training and topology optimization under uncertainty.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 3 linked inside Pith

  1. [1]

    Mathematical Programming 169, 447–487 (2018)

    Chen, R., Menickelly, M., Scheinberg, K.: Stochastic optimization us ing a trust- region method and random models. Mathematical Programming 169, 447–487 (2018)

    2018

  2. [2]

    INFOR MS Journal on Optimization 1(2), 92–119 (2019) https://doi.org/10.1287/ijoo.2019.0016

    Blanchet, J., Cartis, C., Menickelly, M., Scheinberg, K.: Convergen ce rate analysis of a stochastic trust-region method via supermartingales. INFOR MS Journal on Optimization 1(2), 92–119 (2019) https://doi.org/10.1287/ijoo.2019.0016

    arXiv 2019

  3. [3]

    Mathem atical Programming 201(1), 1–40 (2022)

    Baraldi, R.J., Kouri, D.P.: A proximal trust-region method for nons mooth optimization with inexact function and gradient evaluations. Mathem atical Programming 201(1), 1–40 (2022)

    2022

  4. [4]

    CMS Books in Mathematics

    Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone O perator The- ory in Hilbert Spaces. CMS Books in Mathematics. Springer, Cham, Sw itzerland (2017)

    2017

  5. [5]

    SIAM Journal on Optimization 31(2), 1352–1379 (2021)

    Berahas, A.S., Curtis, F.E., Robinson, D.P., Zhou, B.: Sequential Qu adratic Optimization for Nonlinear Equality Constrained Stochastic Optimizat ion. SIAM Journal on Optimization 31(2), 1352–1379 (2021)

    2021

  6. [6]

    arXiv 2408.16186 (2024)

    Curtis, F.E., Jiang, X., Wang, Q.: Single-Loop Deterministic and Stoc has- tic Interior-Point Algorithms for Nonlinearly Constrained Optimizatio n. arXiv 2408.16186 (2024). https://arxiv.org/abs/2408.16186

    arXiv 2024

  7. [7]

    arXiv 2304.14907 (2023)

    Curtis, F.E., Kungurtsev, V., Robinson, D.P., Wang, Q.: A Stochast ic-Gradient- based Interior-Point Algorithm for Solving Smooth Bound-Constra ined Optimiza- tion Problems. arXiv 2304.14907 (2023). https://arxiv.org/abs/2304.14907

    arXiv 2023

  8. [8]

    Ma thematical Programming 207(1), 55–106 (2024)

    Cao, L., Berahas, A.S., Scheinberg, K.: First-and second-order high probability complexity bounds for trust-region methods with noisy oracles. Ma thematical Programming 207(1), 55–106 (2024)

    2024

Show all 26 references
  1. [9]

    MA Journal of Numerical Analysis (2017)

    Gratton, S., Royer, C.W., Vicente, L.N., Zhang, Z.: Complexity and g lobal rates of trust-region methods based on probabilistic models. MA Journal of Numerical Analysis (2017)

    2017

  2. [10]

    Societ y for Indus- trial and Applied Mathematics, Philadelphia, PA (2000)

    Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. Societ y for Indus- trial and Applied Mathematics, Philadelphia, PA (2000). https://doi.org/10. 1137/1.9780898719857

    2000

  3. [11]

    Computational Optimization and Applications , 1–34 (2025)

    Baraldi, R.J., Kouri, D.P.: Efficient proximal subproblem solvers for a nonsmooth trust-region method. Computational Optimization and Applications , 1–34 (2025)

    2025

  4. [12]

    Cambr idge Series in Sta- tistical and Probabilistic Mathematics

    Durrett, R.: Probability: Theory and Examples, 5th edn. Cambr idge Series in Sta- tistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 34 England (2019)

    2019

  5. [13]

    Technical Report 19900001324, NASA Lang ley Research Center (1989)

    Carter, R.G.: Numerical optimization in Hilbert space using inexact function and gradient evaluations. Technical Report 19900001324, NASA Lang ley Research Center (1989)

    1989

  6. [14]

    SIAM Journal on Scientific Comput ing 36(6), 3011–3029 (2014) https://doi.org/10.1137/140955665

    Kouri, D.P., Heinkenschloss, M., Ridzal, D., Bloemen Waanders, B.G.: Inexact objective function evaluations in a trust-region algorithm for pde- constrained optimization under uncertainty. SIAM Journal on Scientific Comput ing 36(6), 3011–3029 (2014) https://doi.org/10.1137/140955665

    2014 doi

  7. [15]

    UCI Machine Learning Repository (2014)

    Whiteson, D.: HIGGS. UCI Machine Learning Repository (2014). https://doi. org/10.24432/C5V312

    2014 doi

  8. [16]

    Springer Series in Statistics

    Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistica l Learning: Data Mining, Inference, and Prediction, 2nd edn. Springer Series in Statistics. Springer, New York, NY (2009)

    2009

  9. [17]

    https://arxiv.org/abs/1412.6980

    Kingma, D.P., Ba, J.: Adam: A Method for Stochastic Optimization ( 2017). https://arxiv.org/abs/1412.6980

    2017 arXiv

  10. [18]

    In: 29th ACM Internationa l Conference on Architectural Support for Programming Languages and Opera ting Systems, Volume 2 (ASPLOS ’24)

    Ansel, J., Yang, E., He, H., Gimelshein, N., Jain, A., Voznesensky, M ., Bao, B., Bell, P., Berard, D., Burovski, E., Chauhan, G., Chourdia, A., Constab le, W., Desmaison, A., DeVito, Z., Ellison, E., Feng, W., Gong, J., Gschwind, M., H irsh, B., Huang, S., Kalambarkar, K., Ki...

    2024

  11. [19]

    http://github.com/ jax-ml/jax

    Bradbury, J., Frostig, R., Hawkins, P., Johnson, M.J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., Zhang, Q.: JAX: Composable Transformations of Python+NumPy programs. http://github.com/ jax-ml/jax

  12. [20]

    Technical report, Rice University (2008)

    Heinkenschloss, M.: Numerical solution of implicitly constrained op timization problems. Technical report, Rice University (2008)

    2008

  13. [21]

    International Journal for Numerica l Methods in Engineering 86(6), 765–781 (2011) https://doi.org/10.1002/nme.3072

    Lazarov, B.S., Sigmund, O.: Filters in topology optimization based o n helmholtz- type differential equations. International Journal for Numerica l Methods in Engineering 86(6), 765–781 (2011) https://doi.org/10.1002/nme.3072

    2011 doi

  14. [22]

    Structural an d Mul- tidisciplinary Optimization 43(1), 1–16 (2011) https://doi.org/10.1007/s00158- 010-0594-7

    Andreassen, E., Clausen, A., Schevenels, M., Lazarov, B.S., Sigm und, O.: Efficient 35 topology optimization in MATLAB using 88 lines of code. Structural an d Mul- tidisciplinary Optimization 43(1), 1–16 (2011) https://doi.org/10.1007/s00158- 010-0594-7

    2011 doi

  15. [23]

    Computer M ethods in Applied Mechanics and Engineering 343, 186–206 (2019) https://doi.org/10

    Baiges, J., Mart ´ ınez-Frutos, J., Herrero-P´ erez, D., Otero, F., Ferrer, A.: Large- scale stochastic topology optimization using adaptive mesh refineme nt and coarsening through a two-level parallelization scheme. Computer M ethods in Applied Mechanics and Engineering 343, 1...

    2019

  16. [24]

    Society for Industrial and App lied Mathe- matics, Philadelphia, PA (2021)

    Shapiro, A., Dentcheva, D., Ruszczynski, A.: Lectures on Stoc hastic Program- ming: Modeling and Theory, 3rd edn. Society for Industrial and App lied Mathe- matics, Philadelphia, PA (2021). https://doi.org/10.1137/1.9781611976595

    2021 doi

  17. [25]

    The Annals of Mathematical Statistics 22(3), 400–407 (1951) https://doi.org/10.1214/aoms/ 1177729586

    Robbins, H., Monro, S.: A Stochastic Approximation Method. The Annals of Mathematical Statistics 22(3), 400–407 (1951) https://doi.org/10.1214/aoms/ 1177729586

    1951 doi

  18. [26]

    PhD thesis, UCLouvain (2004) 36

    Bastin, F.: Trust-region algorithms for nonlinear stochastic pr ogramming and mixed logit models. PhD thesis, UCLouvain (2004) 36

    2004

Pith tools

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