Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Online Covariance Estimation in Nonsmooth Stochastic Approximation

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

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

Pith's one-line read This paper proves that the online batch-means covariance estimator, applied to iterates of a nonsmooth stochastic approximation scheme, converges to the limiting covariance at the same $O(\sqrt{d}\,n^{-1/8+\varepsilon})$ rate that was…

desk verdict Solid local theory for nonsmooth batch-means covariance estimation, but the advertised global nonconvex rate overreaches: Assumption 4.1(1) is effectively global star-strong monotonicity, and the paper's own Example 4 violates it. read the letter →

arxiv 2502.05305 v2 pith:BOI7WNYE submitted 2025-02-07 stat.ML cs.LGmath.OC

Liwei Jiang , Abhishek Roy , Krishna Balasubramanian , Damek Davis , Dmitriy Drusvyatskiy , Sen Na This is my paper · ORCID
classification stat.MLcs.LGmath.OC MSC 62L2090C3390C15
keywords covarianceestimationstochasticapproximationnonsmoothvariationalinequalitiesbatch-meansestimatoractivemanifoldsasymptoticnormalityoptimizationstatisticalinference
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 treats a standing gap: after a nonsmooth stochastic approximation (SA) method produces asymptotically normal averaged iterates, no online procedure was known to estimate the limiting covariance matrix. The paper claims that the online batch-means estimator introduced for smooth SGD, which groups iterates into growing blocks and forms a sample covariance of block sums, is consistent here as well. Under local smooth-structure assumptions near the solution, plus a global aiming condition and light-tailed noise, it proves spectral-norm error $O(\sqrt{d}\,n^{-1/8+\varepsilon})$ in expectation. A sympathetic reader would care because this rate matches the smooth strongly convex benchmark, and consistency makes confidence intervals and hypothesis tests available for nonsmooth variational inclusions such as games and constrained optimization.

What carries the argument

The load-bearing object is the shadow sequence $y_k = P_M(x_k)$, the projection of the SA iterates onto the active manifold $M$ along which the set-valued part of $F$ is locally smooth. The paper shows $y_k$ obeys an inexact Riemannian SA recursion $y_{k+1}=y_k-\eta_{k+1}F_M(y_k)-\eta_{k+1}P_{TM(y_k)}(\nu_{k+1})+\eta_{k+1}E_k$, with error $E_k$ controlled by the distance to the manifold. Around this recursion the argument splits the batch-means estimator into a smooth-driving term and a shadow-error term, bounds each with martingale and drift lemmas, and uses the stopping time $\tau_{k_s,\delta}$ to confine the trajectory to the local region where the manifold description is valid.

What would settle it

Run the estimator on the paper's Example 4, $f(x,y)=|x-y^2|+x^2+\tfrac12 y^2$, with stochastic subgradient noise and parameters $\alpha=\tfrac12+4\varepsilon$, $\beta=2/(1-\alpha)$, from initial points far from the origin, and compare the empirical operator-norm error at horizons $n=10^4,10^5,10^6$ with $\sqrt{d}\,n^{-1/8+\varepsilon}$; since this objective satisfies the local Assumptions 3.1–3.3 but violates the global Assumption 4.1(1), a clear failure to track the promised decay would show that the global rate does not extend to the advertised nonconvex regime.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that nonsmooth geometry does not change the covariance estimation rate: the batch-means estimator (1.4) built from iterates of the generic SA scheme (3.3) converges in expectation to the asymptotic covariance matrix $\Sigma$ of the averaged iterates, with $E[\|\hat\Sigma_n-\Sigma\|_{\mathrm{op}}] = O(\sqrt{d}\,n^{-1/8+\varepsilon})$ for any $\varepsilon>0$ after choosing stepsize exponent $\alpha=\tfrac12+4\varepsilon$ and block growth exponent $\beta=2/(1-\alpha)$. The proof establishes the same rate first for a shadow sequence obtained by projecting iterates onto a smooth active manifold $M$ containing the solution; the projection error decays fast enough that it does not change the rate. A stopping time guards the local argument, and a high-probability bound shows the iterates stay in the neighborhood long enough to drop the stopping time and obtain the global guarantee.

Load-bearing premise

The load-bearing premise is Assumption 4.1(1), a global 'aiming' condition that the noisy update direction point toward the solution with strength proportional to squared distance everywhere in space—a condition the paper's advertised nonconvex example does not satisfy, so if it fails only the local conditional rate is available.

Editorial extensions

If this is right

  • Practitioners can construct asymptotically valid confidence intervals and hypothesis tests for nonsmooth variational inclusions using only first-order online updates.
  • The estimator remains fully online: it needs no prior knowledge of the total sample size and costs $O(d^2)$ memory and computation per update.
  • The $n^{-1/8+\varepsilon}$ rate matches the smooth strongly convex benchmark, so nonsmooth geometry does not degrade the covariance estimation rate.
  • The framework covers projected gradient, projected forward, and forward-backward stochastic methods, including entropy-regularized games and constrained nonlinear programs.
  • The high-probability stopping-time control converts the local conditional bound into a global convergence guarantee when the global aiming condition holds.

Reading between the lines

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

  • If the paper is right, the shadow-sequence technique should transfer to Markovian nonsmooth SA, since the smooth Markovian case already matches the same $n^{-1/8}$ rate.
  • The advertised nonconvex example satisfies the local manifold assumptions but not the global aiming condition, so the global rate likely does not cover every example the paper's introduction gestures toward; only the local conditional rate survives in those cases.
  • A testable extension is to replace the fixed batch-growth schedule with adaptive or overlapping blocks, which may improve the logarithmic factors or approach the conjectured $n^{-1/4}$ rate.
  • The same shadow-sequence template could be used to build confidence regions for other output statistics of nonsmooth SA, not just the averaged iterates.
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 / 4 minor

Summary. The paper studies an online batch-means covariance matrix estimator for averaged stochastic approximation iterates in nonsmooth variational inclusions. The estimator is defined in (1.4) from blocks of iterates generated by the generic SA recursion (3.3). The main local result, Theorem 3.1, bounds the mean squared estimation error up to a stopping time at which the iterates leave a neighborhood of the solution. Section 4 introduces Assumptions 4.1 and 4.2 and uses a martingale concentration argument, Proposition 4.1, to control the escape probability, leading to the global rate claim in Theorem 4.1: E[||Σ̂_n − Σ||_op] is O(sqrt(d) n^{-1/8+ε}) up to logarithms. The paper advertises this rate for nonsmooth, potentially non-monotone (nonconvex) problems, matching the best-known rate in smooth strongly convex settings.

Significance. If the local conditional result were the final claim, this would be a useful extension of the smooth strongly convex batch-means analysis of Zhu et al. (2023) to nonsmooth SA: the shadow-sequence construction, the tangent/normal error decomposition, and the quantitative local error bounds are substantive and carefully developed. The paper also provides concrete examples (ℓ1-regularization, nonlinear programming, entropy-regularized games, and a nonconvex example) and verifies several structural assumptions. However, the advertised global nonconvex rate is not established: the only mechanism that removes the stopping time is Proposition 4.1, and its Assumption 4.1(1) is a global strong-monotonicity condition that the paper's own nonconvex Example 4 violates. The global result in Theorem 4.1 is therefore a strongly monotone result, not a nonconvex one. The local analysis remains defensible and is the main genuine contribution.

major comments (3)
  1. [§4, Assumption 4.1(1); Theorem 4.1; Example 4 (Appendix A)] The global rate claim is unsupported for the paper's nonconvex showcase. Assumption 4.1(1) is a global star-strong-monotonicity condition: in the noiseless limit η→0 it requires ⟨F(x), x−x⋆⟩ ≥ (γ/2)||x−x⋆||² for all x. For f(x,y)=|x−y²|+x²+y²/2 from Example 4, take x⋆=0 and x_ε=(ε, sqrt(ε−ε²)) with ε∈(0,1). For small ε the point lies in the differentiable region x>y², where ∇f(x_ε)=(1+2ε, −sqrt(ε−ε²)), so ⟨∇f(x_ε), x_ε⟩=3ε² while ||x_ε||²=ε. The ratio tends to 0 as ε→0, so no fixed γ>0 can satisfy Assumption 4.1(1). Consequently Proposition 4.1 cannot be applied to Example 4, the stopping time τ_{k_s,δ} in Theorem 3.1 cannot be suppressed, and the advertised unconditional n^{-1/8} rate for 'potentially non-monotone (nonconvex)' problems is not established. What remains for such problems is the conditional local bound of Theorem 3.1.
  2. [§5 and Appendix E, Proposition E.2] The paper's own verification of the global assumptions confirms that Theorem 4.1 is a strongly monotone result. Proposition E.2 verifies Assumption 4.1 only under strong monotonicity of A and convexity of g and f, and Proposition E.1 verifies Assumption 3.6 only under monotonicity/convexity. For the nonconvex Example 4, neither Assumption 4.1 nor Assumption 3.6 is verified. Section 3's claim that Assumptions 3.1–3.3 'do not imply global convexity' is true but irrelevant to the global theorem, since Theorem 4.1 requires the additional global condition Assumption 4.1. The abstract and conclusion therefore overstate the scope of the global convergence rate.
  3. [Appendix D, proof of Theorem 4.1] The displayed conversion of exponents in Theorem 4.1 is algebraically inconsistent. The proof transitions from M^{((α−1)β+1)/2} (or, as printed in the proof, M^{((α−1)β+2)/2}) to n^{−((α−1)β+1)/(2β)}; with β>1/(1−α), the latter exponent is positive, so it cannot be the intended decaying rate. The subsequent line 'Taking β=2/(1−α)' and Remark 1 indicate the intended rate n^{−((α−1)β+1)/(2β)} with the negative sign placed on the whole exponent, i.e., n^{((α−1)β+1)/(2β)}. This is likely a typographical error, but the theorem statement as printed is misleading and should be corrected.
minor comments (4)
  1. [Theorem 3.1] The exponents in the first two terms of the displayed bound are garbled as printed: they should read d n^{((α−1)β+1)/β} and sqrt(d) n^{((α−1)β+1)/(2β)} to match Remark 1 and the proof of Lemma B.1.
  2. [Proposition 4.1] In the final probability bound, the second fraction contains a redundant factor of δ in the numerator and denominator; it simplifies to 8η sqrt(k) exp(−γδ sqrt(k)/(4ησ²))/γ. This is cosmetic but should be cleaned up.
  3. [Notation throughout] The symbol G_η is used for the algorithm map in (3.3) and again in Assumptions 3.2, 3.3, and 4.1 with arguments (x,ν) or (x,ν) plus η; a notational remark distinguishing the map G from the noise ν would improve readability.
  4. [Appendix B] Several displayed equations in Appendix B have typographical issues, for example the definition of λ_i^j and the cross terms in the decomposition of Σ̃_n; a careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the batch-means rate is derived from explicit assumptions and prior lemmas that do not contain the target result.

full rationale

The derivation is self-contained in the relevant sense. The central claim, Theorem 3.1 and its global counterpart Theorem 4.1, is a new technical result about the batch-means estimator (1.4). The proof reduces the nonsmooth SA iterates to a shadow sequence y_k = P_M(x_k), then analyzes that sequence using the recursion y_{k+1} = y_k - eta_{k+1}F_M(y_k) - eta_{k+1}P_{TM(y_k)}(nu_{k+1}) + eta_{k+1}E_k, which is imported verbatim from the authors' prior work [8, Proposition 6.3], together with bounds on E_k from [27]. These are cited theorems with stated assumptions (partial smoothness, proximal aiming, bounded noise moments) that do not themselves assert convergence of the batch-means estimator; they are reusable lemmas, not the target conclusion. No parameter is fitted to the data and then renamed as a prediction: the batch-size sequence a_m = floor(C m^beta) is chosen analytically, and the stopping-time argument in Proposition 4.1 uses an explicitly stated global aiming condition (Assumption 4.1) plus a martingale concentration lemma. The target quantity Sigma never appears in the assumptions. A legitimate concern is whether Assumption 4.1 is compatible with the advertised nonconvex examples, since the deterministic eta->0 limit of Assumption 4.1(1) is global star-strong monotonicity and the paper's Example 4 apparently violates it; however, that is a correctness/scope gap in the global claim, not a circular reduction. Under the stated assumptions, the proof is a genuine derivation.

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

The central claim rests on a cluster of local manifold assumptions (3.1, 3.3) and a global strong-monotonicity assumption (4.1). The local assumptions are inherited from the authors' previous work [8, 27]; the global assumption is what enables the clean n^{-1/8} rate but is not satisfied by the paper's own nonconvex example, creating an overclaim in the abstract.

free parameters (2)
  • batch size exponent beta = beta = 2/(1-alpha) in the optimized rate
    The batch size sequence a_m = floor(C m^beta) is chosen by hand; beta must exceed 1/(1-alpha) and is set to balance bias-variance terms in the proof (Remark 1). Not fitted to data.
  • stepsize exponent alpha = alpha in (1/2,1), e.g. 1/2 + 4eps
    The stepsize eta_k = eta k^{-alpha} is an algorithm hyperparameter; the rate depends on alpha and is optimized at alpha close to 1/2.
assumptions (5)
  • domain assumption Assumption 3.1: existence of a smooth manifold M containing x* with strong monotonicity of the restricted map F_M on M
    This is the 'hidden smoothness' condition. It is assumed, not derived, and is essential for the shadow sequence to behave like a smooth SA recursion.
  • ad hoc to paper Assumption 3.3: tangent comparison and proximal aiming inequalities for the generalized gradient map G
    These bespoke inequalities were developed in the authors' prior work [8] to handle nonsmooth SA. They are not standard off-the-shelf assumptions and are hard to verify in general, though the paper provides several examples.
  • domain assumption Assumption 3.5: noise decomposes as nu_(1) + nu_(2)(x_k) with constant covariance S on the tangent space
    The limit covariance is expressed in terms of S; constancy of S is needed for the batch-means estimator to target a well-defined matrix.
  • domain assumption Assumption 4.1: global aiming inequality <G_eta(x,nu)-nu, x-x*> >= gamma||x-x*||^2/2 - C eta(...)
    This is the load-bearing premise for the global rate; it effectively implies global strong monotonicity and is not satisfied by the paper's own nonconvex example.
  • domain assumption Assumption 4.2: sub-Gaussian noise norm
    Needed for the high-probability concentration bound that keeps iterates inside the local ball and suppresses the stopping time.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Covariance Estimation in Nonsmooth Stochastic Approximation." pith.science (2026). https://pith.science/paper/BOI7WNYE

@misc{pith2026250205305,
  author       = {Pith},
  title        = {Pith review of: Online Covariance Estimation in Nonsmooth Stochastic Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BOI7WNYE}},
  note         = {Machine review of arXiv:2502.05305}
}
abstract

We consider applying stochastic approximation (SA) methods to solve nonsmooth variational inclusion problems. Existing studies have shown that the averaged iterates of SA methods exhibit asymptotic normality, with an optimal limiting covariance matrix in the local minimax sense of H\'ajek and Le Cam. However, no methods have been proposed to estimate this covariance matrix in a nonsmooth and potentially non-monotone (nonconvex) setting. In this paper, we study an online batch-means covariance matrix estimator introduced in Zhu et al.(2023). The estimator groups the SA iterates appropriately and computes the sample covariance among batches as an estimate of the limiting covariance. Its construction does not require prior knowledge of the total sample size, and updates can be performed recursively as new data arrives. We establish that, as long as the batch size sequence is properly specified (depending on the stepsize sequence), the estimator achieves a convergence rate of order $O(\sqrt{d}n^{-1/8+\varepsilon})$ for any $\varepsilon>0$, where $d$ and $n$ denote the problem dimensionality and the number of iterations (or samples) used. Although the problem is nonsmooth and potentially non-monotone (nonconvex), our convergence rate matches the best-known rate for covariance estimation methods using only first-order information in smooth and strongly-convex settings. The consistency of this covariance estimator enables asymptotically valid statistical inference, including constructing confidence intervals and performing hypothesis testing.

Figures

Figures reproduced from arXiv: 2502.05305 by the authors.

Figure 1
Figure 1. f(x1, x2) = |x1| + x 2 2 with x2-axis as an active manifold. Definition 1 (Active manifold). Consider a function f : R d → R∪ {+∞} and fix a set M ⊂ domf that contains a critical point x ⋆ with 0 ∈ ∂f(x ⋆ ). Then M is called an active C p -manifold around x ⋆ if there exists a constant χ > 0 satisfying the following conditions. • (smoothness) Near x ⋆ , the set M is a C p manifold and the restriction of f to M is C … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling

    stat.ML 2025-05 conditional novelty 6.0 of 10

    A random scaling statistic based on averaged AI-SSQP iterates is asymptotically pivotal for constrained stochastic optimization, enabling matrix-free online confidence intervals.

Reference graph

Works this paper leans on

41 extracted references · 35 canonical work pages · cited by 1 Pith paper

  1. [1]

    Online covariance matrix estimation in stochastic gradient descent

    Wanrong Zhu, Xi Chen, and Wei Biao Wu. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 118(541):393–404, 2023

    work page 2023

  2. [2]

    Acceleration of stochastic approximation by averaging

    Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838–855, 1992

    1992

  3. [3]

    Asymptotic and finite-sample properties of estimators based on stochastic gradients

    Panos Toulis and Edoardo Maria Airoldi. Asymptotic and finite-sample properties of estimators based on stochastic gradients. The Annals of Statistics, 2017

    work page 2017

  4. [4]

    Asymptotic optimality in stochastic optimization

    John C Duchi and Feng Ruan. Asymptotic optimality in stochastic optimization. The Annals of Statistics, 49(1):21–48, 2021

    work page 2021

  5. [5]

    Normal ap- proximation for stochastic gradient descent via non-asymptotic rates of martingale clt

    Andreas Anastasiou, Krishnakumar Balasubramanian, and Murat A Erdogdu. Normal ap- proximation for stochastic gradient descent via non-asymptotic rates of martingale clt. In Conference on Learning Theory, pages 115–137. PMLR, 2019

    work page 2019

  6. [6]

    Berry–esseen bounds for multivariate nonlinear statistics with applications to m-estimators and stochastic gradient descent algorithms

    Qi-Man Shao and Zhuo-Song Zhang. Berry–esseen bounds for multivariate nonlinear statistics with applications to m-estimators and stochastic gradient descent algorithms. Bernoulli, 28(3):1548–1576, 2022

    work page 2022

  7. [7]

    Gaussian approximation and multiplier bootstrap for polyak-ruppert averaged linear stochastic approximation with applications to td learning

    Sergey Samsonov, Eric Moulines, Qi-Man Shao, Zhuo-Song Zhang, and Alexey Naumov. Gaussian approximation and multiplier bootstrap for polyak-ruppert averaged linear stochastic approximation with applications to td learning. arXiv preprint arXiv:2405.16644, 2024

    arXiv 2024

  8. [8]

    Asymptotic normality and optimality in nonsmooth stochastic approximation

    Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang. Asymptotic normality and optimality in nonsmooth stochastic approximation. The Annals of Statistics, 52(4):1485–1508, 2024

    work page 2024

Show all 41 references
  1. [9]

    Resampling methods for dependent data

    Soumendra Nath Lahiri. Resampling methods for dependent data . Springer Science & Business Media, 2003

    2003

  2. [10]

    Batch means and spectral variance estimators in markov chain monte carlo

    James M Flegal and Galin L Jones. Batch means and spectral variance estimators in markov chain monte carlo. The Annals of Statistics, 38(2):1034–1070, 2010

    2010

  3. [11]

    Online covariance estimation for stochas- tic gradient descent under markovian sampling

    Abhishek Roy and Krishnakumar Balasubramanian. Online covariance estimation for stochas- tic gradient descent under markovian sampling. arXiv preprint arXiv:2308.01481, 2023

    2023 arXiv

  4. [12]

    Statistical inference for model parameters in stochastic gradient descent

    Xi Chen, Jason D Lee, Xin T Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic gradient descent. Annals of Statistics, 48(1):251–273, 2020

    2020

  5. [13]

    Smooth manifolds

    John M Lee. Smooth manifolds. In Introduction to Smooth Manifolds, pages 1–31. Springer, 2013

    2013

  6. [14]

    An introduction to optimization on smooth manifolds

    Nicolas Boumal. An introduction to optimization on smooth manifolds. Available online, Aug, 2020

    2020

  7. [15]

    Springer Science & Business Media, 2009

    R Tyrrell Rockafellar and Roger J-B Wets.Variational analysis, volume 317. Springer Science & Business Media, 2009. 14

    2009

  8. [16]

    A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth

    Damek Davis and Liwei Jiang. A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth. arXiv preprint arXiv:2205.00064, 2022

    2022 arXiv

  9. [17]

    Numerical optimization

    Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 2006

    2006

  10. [18]

    An efficient stochastic newton algorithm for parameter estimation in logistic regressions

    Bernard Bercu, Antoine Godichon, and Bruno Portier. An efficient stochastic newton algorithm for parameter estimation in logistic regressions. SIAM Journal on Control and Optimization, 58(1):348–367, 2020

    2020

  11. [19]

    Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming

    Sen Na and Michael W Mahoney. Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming. arXiv preprint arXiv:2205.13687, 2022

    2022 arXiv

  12. [20]

    A short note on concentration inequalities for random vectors with subgaussian norm

    Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.03736, 2019

    1902 arXiv

  13. [21]

    Identifiable surfaces in constrained optimization

    Stephen J Wright. Identifiable surfaces in constrained optimization. SIAM Journal on Control and Optimization, 31(4):1063–1079, 1993

    1993

  14. [22]

    Active sets, nonsmoothness, and sensitivity

    Adrian S Lewis. Active sets, nonsmoothness, and sensitivity. SIAM Journal on Optimization, 13(3):702–725, 2002

    2002

  15. [23]

    The U-lagrangian of a convex function

    Claude Lemaréchal, François Oustry, and Claudia Sagastizábal. The U-lagrangian of a convex function. Transactions of the American mathematical Society, 352(2):711–729, 2000

    2000

  16. [24]

    A V U-algorithm for convex minimization

    Robert Mifflin and Claudia Sagastizábal. A V U-algorithm for convex minimization. Mathe- matical programming, 104(2):583–608, 2005

    2005

  17. [25]

    On a class of nonsmooth composite functions

    Alexander Shapiro. On a class of nonsmooth composite functions. Mathematics of Operations Research, 28(4):677–692, 2003

    2003

  18. [26]

    Optimality, identifiability, and sensitivity

    Dmitriy Drusvyatskiy and Adrian S Lewis. Optimality, identifiability, and sensitivity. Mathe- matical Programming, 147(1):467–498, 2014

    2014

  19. [27]

    Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization

    Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang. Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization. Foundations of Computational Mathematics, pages 1–83, 2025

    2025

  20. [28]

    Fast policy extragradient methods for competitive games with entropy regularization

    Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems , 34:27952–27964, 2021

    2021

  21. [29]

    On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging

    Chris Junchi Li, Yaodong Yu, Nicolas Loizou, Gauthier Gidel, Yi Ma, Nicolas Le Roux, and Michael Jordan. On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging. In International Conference on Artificial Intelligence and Statistics...

    2022

  22. [30]

    Learning in games via reinforcement and regularization

    Panayotis Mertikopoulos and William H Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 41(4):1297–1324, 2016. 15

    2016

  23. [31]

    Quantal response equilibria for normal form games

    Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6–38, 1995

    1995

  24. [32]

    Tight analyses for non-smooth stochastic gradient descent

    Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579–1613. PMLR, 2019

    2019

  25. [33]

    Stochastic optimization under distributional drift

    Joshua Cutler, Dmitriy Drusvyatskiy, and Zaid Harchaoui. Stochastic optimization under distributional drift. Journal of machine learning research, 24(147):1–56, 2023. 16 A Concrete Examples In this section, we expand on the discussion in Section 3 and provide some concrete exa...

    2023

  26. [34]

    Using Lemma F.4 and Lemma G.6, we have, ∥Si ti−1∥2 2∥E[∆ti−1∆⊤ ti−11 τks,δ>ti−1]∥2 ≤ ∥Si ti−1∥2 2E[∥∆ti−1∥2 21 τks,δ>ti−1] ≲ kα s tα i

    ti − 1 ≥ ks. Using Lemma F.4 and Lemma G.6, we have, ∥Si ti−1∥2 2∥E[∆ti−1∆⊤ ti−11 τks,δ>ti−1]∥2 ≤ ∥Si ti−1∥2 2E[∥∆ti−1∥2 21 τks,δ>ti−1] ≲ kα s tα i . (B.12)

  27. [35]

    By the definition ofyi, we always have∥∆ti−1∥ ≤4δ

    ti−1 < ks. By the definition ofyi, we always have∥∆ti−1∥ ≤4δ. Applying Lemma G.6, we have ∥Si ti−1∥2 2∥E[∆ti−1∆⊤ ti−11 τks,δ>ti−1]∥2 ≲ t2α i ≲ k2α s . Next, we consider the second term on the RHS of (B.11). By Assumption 3.5 and 3.6, we have ∥U ⊤E[(ν(1) k+1 + ν(2) k+1(xk))(ν(1...

  28. [36]

    One applies the stochastic forward algorithm to the case f = 0 and g is Lipschitz and convex

  29. [37]

    One applies the stochastic projected forward algorithm to the case f is the indicator function of a closed convex set X and g is Lipschitz and convex

  30. [38]

    Then Assumption 3.6 holds

    One applies the stochastic forward-backward algorithm to the casef is Lipschitz in its domain and g = 0. Then Assumption 3.6 holds. Proof. Note that the first scenario is a special case of the second one, we only prove it for the second and third cases. 33 Stochastic projected...

  31. [39]

    One applies the stochastic forward algorithm to the case f = 0 and g is Lipschitz and convex. 35

  32. [40]

    One applies the stochastic projected forward algorithm to the case f is the indicator function of a closed set X and g is Lipschitz and convex

  33. [41]

    yk+1 − yk ηk+1 + FM(yk) + PTM(yk)(νk) 2 2 # ≲

    One applies the stochastic forward-backward algorithm to the casef is Lipschitz in its domain and g = 0. Then Assumption 4.1 holds. Proof. Since the stochastic forward algorithm is a special case of the stochastic projected forward algorithm, it suffices to prove the result fo...

Pith tools

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