Pith. sign in

REVIEW 3 major objections 5 minor 81 references

Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements

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

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

Pith's one-line read Two simple modifications to stochastic extragradient give it provable convergence in convex-concave minimax problems and a faster strongly-monotone rate.

desk verdict Solid theory result with a real advance, but the headline rates rest on a Lipschitz-Hessian assumption that confines the practical claims to quadratics. read the letter →

arxiv 2501.00511 v1 pith:4PPQPDKA submitted 2024-12-31 cs.LG math.OC

Jiseok Chae , Chulhee Yun , Donghwan Kim This is my paper · ORCID
classification cs.LGmath.OC MSC 90C4765K1049J4068W20
keywords stochasticextragradientflip-flopshufflinganchoringconvex-concaveminimaxrandomreshufflingstronglymonotonevariationalinequalitiessecond-ordermatchingfinite-sumoptimization
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 tries to establish that a minimal modification of stochastic extragradient (SEG), combining flip-flop shuffling with an anchoring step, makes the method converge in unconstrained convex-concave finite-sum minimax problems with an explicit rate, while also provably speeding up convergence in the strongly convex-strongly concave case. It shows that shuffling alone, either random reshuffling or the recent flip-flop scheme, is not enough: those SEG variants can diverge in the convex-concave setting. The paper provides a design principle, second-order matching to the deterministic extragradient method, explains why previous stochastic methods fail it, and proves that SEG-FFA fulfills it.

What carries the argument

The central device is second-order matching: within one epoch, SEG-FFA's update is shown to match the deterministic extragradient update EG up to error $O(\eta^3)$, whereas SEG-RR only matches to first order (error $O(\eta^2)$) and flip-flop-only SEG would require parameters that make EG+ diverge. Flip-flop sampling (two passes through the components in reversed order) supplies all the cross terms $DF_j(z_0)F_i z_0$ needed in the Taylor expansion, and the anchoring step of averaging $z^N$ with $z^0$ divides the coefficients appropriately so that the epoch update becomes EG with the correct stepsize ratio $\eta_1=\eta_2$.

What would settle it

Construct a finite-sum monotone minimax problem whose components are L-smooth but have non-Lipschitz Hessians (for example, a piecewise-quadratic saddle function that is still convex-concave overall) and measure the within-epoch error $\|z^{k+1}_0 - (z^k_0 - \eta_k n F(z^k_0 - \eta_k n F z^k_0))\|$; if it scales as $\eta^2$ rather than $\eta^3$, then Theorem 5.4's $O((\log K)^2/K^{1/3})$ rate cannot hold for that class, directly contradicting the paper's claim that M-smoothness suffices.

Watch

Extended reading notes

Core claim

The paper claims that SEG-FFA, stochastic extragradient with flip-flop sampling and anchoring, achieves in the (star-)monotone setting the bound $\min_{k=0,\dots,K} \mathbb{E}\|F z^k_0\|^2 = O((\log K)^2 / K^{1/3})$ when stepsizes are chosen as $\beta_k = O(1/k^{1/3}\log k)$ and $\alpha_k = \beta_k/2$, and in the $\mu$-strongly monotone setting achieves $\mathbb{E}\|z^K_0 - z_*\|^2 \le \exp(-c \mu \omega nK)\|z^0_0 - z_*\|^2 + O((\log(n^{1/4}K))^4/(nK^4))$ for a constant $\omega$ independent of the stepsize. It also proves that with the same problem settings, SEG-US, SEG-RR, and SEG-FF all diverge on a quadratic monotone counterexample, and that SGDA-RR and SEG-RR suffer $\Omega(1/(nK^3))$ lower bounds, so SEG-FFA provides a provable speedup.

Load-bearing premise

The proof that one epoch of SEG-FFA tracks deterministic extragradient to third order requires every component Fi to have a Lipschitz-Hessian (M-smoothness, Assumption 3.3(ii)); if that fails, the error drops to second order and both the monotone convergence rate and the strongly-monotone speedup are lost.

Editorial extensions

If this is right

  • SEG-FFA converges in unconstrained finite-sum convex-concave minimax problems with an explicit $\widetilde{O}(1/K^{1/3})$ rate on squared-gradient norm, removing the need for bounded domains, increasing batch sizes, or uniformly bounded gradient variance.
  • In strongly monotone problems, SEG-FFA attains $\widetilde{O}(1/(nK^4))$ last-iterate error, a polynomial order faster than the $\Omega(1/(nK^3))$ lower bounds shown for SGDA-RR and SEG-RR.
  • The paper's counterexample (Theorem 4.1) shows that SEG-US, SEG-RR, and SEG-FF can diverge in expectation for any positive stepsizes on a simple quadratic monotone problem, so anchoring, not just shuffling, is essential for convergence.
  • The unified analysis in Theorem F.5 implies that any other stochastic method achieving the same second-order matching to EG would automatically enjoy the same convergence guarantees, not just SEG-FFA itself.

Reading between the lines

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

  • The same second-order-matching design principle could likely be applied to other stochastic operator-splitting methods (e.g., optimistic gradient or proximal point variants) to fix divergence in monotone settings, though the paper does not explore this.
  • The $O(1/K^{1/3})$ rate in the monotone setting may not be tight; the analysis suggests that more aggressive stepsize decay or variance reduction could push the rate toward $O(1/K^{1/2})$, but this is an editor's guess, not a claim of the paper.
  • The M-smoothness assumption (Lipschitz-Hessian of each component) is a genuine restriction; if it fails, the epoch-error drops to $O(\eta^2)$ and the provable speedup disappears, so testing SEG-FFA on piecewise-smooth or nonsmooth-Hessian problems is a natural stress test.
  • The anchoring step is a fixed-point averaging reminiscent of Krasnoselskii-Mann iteration; combining it with Halpern-type anchoring on the initial point, which the paper explicitly distinguishes, could yield further acceleration, but the paper leaves that open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. This paper studies same-sample stochastic extragradient (SEG) variants with shuffling schemes for unconstrained finite-sum minimax problems. It first proves, via a two-component bilinear counterexample, that SEG with uniform sampling, random reshuffling, and flip-flop shuffling can all diverge in monotone problems. The authors then identify a second-order Taylor-matching condition that separates convergent from divergent SEG variants, and propose SEG-FFA, which combines flip-flop shuffling with an anchoring step. Under (star-)monotonicity, smoothness, and a component-variance assumption, SEG-FFA is shown to attain min_{k<=K} E||F z^k_0||^2 = O((log K)^2/K^{1/3}); under strong monotonicity it attains E||z^K_0 - z*||^2 <= exp(-c mu omega n K)||z^0_0 - z*||^2 + O((log(n^{1/4}K))^4/(nK^4)). The paper also proves Omega(1/(nK^3)) lower bounds for SGDA-RR and SEG-RR on quadratic strongly monotone instances, establishing a separation in the K-exponent. The proof is supported by detailed appendices, and experiments on random quadratics match the theory.

Significance. If the results are correct, SEG-FFA is a meaningful advance: it provides an explicit convergence rate for a same-sample shuffling-based SEG in unconstrained convex-concave finite-sum problems, and it identifies a design principle, second-order matching with anchoring, that could be reused. The paper's strengths include complete proofs with explicit constants, clean divergence counterexamples, and lower-bound constructions tailored to the assumptions. The upper and lower bounds are internally consistent, and the experiments corroborate the qualitative predictions. The main reservation is scope: the advertised improvements are conditional on the Lipschitz-Hessian assumption on each component saddle gradient (Assumption 3.3(ii)), and the numerical validation is limited to quadratics, where that assumption holds trivially. The contribution is nonetheless solid within its stated assumptions.

major comments (3)
  1. [Section 3, Proposition 5.3, Theorem E.1] The advertised rates in Theorems 5.4 and 5.5 are load-bearing on Assumption 3.3(ii), the M-smoothness of each Fi. In the proof of Proposition 5.3 and Theorem E.1, the O(eta^3) within-epoch error for SEG-FFA depends on controlling the Taylor remainder in Eq. (62b) via Lemma C.6, which requires a Lipschitz bound on DF_j. Without Assumption 3.3(ii), that remainder is only o(eta) per term, so the error exponent a in Theorem E.1 drops to at most 2 and the monotone rate O((log K)^2/K^{1/3}) and the strongly monotone speedup O((log(n^{1/4}K))^4/(nK^4)) do not follow. The paper itself acknowledges this in Section 3, but the abstract and Section 1.1 present the rates without this qualification, and Section 6 validates only quadratic problems where M=0. Please state the M-smoothness requirement prominently in the abstract and contributions, add at least one non-quadratic experiment satisfying Assumption 3.3(ii) with M>0, or explicitly state that the empirical validation does not exercise the key assumption.
  2. [Appendix B.4] The paper's novelty claim of being the first same-sample SEG with an explicit monotone convergence rate rests on the assertion that the monotone SEG-RR result of Emmanouilidis et al. [18] is flawed. The critique, that Jensen's inequality is applied to weights 1/G^k that do not sum to 1, is plausible, but it is given in one paragraph without reproducing the exact equation from [18] and without showing that the surrounding argument cannot be repaired. Since Theorem 4.1 of the present paper directly contradicts the monotone claim of [18], the appendix should present a self-contained, step-by-step exposition of the flaw, including the exact equation in [18] and why the corrected inequality cannot restore the claimed convergence.
  3. [Theorem 5.6] Theorem 5.6 as stated in the main text omits the condition L/mu >= 2 that is required by the constructions in Theorem H.6 and by the Safran-Shamir lower bound cited in Appendix H.3.1. Without this condition, the case analysis in Appendix H.3.3, in particular the bound in Case 3 that uses L/mu >= 2, does not cover the full parameter range. Please either add this condition to the theorem statement or extend the argument to the regime 1 <= L/mu < 2.
minor comments (5)
  1. [Section 3, Assumption 3.3] It would be helpful to give an explicit example of a non-quadratic component satisfying Assumption 3.3(ii) with M>0, to show that the assumption is not vacuous outside the quadratic case.
  2. [Table 1 and Theorems 5.4-5.5] The O-tilde notation in Table 1 and the main theorems should clarify that the hidden constants depend on n, sigma, rho, and the problem data; a reader could otherwise read the rates as depending only on K.
  3. [Section 6] The experimental section reports only geometric means over five random instances without error bars or ranges; since the paper is primarily theoretical this is acceptable, but the captions and text should state explicitly that no statistical significance is claimed.
  4. [Theorem 5.5 and Appendix F.5] The statement of Theorem 5.5 says the constant omega is independent of eta, but the proof in Theorem F.5 defines omega as a minimum of constants depending on the problem data and on the initial gradient bound; this quantification should be stated precisely in the main theorem.
  5. [Throughout] There are occasional typographical and phrasing issues, for example 'the results of the geometric mean' in Section 6 and the incomplete sentence after Eq. (102) in Appendix F; a careful proofreading pass would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SEG-FFA's advertised rates are proven from explicit Taylor-expansion error bounds and known EG convergence, with no fitted parameters or load-bearing self-citations.

full rationale

The paper's derivation chain is self-contained. SEG-FFA is constructed by choosing flip-flop sampling plus an anchoring step so that, by the paper's own Proposition 5.3 and the detailed within-epoch analysis of Appendix E (Theorems E.9 and E.13), the epoch update matches a deterministic EG step up to an error of order O(eta^3) under Assumptions 3.2-3.4. The monotone convergence rate in Theorem 5.4 follows from Theorem G.4, which uses only the star-monotonicity inequality, the L-smoothness of F, the explicit error decomposition of equations (104)-(105), and the deterministic/expected error bounds (58) and (71); no step sets the claimed 'prediction' equal to an input or to the conclusion. The strongly monotone rate in Theorem 5.5 is a specialization of the unified Theorem F.5, whose proof algebraically unravels a recurrence from Proposition F.2 and Lemma F.4; the constants C1, D1, V1, C2, D2, V2 are explicit universal constants derived from the error analysis, not fit to data. The lower bounds for SEG-RR and SGDA-RR in Theorem 5.6 are proved by explicit quadratic counterexamples using the Safran-Shamir lower bound [49,50], not by invoking any uniqueness theorem. Self-citations in the paper (e.g., [1], [11], [13], [56]) appear in related-work context or as prior shuffling results, but the target convergence theorems do not rely on them as the load-bearing argument; in particular, the SEG-FFA upper bounds are proven directly. The acknowledged limitation involving the M-smoothness (Lipschitz Hessian) assumption is a scope and correctness-risk issue, not a circularity: dropping Assumption 3.3(ii) would weaken the error exponent in Theorem E.1, but that is a hypothesis-sensitivity concern rather than a reduction of the conclusion to the assumptions. Accordingly, the appropriate circularity score is 0.

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

The central claims rest on the stated monotonicity and smoothness assumptions; no parameters are fitted to data. SEG-FFA is a new algorithmic combination, not a new physical entity.

assumptions (5)
  • domain assumption The full saddle gradient F is (star-)monotone (Assumption 3.1 / G.1).
    Convergence of SEG-FFA in the monotone setting relies on (star-)monotonicity of F, not of the individual components; star-monotonicity is weaker and permits some nonconvex-nonconcave objectives.
  • domain assumption An optimal solution z* exists (Assumption 3.2).
    Excludes pathological monotone problems like f(x,y)=x-y where no finite saddle point exists; for strongly monotone problems it is automatic.
  • domain assumption Each fi is L-smooth and each Fi is M-smooth, i.e. the Hessian of fi is Lipschitz (Assumption 3.3).
    The M-smoothness is the key premise for the O(eta^3) within-epoch error; it is satisfied by quadratics but is restrictive for general smooth objectives.
  • domain assumption Component variance satisfies 1/n sum ||Fi z - F z||^2 <= (rho ||F z|| + sigma)^2 (Assumption 3.4).
    Allows variance to grow with gradient norm, more realistic than uniform bound, but still restrictive for unconstrained problems.
  • standard math Known convergence properties of deterministic EG and EG+ (e.g., nonexpansiveness lemma C.10).
    Used as reference for second-order matching and in the proof of the monotone upper bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements." pith.science (2026). https://pith.science/paper/4PPQPDKA

@misc{pith2026250100511,
  author       = {Pith},
  title        = {Pith review of: Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4PPQPDKA}},
  note         = {Machine review of arXiv:2501.00511}
}
read the original abstract

In minimax optimization, the extragradient (EG) method has been extensively studied because it outperforms the gradient descent-ascent method in convex-concave (C-C) problems. Yet, stochastic EG (SEG) has seen limited success in C-C problems, especially for unconstrained cases. Motivated by the recent progress of shuffling-based stochastic methods, we investigate the convergence of shuffling-based SEG in unconstrained finite-sum minimax problems, in search of convergent shuffling-based SEG. Our analysis reveals that both random reshuffling and the recently proposed flip-flop shuffling alone can suffer divergence in C-C problems. However, with an additional simple trick called anchoring, we develop the SEG with flip-flop anchoring (SEG-FFA) method which successfully converges in C-C problems. We also show upper and lower bounds in the strongly-convex-strongly-concave setting, demonstrating that SEG-FFA has a provably faster convergence rate compared to other shuffling-based methods.

Figures

Figures reproduced from arXiv: 2501.00511 by the authors.

Figure 1
Figure 1. Experimental results on the (left) monotone and (right) strongly monotone examples, [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Experimental results in the monotone example, comparing the performance of SEG-RRA [PITH_FULL_IMAGE:figures/full_fig_p071_2.png] view at source ↗
Figure 3
Figure 3. Experimental results in the monotone example, comparing [PITH_FULL_IMAGE:figures/full_fig_p072_3.png] view at source ↗
Figures from the paper (2 more)
Figure 2
Figure 2. Figure 2: Here we can clearly see that SEG-FFA outperforms both versions of DSEG. I.4 Strongly Monotone Case Again, with Various Stepsizes We also ran the experiment on strongly monotone problems described in Section 6, but with changing the stepsizes. We tested six different va…
Figure 4
Figure 4. Figure 4: Experimental results on the strongly monotone problems with different stepsizes. Notice [PITH_FULL_IMAGE:figures/full_fig_p073_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

81 extracted references · 75 canonical work pages

  1. [18]

    Stochastic extragradient with random reshuffling: Improved convergence for variational inequalities

    Konstantinos Emmanouilidis, René Vidal, and Nicolas Loizou. Stochastic extragradient with random reshuffling: Improved convergence for variational inequalities. In International Confer- ence on Artificial Intelligence and Statistics, pages 3682–3690. PMLR, 2024

    work page 2024

  2. [1]

    SGD with shuffling: optimal rates without component convexity and large epoch requirements.Advances in Neural Information Processing Systems, 33:17526–17535, 2020

    Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements.Advances in Neural Information Processing Systems, 33:17526–17535, 2020

    2020

  3. [2]

    Stochastic variance reduction for variational inequality methods

    Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory, pages 778–816. PMLR, 2022

    work page 2022

  4. [3]

    Arrow and Leonid Hurwicz

    Kenneth J. Arrow and Leonid Hurwicz. Reduction of constrained maxima to saddle-point problems. In Proc. Third Berkeley Symp. on Math. Statist. and Prob., volume 5, pages 1–20,

    work page

  5. [4]

    A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games

    Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games. In 10 International Conference on Artificial Intelligence and Statistics, pages 2863–2873. PMLR, 2020

    work page 2020

  6. [5]

    Bauschke and Patrick L

    Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2nd edition, 2017

    work page 2017

  7. [6]

    Distributed saddle-point problems: Lower bounds, near-optimal and robust algorithms

    Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, near-optimal and robust algorithms. arXiv preprint arXiv:2010.13112, 2020

    arXiv 2010

  8. [7]

    Smooth monotone stochastic variational inequalities and saddle point problems: A survey

    Aleksandr Beznosikov, Boris Polyak, Eduard Gorbunov, Dmitry Kovalev, and Alexander Gasnikov. Smooth monotone stochastic variational inequalities and saddle point problems: A survey. European Mathematical Society Magazine, 127:15–28, 2023

    work page 2023

Show all 81 references
  1. [8]

    Curiously fast convergence of some stochastic gradient descent algorithms

    Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Paris, volume 8, pages 2624–2633. Citeseer, 2009

    2009

  2. [9]

    Stochastic Halpern iteration with variance reduction for stochastic monotone inclusions

    Xufeng Cai, Chaobing Song, Cristóbal Guzmán, and Jelena Diakonikolas. Stochastic Halpern iteration with variance reduction for stochastic monotone inclusions. Advances in Neural Information Processing Systems, 35:24766–24779, 2022

    2022

  3. [10]

    Variance reduction for matrix games

    Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. Advances in Neural Information Processing Systems, 32, 2019

    2019

  4. [11]

    Tighter lower bounds for shuffling SGD: Random permutations and beyond

    Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling SGD: Random permutations and beyond. In International Conference on Machine Learning, pages 3855–3912. PMLR, 2023

    2023

  5. [12]

    Taming GANs with Lookahead-minmax

    Tatjana Chavdarova, Matteo Pagliardini, Sebastian U Stich, François Fleuret, and Martin Jaggi. Taming GANs with Lookahead-minmax. In The Ninth International Conference on Learning Representations, 2021

    2021

  6. [13]

    SGDA with shuffling: faster convergence for nonconvex-PŁ minimax optimization

    Hanseul Cho and Chulhee Yun. SGDA with shuffling: faster convergence for nonconvex-PŁ minimax optimization. In The Eleventh International Conference on Learning Representations, 2023

    2023

  7. [14]

    Single-call stochastic extragra- dient methods for structured non-monotone variational inequalities: Improved analysis under weaker conditions

    Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragra- dient methods for structured non-monotone variational inequalities: Improved analysis under weaker conditions. Advances in Neural Information Processing Systems , 36:64918–64956, 2023

    2023

  8. [15]

    Sampling without replacement leads to faster rates in finite-sum minimax optimization

    Aniket Das, Bernhard Schölkopf, and Michael Muehlebach. Sampling without replacement leads to faster rates in finite-sum minimax optimization. Advances in Neural Information Processing Systems, 35:6749–6762, 2022

    2022

  9. [16]

    On the ineffectiveness of variance reduced optimization for deep learning

    Aaron Defazio and Léon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. Advances in Neural Information Processing Systems, 32, 2019

    2019

  10. [17]

    Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for structured nonconvex-nonconcave min-max optimization. In International Conference on Artificial Intelligence and Statistics, pages 2746–2754. PMLR, 2021

    2021

  11. [19]

    Generative adversarial nets

    Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014

    2014

  12. [20]

    Stochastic extragradient: General analysis and improved rates

    Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pages 7865–7901. PMLR, 2022. 11

    2022

  13. [21]

    Extragradient method: O(1/K) last- iterate convergence for monotone variational inequalities and connections with cocoercivity

    Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/K) last- iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics, pages 366–402. PMLR, 2022

    2022

  14. [22]

    The landscape of the proximal point method for nonconvex–nonconcave minimax optimization

    Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. The landscape of the proximal point method for nonconvex–nonconcave minimax optimization. Mathematical Programming, 201(1-2):373–407, 2023

    2023

  15. [23]

    Fixed points of nonexpanding maps

    Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6):957–961, 1967

    1967

  16. [24]

    Harris, K

    Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fe...

    2020

  17. [25]

    Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling

    Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems, 33:16223–16234, 2020

    2020

  18. [26]

    J. D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engineering, 9 (3):90–95, 2007

    2007

  19. [27]

    Solving variational inequalities with stochastic mirror-prox algorithm

    Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17–58, 2011

    2011

  20. [28]

    Consistency trajectory models: Learning probability flow ODE trajectory of diffusion

    Dongjun Kim, Chieh-Hsin Lai, Wei-Hsiang Liao, Naoki Murata, Yuhta Takida, Toshimitsu Uesaka, Yutong He, Yuki Mitsufuji, and Stefano Ermon. Consistency trajectory models: Learning probability flow ODE trajectory of diffusion. In International Conference on Learning Representati...

    2024

  21. [29]

    Korpelevich

    Galina M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747–756, 1976

    1976

  22. [30]

    M. A. Krasnosel’ski˘ı. Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk, 10:123–127, 1955

    1955

  23. [31]

    Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity

    Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information Processing Systems, 34: ...

    2021

  24. [32]

    GraB: Finding provably better data per- mutations than random reshuffling

    Yucheng Lu, Wentao Guo, and Christopher De Sa. GraB: Finding provably better data per- mutations than random reshuffling. Advances in Neural Information Processing Systems, 35: 8969–8981, 2022

    2022

  25. [33]

    Robert Mann

    W. Robert Mann. Mean value methods in iteration. Proceedings of the American Mathematical Society, 4(3):506–510, 1953

    1953

  26. [34]

    Regularisation d’inéquations variationelles par approximations succesives

    Bernard Martinet. Regularisation d’inéquations variationelles par approximations succesives. Revue Française d’informatique et de Recherche opérationelle, 1970

    1970

  27. [35]

    Random reshuffling: Simple analysis with vast improvements

    Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems , 33: 17309–17320, 2020

    2020

  28. [36]

    Revisiting stochastic extragradient

    Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pages 4573–4582. PMLR, 2020

    2020

  29. [37]

    Towards deep learning models resistant to adversarial attacks

    Aleksander M ˛ adry, Aleksandar Makelov, Ludwig Schmdit, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. 12

    2018

  30. [38]

    A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach

    Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pages 1497–1507. PMLR, 2020

    2020

  31. [39]

    SGD without replacement: Sharper rates for general smooth convex functions

    Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703–4711. PMLR, 2019

    2019

  32. [40]

    Lectures on convex optimization, volume 137 of Springer Optimization and Its Applications

    Yurii Nesterov. Lectures on convex optimization, volume 137 of Springer Optimization and Its Applications. Springer, second edition, 2018

    2018

  33. [41]

    Nguyen, Quoc Tran-Dinh, Dzung T

    Lam M. Nguyen, Quoc Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, and Marten Van Dijk. A unified convergence analysis for shuffling-type gradient methods. The Journal of Machine Learning Research, 22(1):9397–9440, 2021

    2021

  34. [42]

    Solving stochastic weak Minty variational inequalities without increasing batch size

    Thomas Pethick, Olivier Fercoq, Puya Latafat, Panagiotis Patrinos, and V olkan Cevher. Solving stochastic weak Minty variational inequalities without increasing batch size. In International Conference on Learning Representations, 2023

    2023

  35. [43]

    Stable nonconvex-nonconcave training via linear interpolation

    Thomas Pethick, Wanyun Xie, and V olkan Cevher. Stable nonconvex-nonconcave training via linear interpolation. Advances in Neural Information Processing Systems, 37, 2023

    2023

  36. [44]

    L. D. Popov. A modification of the Arrow-Hurwitz method of search for saddle points. Matem- aticheskie Zametki, 28(5):777–784, 1980

    1980

  37. [45]

    Closing the convergence gap of SGD without replacement

    Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, pages 7964–7973. PMLR, 2020

    2020

  38. [46]

    Permutation-based SGD: Is random optimal? In International Conference on Learning Representations, 2022

    Shashank Rajput, Kangwook Lee, and Dimitris Papailiopoulos. Permutation-based SGD: Is random optimal? In International Conference on Learning Representations, 2022

    2022

  39. [47]

    Parallel stochastic gradient algorithms for large-scale matrix completion

    Benjamin Recht and Christopher Ré. Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation, 5(2):201–226, 2013

    2013

  40. [48]

    Generative modeling with optimal transport maps

    Litu Rout, Alexander Korotin, and Evgeny Burnaev. Generative modeling with optimal transport maps. In International Conference on Learning Representations, 2022

    2022

  41. [49]

    How good is SGD with random shuffling? In Conference on Learning Theory, pages 3250–3284

    Itay Safran and Ohad Shamir. How good is SGD with random shuffling? In Conference on Learning Theory, pages 3250–3284. PMLR, 2020

    2020

  42. [50]

    Random shuffling beats SGD only after many epochs on ill- conditioned problems

    Itay Safran and Ohad Shamir. Random shuffling beats SGD only after many epochs on ill- conditioned problems. Advances in Neural Information Processing Systems, 34:15151–15161, 2021

    2021

  43. [51]

    Solodov and Benar F

    Mikhail V . Solodov and Benar F. Svaiter. A hybrid approximate extragradient–proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Analysis, 7(4): 323–345, 1999

    1999

  44. [52]

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

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

    2020

  45. [53]

    Multi-agent reinforcement learning via double averaging primal-dual optimization

    Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. Advances in Neural Information Processing Systems, 31, 2018. 13

    2018

  46. [54]

    TaeHo Yoon and Ernest K. Ryu. Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm. In International Conference on Machine Learning, pages 12098–12109. PMLR, 2021

    2021

  47. [55]

    Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? In Conference on Learning Theory, pages 4653–4658

    Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? In Conference on Learning Theory, pages 4653–4658. PMLR, 2021

    2021

  48. [56]

    averaged

    Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations, 2022. 14 Contents 1 Introduction 1 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . ....

    2022

  49. [58]

    star-monotone

    + 3η3M (2ν2 − 1)2 8 Ψ2n−1 + 3η3M ν6e4 2n2 2n−1X j=1 (j − 1)Ψj−1 + ηM 4 η2 2 ∥F z0∥2 + η2 2 δ2 1 ≤ η3n3M ν2 + (2ν2 − 1)2 + 16νe4 5 ∥F z0∥2 + 3η3M 8 Ψ2n + 3η3M (2ν2 − 1)2 8 Ψ2n−1 + 3η3M ν6e4 2n2 2n−2X j=1 jΨj ≤ η3n3M 4ν4 + 16νe4 5 ∥F z0∥2 + 3η3M 8  Ψ2n + (2ν2 − 1)2Ψ2n−1 + 4ν6e...

  50. [59]

    = " 1 − β2 kL2 2 −βkL − β2 kL2 2 βkL − β2 kL2 2 1 − β2 kL2 2 # , (122) M2 := (I − βkA2 + αkβkA2 2)(I − βkA1 + αkβkA2

  51. [60]

    convergence

    = " 1 − β2 kL2 2 −βkL + β2 kL2 2 βkL + β2 kL2 2 1 − β2 kL2 2 # . (123) From this, we notice that the expectation of zk+1 0 2 conditional on zk 0 reads E h zk+1 0 2 zk 0 i = (zk 0 )⊤ M ⊤ 1 M1 + M ⊤ 2 M2 2 zk 0 . Working out the calculations, we can check that M ⊤ 1 M1 + M ⊤ 2 M...

  52. [61]

    That is, the iterate moves away from the equilibrium in expectation

    ∥zt∥2 ≤ E[∥zt+1∥2]. That is, the iterate moves away from the equilibrium in expectation

  53. [62]

    That is, the expected squared distance shrinks but is lower bounded by a certain constant independent of the stepsizes

    ∥zt∥2 ≥ E[∥zt+1∥2] ≥ γσ 2 2L2 . That is, the expected squared distance shrinks but is lower bounded by a certain constant independent of the stepsizes. Showing this immediately finishes the proof, because there is no way that any E[∥zt∥2] can get smaller than min{∥z0∥2 , γσ 2 ...

  54. [63]

    α > 1 L, in which case we show that SEG-RR makes (xk+1 0,1 )2 > (xk 0,1)2 hold deterministi- cally, so that if we initialize at x0 0,1 = σ√Lµ then we have E h zK 0 2i ≥ (xK 0,1)2 > (x0 0,1)2 = σ2 Lµ

  55. [64]

    α ≤ 1 L and β ≤ 1 µnK , in which case we show that SEG-RR initialized at y0 0 = σ√Lµ suffers E h zK 0 2i = Ω σ2 Lµ ,

  56. [65]

    α ≤ 1 L and 1 µnK < β <1 nL, in which case we show that SEG-RR initialized at x0 0,2 = 0 suffers E h zK 0 2i = Ω Lσ2 µ3nK 3 ,

  57. [66]

    large epoch

    α ≤ 1 L, β > 1 µnK , and β ≥ 1 nL in which case we show that SEG-RR initialized at x0 0,2 = 0 suffers E h zK 0 2i = Ω σ2 LµnK . Notice that the third case 1 µnK < β < 1 nL only makes sense when K > L/µ; otherwise, the third case just disappears. Hence, for the “large epoch” re...

    2000

  58. [67]

    Guidelines: • The answer NA means that the abstract and introduction do not include the claims made in the paper

    Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract and the introduction well summarizes our theoretical results and the problem settings we are considering....

  59. [68]

    Limitations

    Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: While we do not have a separate "Limitations" sections, in Section 3 we thoroughly discuss about the assumptions we have imposed. The paper is highly...

  60. [69]

    Full proofs of the theorems/lemmata/propositions can be found in the appendices

    Theory Assumptions and Proofs 74 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: Section 3 is devoted for the discussions on the assumptions. Full proofs of the theorems/...

  61. [70]

    We have also submitted the exact code that we used for our experiments as a supplemental material

    Experimental Result Reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and da...

  62. [71]

    Guidelines: • The answer NA means that paper does not include experiments requiring code

    Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We have submitted the exact...

  63. [72]

    The code we submit along with the paper is an exact copy of the one we used in the reported experiments, so the details not included in the paper shall be found in the code itself

    Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: The overall settings are disc...

  64. [73]

    Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [No] Justification: Our paper is mainly theoretical, and the experiment...

  65. [74]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experiments Compute Resources Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [No] Justification: The experiments are nume...

  66. [75]

    Guidelines: • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics

    Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: We have read through the Code of Ethics, but due to the theoretical nature of t...

  67. [76]

    Guidelines: • The answer NA means that there is no societal impact of the work performed

    Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 77 Answer: [NA] Justification: There are no societal impacts of this paper, as it is a theory paper. Guidelines: • The answer NA means...

  68. [77]

    Guidelines: • The answer NA means that the paper poses no such risks

    Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This paper is h...

  69. [78]

    No existing data nor models are used

    Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Packages used in...

  70. [79]

    Guidelines: • The answer NA means that the paper does not release new assets

    New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: Our paper provides novel theoretical results rather than datasets or models, hence this question is not applicable. G...

  71. [80]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Crowdsourcing and Research with Human Subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? A...

  72. [81]

    Guidelines: 79 • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals...

  73. [1956]

    of Calif

    Univ. of Calif. Press

Pith tools

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