Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems

Chulhee Yun; Jaeyoung Cha; Yujun Kim

REVIEW 3 major objections 4 minor 29 references

Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems

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

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

Pith's one-line read Incremental gradient descent can be dramatically slower than shuffled SGD when the epoch count is below the condition number.

desk verdict Solid lower bounds on small-epoch IGD, undermined by a false matching upper bound that needs fixing. read the letter →

arxiv 2506.04126 v1 pith:RJKOFKJS submitted 2025-06-04 cs.LG math.OC

Yujun Kim , Jaeyoung Cha , Chulhee Yun This is my paper

classification cs.LGmath.OC MSC 90C2590C0668W40

keywords incrementalgradientdescentpermutation-basedSGDsmallepochregimelowerboundsconditionnumberstrongconvexityrandomreshufflingfinite-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

This paper proves that Incremental Gradient Descent, the simplest permutation-based method that cycles through components in a fixed order, can converge far more slowly in the regime where the number of epochs K stays below the condition number κ. With strongly convex components sharing one Hessian, the final optimality gap can be Ω(G²/(µK)) for any constant step size; removing the shared-Hessian assumption makes the bound worse, and allowing nonconvex components makes it grow roughly exponentially in κ/K. The paper also shows that the fixed order is the culprit rather than permutation-based descent itself: some fixed permutation, chosen by herding the component gradients at the optimum, does beat with-replacement SGD in this regime. Matching upper and lower bounds for the large epoch regime complete the picture.

What carries the argument

The argument rides on a dimension-aggregation lower-bound technique: the step-size axis is partitioned into small, moderate, and large regimes, a low-dimensional quadratic (or near-quadratic) objective is built for each regime that is provably slow for step sizes in that regime, and the functions are summed across separate coordinates so that every constant step size inherits at least one slow coordinate. The moderate-regime constructions carry the novelty: Theorem 3.3 arranges the component minimizers as a regular n-polygon via rotated quadratics, so the iterate sequence preserves rotational symmetry and cycles around the global minimizer at constant distance, and Theorem 3.5 inserts concave directions that multiply the iterate by a factor (1 + ηL/2)^{n/2} per epoch, producing the exponential term. On the positive side, the Herding lemma, a discrepancy bound on prefix sums of the component gradients at the optimum, selects a permutation whose cumulative gradient error stays bounded, yielding the acceleration result.

What would settle it

Run IGD with a time-varying (e.g., decaying) step size on the 3-dimensional identical-Hessian construction of Theorem 3.1 for K ≤ κ/2 and measure the final optimality gap: a gap dropping below the proved Ω(G²/(µK)) by a factor growing with n would show the constant-step-size assumption is the load-bearing restriction. Equivalently, an upper bound of O(G²/(µnK)) for IGD with variable step sizes in the small epoch regime would settle the question analytically.

Watch

Extended reading notes

Core claim

In the small epoch regime K ≲ κ, the paper establishes lower bounds on IGD's final optimality gap under a constant step size: Ω(G²/(µK)) when every component shares the same Hessian (Theorem 3.1); Ω((LG²/µ²) min{1, κ²/K⁴}) when components are merely strongly convex (Theorem 3.3); and Ω(min{µD², (G²/L)(1 + L/(2µnK))ⁿ}) when some components are nonconvex (Theorem 3.5), the last being roughly exponential in κ/K. The first rate is a factor n slower than the known with-replacement SGD upper bound O(G²/(µnK)), under assumptions more favorable to IGD. Complementing these, the paper proves an upper bound for arbitrary permutations with identical Hessians (O(G²*/µK)), an upper bound for strongly convex components (O(L²G²*/(µ³K²))), and a permutation-based method achieving H²L²G²*/(µ³n²K²), the first result showing a permutation-based method outperforming with-replacement SGD in this regime. In the large epoch regime K ≳ κ the bounds tighten to matching LG²/(µ²K²) for convex components and L²G²/(µ³K²) for nonconvex ones, showing the exponential slowdown is confined to small K.

Load-bearing premise

The lower bounds only cover a constant step size, while the faster with-replacement SGD rate they are compared against comes from a varying-step-size analysis; give IGD an adaptive or decaying step size and the trapping constructions may stop working.

Editorial extensions

If this is right

With a constant step size, IGD cannot match the known with-replacement SGD rate O(G²/(µnK)) in the small epoch regime; the identical-Hessian lower bound already leaves a factor n gap.
The slowdown sharpens as assumptions weaken: polynomial in 1/K with identical Hessians, worse min{1, κ²/K⁴} with distinct strongly convex components, and roughly exponential in κ/K once nonconvex components enter.
The large epoch regime (K ≳ κ) is qualitatively different: bounds match up to polylog factors, and nonconvex components cost only an extra κ factor rather than an exponential one.
A fixed permutation produced by herding at the optimum achieves the optimal n, K dependence among permutation methods and beats with-replacement SGD when n ≳ H²κ²/K, but implementing it requires knowing the component gradients at the optimum.
The lower bounds are tailored to the identity permutation, so they do not settle random reshuffling; the paper leaves RR's small-epoch behavior as an open problem.

Reading between the lines

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

If the constant-step-size restriction is what makes the trapping constructions work, then adaptive or decaying step sizes may restore faster convergence for IGD; running Theorem 3.1's construction under an epoch-decaying step size is a direct way to check this.
The rotational-polygon construction suggests a general failure mode: when component minimizers are arranged with high symmetry, deterministic cyclic updates can be trapped on a closed trajectory, and randomized reshuffling plausibly breaks this symmetry, which may explain why RR avoids the worst case in the paper's experiments.
The herding result indicates that in the small-epoch regime the quantity to control is the worst prefix sum of gradient errors at the optimum, so building an implementable permutation rule that estimates these errors online is a concrete next step.
The MNIST and CIFAR-10 experiments indicate practitioners using fixed cyclic data order with small epoch budgets may be leaving performance on the table, and that adaptive ordering could be most valuable early in training before K reaches κ.

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.

Desk Editor's Note

read the letter

This paper is worth reading for the lower bounds. The small-epoch regime of IGD is genuinely open, and the authors produce three separate constructions showing that even with strongly convex components, IGD can be much slower than previously known. Theorem 3.1 improves the identical-Hessian lower bound by a factor of K; Theorem 3.3's rotating polygon construction is elegant; Theorem 3.5's exponential slowdown with nonconvex components is striking and the experiments confirm the intended behavior. The large-epoch tight bounds are a nice addition. I believe the lower-bound proofs are solid. The soft spot is Theorem 3.2. As the stress-test note shows, the step size η = (1/(μ n K)) max{log(L|x0-x*|/G*), 1} can exceed 1/L when the log term is large, and the contraction argument (Lemma C.1) requires η < 1/L. The concrete example with n=2, K=1, μ=1, L=2, x0=e^{100} gives ηL ≈ 100.7 and the algorithm diverges. This is a real bug, not a technicality. The needed fix is probably to add a condition like K ≥ (κ/n) max{log(...), 1} as in Proposition 3.4 and Theorem 3.7, but that narrows the small-epoch regime. So the claimed matching upper bound in Table 1 is not correct as stated, and the narrative that the same-Hessian case is fully understood is premature. That said, the lower bounds are independent of Theorem 3.2 and I see no reason to doubt them. The paper's comparison with with-replacement SGD is careful, noting the step-size mismatch. The Herding-at-optimum existence result is interesting and clearly flagged as impractical. In summary: this is a paper with one load-bearing flaw in the upper-bound side, surrounded by a solid lower-bound contribution. It deserves peer review, but with a mandatory fix to Theorem 3.2 before acceptance.

Referee Report

3 major / 4 minor

Summary. This paper studies incremental gradient descent (IGD) and generic permutation-based SGD for finite-sum minimization when the number of epochs K is smaller than the condition number kappa. The main contributions are lower bounds on the final optimality gap in the small-epoch regime under three component assumptions: identical Hessians (Theorem 3.1, Omega(G^2/(mu K))), distinct strongly convex components (Theorem 3.3, Omega((L G^2/mu^2) min{1, kappa^2/K^4})), and potentially nonconvex components (Theorem 3.5, Omega(min{mu D^2, (G^2/L)(1+L/(2 mu n K))^n})). It also states an upper bound for arbitrary permutations in the identical-Hessian case (Theorem 3.2, O(G_*^2/(mu K))), an existence result for a Herding-based permutation beating with-replacement SGD (Theorem 3.7), and matching lower and upper bounds in the large-epoch regime (Theorems 4.1, 4.3, 4.4). Experimental validation is provided for the lower-bound constructions and on MNIST and CIFAR-10.

Significance. The lower-bound constructions are the paper's main value. The rotating-polygon construction behind Theorem 3.3 and the concave-component construction behind Theorem 3.5 are nontrivial, and the dimension-aggregation technique is executed carefully. If the identified issues are repaired, these results significantly advance the understanding of the small-epoch regime, complementing prior work by Safran and Shamir. The paper is also honest about limitations: it notes the constant-step-size caveat for Theorem 3.1 and the open status of random reshuffling. However, the stated matching upper bound in the identical-Hessian case (Theorem 3.2) is not valid as written, and the proof of Theorem 3.5 does not cover the claimed parameter range. These are load-bearing issues for the paper's central narrative.

major comments (3)

[Theorem 3.2 and Section C.1] Theorem 3.2 is false as stated. The theorem sets eta = (1/(mu n K)) max{log(L|x0-x*|/G_*),1} and assumes only kappa/n <= K <= kappa, but the proof relies on Lemma C.1, which requires eta < 1/L, and on equation (17), which requires the exponential contraction e^{-eta mu n K} to reduce the initialization term. No hypothesis guarantees eta < 1/L. Concretely, with n=2, K=1, mu=1, L=2, f1(x)=0.5x^2+x, f2(x)=0.5x^2-x, x0=e^{100}, we have kappa=2, kappa/n=1 <= K=1 <= kappa, G_*=1, and the prescribed eta is approximately 50.3, so eta L is about 100.7 > 2. One epoch of IGD then gives x2 = 2401 x0 + 2450, and the optimality gap is on the order of (2401^2/2)e^{200}, not O(G_*^2/(mu K)). The theorem can be repaired by adding the initialization-dependent condition K >= (kappa/n) max{log(L|x0-x*|/G_*),1}, as Proposition 3.4 does, but that condition is incompatible with K <= kappa unless |x0-x*| <= (G_*/L)e^{O(n)}. Consequently, Table 1's claimed matching upper bound for the identical-Hessian small-epoch case, and the associated narrative, require revision.
[Section B.3.2, proof of Theorem 3.5] The proof of Theorem 3.5 does not establish the claimed lower bound for all constant step sizes. In the construction of F2, the proof of equation (15) and the subsequent lower bound use the inequality (1+eta L/2)^{n/2}(1+(1-eta L)^{n/2}) - 2 > (1+eta L/2)^{n/2} - 2. This requires (1-eta L)^{n/2} > 0, which fails when eta > 1/L and n/2 is odd, for example n=6. The theorem asserts a bound for all eta >= 1/(mu n K), but the supplied argument only covers eta < 1/L. Additionally, the same construction states that F2 is mu-strongly convex because L/4 >= mu, but averaging the component functions gives F2(x) = (L/8)x^2, so the strong convexity parameter is L/8. Assumption 2.3 therefore requires kappa >= 8, not merely kappa >= 4 as stated in Theorem 3.5. These two gaps mean the theorem's parameter range and step-size coverage are not justified by the proof.
[Proposition 3.4 and Theorem 3.7] The statements of Proposition 3.4 and Theorem 3.7 assume only K >= kappa/n (up to the paper's 'less than or similar' convention), but their proofs (Sections C.2 and C.3) explicitly require the stronger, initialization-dependent condition K >= 2 kappa/n max{log(||x0-x*|| mu K sqrt(kappa)/G_*),1} (respectively with the Herding factor H). The paper defines x <= y to allow only polylog(n,K,mu,L,...) factors, which cannot absorb a logarithmic term depending on ||x0-x*|| or G_*. Therefore the stated ranges for these upper bounds are overbroad, and the theorems should either include the explicit epoch condition or the defining notation of the asymptotic symbols must be extended. This is not merely cosmetic: the same missing condition is what makes Theorem 3.2 false, and the affected propositions appear in Table 1 and in the comparison with with-replacement SGD.

minor comments (4)

[Theorem 3.2] The statement uses log(L|x0-x*|/G_*); when G_* = 0 the expression is undefined, and the theorem should state the convention for G_* > 0 or handle the case by a limit.
[Table 1] The table omits the initialization-dependent epoch condition for the upper-bound rows; after the discussion in the major comments, these rows should be annotated with the actual condition K >= (kappa/n) max{log(...),1} or a similarly explicit requirement.
[Figure 1] The axis label in Figure 1 appears garbled ('1 n max{3/n2, 3/2}'), and the legend should be updated once Theorem 3.2 is corrected.
[Section B.3.2] The proof says that for odd n it uses n-1 components and adds a zero component, 'modifying parameters by at most a constant factor'. Since the bound depends on n in the exponent, the constant-factor claim should be quantified.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bounds are hard-instance constructions and the upper bounds are derived from stated assumptions or external lemmas; self-citations are not load-bearing.

full rationale

Score 0. The main lower-bound theorems (3.1, 3.3, 3.5, 4.1, 4.3) are proved by explicitly constructing functions and initializations and by partitioning the step-size axis into regimes. The paper states this directly in Section B.1: "we partition the positive real line of possible step sizes into three regimes... For each regime, we design a distinct lower-bound function tailored to follow the stated convergence behavior within that range. Finally, we combine these functions across dimensions, ensuring that the resulting function satisfies the stated lower bound for any choice of step size." This is the standard and legitimate way to prove an Omega-rate: the construction does not use the rate as an input, and no fitted parameter is later renamed as a prediction. The upper bounds are either proved from Assumptions 2.3/2.5 and the contraction Lemma C.1 (Theorem 3.2), from the externally sourced Herding lemma (Theorem 3.7), or are explicitly attributed to prior non-self work (Mishchenko et al. 2020 for Proposition 3.4; Liu and Zhou 2024a for Proposition 4.2). The self-citations in the paper (Cha et al. 2023, Yun et al. 2022, Ahn et al. 2020) are used as benchmarks, as sources of a proof technique, or as an external lower bound against which Theorem 3.7 is compared; none of these citations supplies the conclusion of the theorem being proved. The paper also flags its own limitations, including that the small-epoch comparison uses a constant step size with the varying-step-size case left open, and that Theorem 3.7 is not implementable because it requires knowledge of component gradients at the optimum; these admissions further indicate that the claims are not definitionally forced. A separate correctness concern exists, namely that Theorem 3.2's proof invokes Lemma C.1's condition eta < 1/L, while the stated hypotheses and step-size formula do not obviously guarantee it for arbitrary initialization; this may make the theorem false as stated, but that is a proof gap, not circularity.

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

The paper introduces no fitted constants and no new physical or mathematical entities. Problem parameters mu, L, G, G*, P, n, and K are inputs to the theorems or are chosen inside lower-bound constructions, which is standard for worst-case lower bounds. The only external constructions relied upon are the Herding algorithm and prior optimization theorems, both cited in the text.

assumptions (6)

domain assumption Assumption 2.3: F is mu-strongly convex and each component f_i is L-smooth.
This is the function class for all theorems in the paper; it is invoked throughout and is part of the problem setting, not a derived fact.
domain assumption Assumption 2.4: ||grad f_i(x) - grad F(x)|| <= G + P ||grad F(x)||.
Used in Theorems 3.1, 3.3, 3.5, 4.1, 4.3, and 4.4 to control gradient noise; the lower bounds construct functions that satisfy it with chosen P.
domain assumption Assumption 2.5: ||grad f_i(x*)|| <= G*.
Used in Theorem 3.2, Proposition 3.4, and Theorem 3.7 to measure the gradient spread at the optimum; it is the main quantity in those upper bounds.
domain assumption Herding algorithm (Lemma 3.6) outputs a permutation with discrepancy H = O_tilde(sqrt(d)).
Theorem 3.7 relies on this external algorithmic result from Bansal and Garg (2017); the paper states the lemma but does not prove it.
standard math Standard analytic inequalities, e.g., (1-1/m)^m >= 1/4 and root-of-unity summation identities.
These are used in the lower-bound constructions in Sections B and D without proof.
domain assumption Prior upper bounds Mishchenko et al. (2020) Theorem 5 and Liu and Zhou (2024a) Theorem 4.6, restated as Proposition 3.4 and Proposition 4.2.
The paper relies on these previously published upper bounds for comparisons and for completing the large-epoch picture; they are not re-proved.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems." pith.science (2026). https://pith.science/paper/RJKOFKJS

@misc{pith2026250604126,
  author       = {Pith},
  title        = {Pith review of: Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RJKOFKJS}},
  note         = {Machine review of arXiv:2506.04126}
}

abstract

Recent theoretical results demonstrate that the convergence rates of permutation-based SGD (e.g., random reshuffling SGD) are faster than uniform-sampling SGD; however, these studies focus mainly on the large epoch regime, where the number of epochs $K$ exceeds the condition number $\kappa$. In contrast, little is known when $K$ is smaller than $\kappa$, and it is still a challenging open question whether permutation-based SGD can converge faster in this small epoch regime (Safran and Shamir, 2021). As a step toward understanding this gap, we study the naive deterministic variant, Incremental Gradient Descent (IGD), on smooth and strongly convex functions. Our lower bounds reveal that for the small epoch regime, IGD can exhibit surprisingly slow convergence even when all component functions are strongly convex. Furthermore, when some component functions are allowed to be nonconvex, we prove that the optimality gap of IGD can be significantly worse throughout the small epoch regime. Our analyses reveal that the convergence properties of permutation-based SGD in the small epoch regime may vary drastically depending on the assumptions on component functions. Lastly, we supplement the paper with tight upper and lower bounds for IGD in the large epoch regime.

Figures

Figures reproduced from arXiv: 2506.04126 by the authors.

**Figure 2.** Trajectory of IGD with the function for Theorem 3.3, starting from the x ∗ (the origin, purple dot), when K = 20. Blue dots starting point of each epoch, x k 0 , while the cyan dot indicates the final iterate x K 0 [PITH_FULL_IMAGE:figures/full_fig_p053_2.png] view at source ↗

**Figure 3.** Experiments on Theorem 3.3 for IGD, RR, Herding at Optimum, and with-replacement SGD. Both axes are log-scaled. G.2. Results for the Function in Theorem 3.5 Recall that the proof of Theorem 3.5 uses 4-dimensional functions, formulated through the “dimension aggregation” step. For a clear observation, we conduct experiments using the construction for the “Moderate & Large” step size regime, and remove the first dimen… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Experiments on Theorem 3.5 for IGD, RR, Herding at Optimum, and with-replacement SGD. Both axes are log-scaled [PITH_FULL_IMAGE:figures/full_fig_p054_4.png]

**Figure 5.** Figure 5: Experiments on MNIST dataset for IGD, RR, and with-replacement SGD. y-axis for the training loss is log-scaled [PITH_FULL_IMAGE:figures/full_fig_p055_5.png]

**Figure 6.** Figure 6: Experiments on CIFAR-10 dataset for IGD, RR, and with-replacement SGD. y-axis for the training loss is log-scaled. 56 [PITH_FULL_IMAGE:figures/full_fig_p056_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 24 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

SGD with shuffling: optimal rates without component convexity and large epoch requirements

Ahn, K., Yun, C., and Sra, S. SGD with shuffling: optimal rates without component convexity and large epoch requirements. Advances in Neural Information Processing Systems, 33: 0 17526--17535, 2020

work page 2020
[3]

and Garg, S

Bansal, N. and Garg, S. Algorithmic discrepancy beyond partial coloring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 914--926, 2017

work page 2017
[4]

Bertsekas, D. P. Incremental proximal methods for large scale convex optimization. Mathematical programming, 129 0 (2): 0 163--195, 2011

work page 2011
[5]

Bubeck, S. et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8 0 (3-4): 0 231--357, 2015

work page 2015
[6]

and Diakonikolas, J

Cai, X. and Diakonikolas, J. Last iterate convergence of incremental methods and applications in continual learning. arXiv preprint arXiv:2403.06873, 2024

arXiv 2024
[7]

Tighter lower bounds for shuffling SGD : Random permutations and beyond

Cha, J., Lee, J., and Yun, C. Tighter lower bounds for shuffling SGD : Random permutations and beyond. In International Conference on Machine Learning, pp.\ 3855--3912. PMLR, 2023

work page 2023
[8]

and Gower, R

Garrigos, G. and Gower, R. M. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023

arXiv 2023

Show all 29 references

[9]

An investigation into neural net optimization via hessian eigenvalue density

Ghorbani, B., Krishnan, S., and Xiao, Y. An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning, pp.\ 2232--2241. PMLR, 2019

2019
[10]

Gurbuzbalaban, M., Ozdaglar, A., and Parrilo, P. A. Convergence rate of incremental gradient and incremental newton methods. SIAM Journal on Optimization, 29 0 (4): 0 2542--2565, 2019

2019
[11]

and Sra, S

Haochen, J. and Sra, S. Random shuffling beats SGD after finite epochs. In International Conference on Machine Learning, pp.\ 2624--2633. PMLR, 2019

2019
[12]

U., and Jaggi, M

Koloskova, A., Doikov, N., Stich, S. U., and Jaggi, M. On convergence of incremental gradient for non-convex smooth functions. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=ZRMQX6aTUS

2024
[13]

First-order and stochastic optimization methods for machine learning, volume 1

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

2020
[14]

Visualizing the loss landscape of neural nets

Li, H., Xu, Z., Taylor, G., Studer, C., and Goldstein, T. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018

2018
[15]

and Zhou, Z

Liu, Z. and Zhou, Z. On the last-iterate convergence of shuffling gradient methods. In Forty-first International Conference on Machine Learning, 2024 a . URL https://openreview.net/forum?id=Xdy9bjwHDu

2024
[16]

and Zhou, Z

Liu, Z. and Zhou, Z. Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024 b . URL https://openreview.net/forum?id=xxaEhwC1I4

2024
[17]

Lu, Y., Guo, W., and Sa, C. D. Grab: Finding provably better data permutations than random reshuffling. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022 a . URL https://openreview.net/forum?id=nDemfqKHTpK

2022
[18]

Y., and De Sa, C

Lu, Y., Meng, S. Y., and De Sa, C. A general analysis of example-selection for stochastic gradient descent. In International Conference on Learning Representations (ICLR), volume 10, 2022 b

2022
[19]

Random reshuffling: Simple analysis with vast improvements

Mishchenko, K., Khaled, A., and Richt \'a rik, P. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33: 0 17309--17320, 2020

2020
[20]

Characterizing & finding good data orderings for fast convergence of sequential gradient methods

Mohtashami, A., Stich, S., and Jaggi, M. Characterizing & finding good data orderings for fast convergence of sequential gradient methods. arXiv preprint arXiv:2202.01838, 2022

2022 arXiv
[21]

SGD without replacement: Sharper rates for general smooth convex functions

Nagaraj, D., Jain, P., and Netrapalli, P. SGD without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pp.\ 4703--4711. PMLR, 2019

2019
[22]

M., Tran-Dinh, Q., Phan, D

Nguyen, L. M., Tran-Dinh, Q., Phan, D. T., Nguyen, P. H., and Van Dijk, M. A unified convergence analysis for shuffling-type gradient methods. Journal of Machine Learning Research, 22 0 (207): 0 1--44, 2021

2021
[23]

Closing the convergence gap of SGD without replacement

Rajput, S., Gupta, A., and Papailiopoulos, D. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, pp.\ 7964--7973. PMLR, 2020

2020
[24]

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

Rajput, S., Lee, K., and Papailiopoulos, D. Permutation-based SGD : Is random optimal? In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=YiBa9HKTyXE

2022
[25]

and R \'e , C

Recht, B. and R \'e , C. Toward a noncommutative arithmetic-geometric mean inequality: Conjectures, case-studies, and consequences. In Conference on Learning Theory, pp.\ 11--1. JMLR Workshop and Conference Proceedings, 2012

2012
[26]

and Shamir, O

Safran, I. and Shamir, O. How good is SGD with random shuffling? In Conference on Learning Theory, pp.\ 3250--3284. PMLR, 2020

2020
[27]

and Shamir, O

Safran, I. and Shamir, O. Random shuffling beats SGD only after many epochs on ill-conditioned problems. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https://openreview.net/forum?id=fNKwtwJHjx

2021
[28]

and Zhang, T

Shamir, O. and Zhang, T. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pp.\ 71--79. PMLR, 2013

2013
[29]

Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond

Yun, C., Rajput, S., and Sra, S. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=LdlwbBP2mlq

2022

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

SGD with shuffling: optimal rates without component convexity and large epoch requirements

Ahn, K., Yun, C., and Sra, S. SGD with shuffling: optimal rates without component convexity and large epoch requirements. Advances in Neural Information Processing Systems, 33: 0 17526--17535, 2020

work page 2020

[3] [3]

and Garg, S

Bansal, N. and Garg, S. Algorithmic discrepancy beyond partial coloring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 914--926, 2017

work page 2017

[4] [4]

Bertsekas, D. P. Incremental proximal methods for large scale convex optimization. Mathematical programming, 129 0 (2): 0 163--195, 2011

work page 2011

[5] [5]

Bubeck, S. et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8 0 (3-4): 0 231--357, 2015

work page 2015

[6] [6]

and Diakonikolas, J

Cai, X. and Diakonikolas, J. Last iterate convergence of incremental methods and applications in continual learning. arXiv preprint arXiv:2403.06873, 2024

arXiv 2024

[7] [7]

Tighter lower bounds for shuffling SGD : Random permutations and beyond

Cha, J., Lee, J., and Yun, C. Tighter lower bounds for shuffling SGD : Random permutations and beyond. In International Conference on Machine Learning, pp.\ 3855--3912. PMLR, 2023

work page 2023

[8] [8]

and Gower, R

Garrigos, G. and Gower, R. M. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023

arXiv 2023