PaperlayerView exact revision on arXiv

Source-linked AI summary

Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions

Jiaxiang Li

arXiv:2609.04578v1math.OCcs.LG

TL;DR

The paper studies sharp convergence for random-reshuffling SGD and epoch-wise ProxRR under average Hessian regularity. It centers permutation-prefix fluctuations and proves quadratic-scale rates, including Hölder and composite extensions, with matching lower bounds in the stated constant-stepsize regime.

  • Problem

    Random-reshuffling SGD has dependent within-epoch sampling, and prior non-quadratic second-order bounds retained a factor-n gap relative to quadratic lower bounds.

  • Method

    The analysis decomposes permutation prefixes into deterministic means and centered finite-population fluctuations, then applies Taylor expansion after centering and extends the argument through proximal nonexpansiveness.

  • Results

    The last-epoch smooth rate is Õ(T^-2 + n^2T^-3), average ν-Hölder curvature adds Õ(n^(1+ν)T^(-2-2ν)) with ν ≥ 1/2 preserving the quadratic scale, and ProxRR has a β⋆^2/K^2 splitting term plus matching lower bounds up to logarithms.

  • Takeaways & Limitations

    Finite-population centering and epoch-end proximal splitting are distinct mechanisms governing sharp reshuffling rates, while convex components permit the same scale without a large-epoch requirement.

  • Takeaways & Limitations

    The sharpness claims are restricted to constant-stepsize, last-iterate settings, and the composite result directly bounds distance rather than the raw objective gap when ψ may be +∞.

Abstract

from arXiv · show

We study stochastic gradient descent with random reshuffling for finite sums \[ F(x)=\frac1n\sum_{i=1}^n f_i(x). \] For fresh reshuffling with a constant component stepsize, if each $f_i$ has an $L$-Lipschitz gradient and the average $F$ is $μ$-strongly convex with a Lipschitz-continuous Hessian, we prove the last-epoch rate \[ \mathbb E[F(y_K)-F(x_\star)] =\widetilde O\!\left(T^{-2}+n^2T^{-3}\right), \qquad T=nK, \] matching the known quadratic lower bound in its $(n,K)$-dependence. The components may be nonconvex, and no componentwise Hessian continuity or separate bounded-iterate assumption is required. More generally, a $ν$-Hölder-continuous average Hessian adds only $\widetilde O(n^{1+ν}T^{-2-2ν})$, so every $ν\ge 1/2$ preserves the quadratic rate. Under convex components, a decreasing-stepsize result removes the large-epoch requirement and recovers the same two-term scale once $nK$ exceeds the condition-number scale. We also analyze epoch-wise ProxRR for $\mathcal P=F+ψ$. Writing $x^\dagger$ for the composite minimizer and $β_\star=\|\nabla F(x^\dagger)\|$, we prove \[ \mathbb E\|y_K-x^\dagger\|^2 =\widetilde O\!\left( \frac{β_\star^2}{K^2} +T^{-2}+n^2T^{-3} +n^{1+ν}T^{-2-2ν} \right). \] For $ν\ge 1/2$, we show that the $β_\star^2/K^2$ splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.

1 Introduction

The paper closes a factor-n gap in random-reshuffling convergence by using centered permutation prefixes, establishing sharp rates under weaker average-curvature assumptions and extending them to composite proximal objectives.

  • Motivation: Random reshuffling processes each finite-sum component once per epoch, but within-epoch label dependence makes its analysis more delicate than with-replacement SGD.With-replacement SGD has a generic O(T^-1) last-iterate benchmark under bounded stochastic-gradient second moments.
  • Novelty: Centering permutation-prefix partial sums before Taylor expansion closes the remaining factor-n gap in the non-quadratic second-order rate.The prior bound was Õ(T^-2 + n^3T^-3), whereas the paper targets the sharper n^2 dependence.
  • Main contributions: Under component smoothness, average strong convexity, and an average Lipschitz Hessian, the method permits nonconvex components without componentwise Hessian continuity or separate bounded-iterate assumptions.The resulting upper bound matches the quadratic lower bound in (n, K), according to the authors.
  • Main contributions: With convex components, decreasing stepsizes remove the large-epoch requirement and recover O(T^-2 + n^2T^-3) once nK is comparable to the condition-number scale.This result is valid for every K ≥ 1 but uses varying stepsizes, component convexity, and a bounded-iterates condition.
  • Composite extension: Epoch-wise ProxRR applies one proximal map after each reshuffled pass and yields a composite theorem whose leading terms are matched by a direct-sum lower bound up to logarithms.The composite analysis uses a different error measure from the smooth-objective comparison table.

2 Related work

Prior work established accelerated reshuffling rates, but sharp component-count dependence and composite extensions remained tied to narrower assumptions or separate settings.

  • With-replacement SGD provides the conventional O(T^-1) last-iterate benchmark, even when the average objective has additional Hessian regularity.
  • Earlier reshuffling analyses progressed from asymptotic explanations to nonasymptotic two-term rates and varying-step results for convex components.
  • The prior nonquadratic second-order bound had n^3T^-3 dependence, leaving a factor-n gap from the quadratic lower bound.
  • ProxRR applies one common proximal map after each epoch, while related nonsmooth methods use different proximal or trajectory-tracking constructions.
  • Related reshuffling work also studies distributed methods, variational inequalities, designed orderings, and prefix-balancing schemes.
  • The paper organizes its contributions around strongly convex, Hölder-Hessian, all-epoch, and composite ProxRR results, with proofs in appendices.

3 Problem formulation and main results

The paper analyzes fresh random reshuffling for smooth finite sums under strong convexity of the average, then derives sharp last-epoch rates and extensions to weaker curvature and composite objectives.

  • 3.1 Algorithm and assumptions: Random reshuffling samples a fresh uniform permutation each epoch and updates every component once, with y_K the last epoch iterate and h=nη the epoch stepsize.
  • 3.1 Algorithm and assumptions: The assumptions require L-Lipschitz component gradients and μ-strong convexity of F, while allowing nonconvex components.
  • 3.1 Algorithm and assumptions: The Lipschitz-Hessian regime regularizes only the average F; no corresponding Hessian condition is imposed on individual components.
  • 3.1 Algorithm and assumptions: Centered permutation prefixes reduce the summed second moment from order n^3 to order n^2, avoiding the direct path-wise scaling behind earlier bounds.
  • 3.1 Algorithm and assumptions: The analysis separately controls label-prefix dependence and the discrepancy between actual inner iterates and common-start reference iterates.
  • 3.1 Algorithm and assumptions: Hölder continuity of the average Hessian preserves the centered-prefix strategy because the first-order Taylor fluctuation has zero expectation.
  • 3.2 Main theorems: T^-2+n^2T^-3 is the Lipschitz-Hessian last-epoch scale, matching the quadratic dependence in n and K up to logarithms.
  • 3.2 Main theorems: Without Hessian continuity, the leading contribution loses a factor n because the epoch-error mean is controlled only through its standard deviation.

4 Proof ingredients for the main results

The proof combines deterministic contraction, finite-population prefix moments, trajectory control, and conditional-mean estimates to derive one-epoch recursions.

  • The analysis first obtains a full-gradient descent term and uses it to absorb state-dependent reshuffling errors.
  • Trajectory confinement derives uniform bounds on inner iterates and component gradients from the initial distance and a small epoch stepsize.
  • Centered prefixes decompose permutation sums into a deterministic average-gradient part and a zero-mean fluctuation.
  • Finite-population moments make the accumulated centered-prefix variance order n^2V rather than the order n^3 worst-case bound.
  • Within-epoch displacement and evaluation-error lemmas remain valid despite dependence between permutation sums and changing iterates.
  • Without extra regularity, Jensen’s inequality yields a universal mean-error bound and a one-epoch recursion with two additive variance terms.
  • The sharper regime replaces the changing-iterate analysis by reference iterates, then separates evaluation-point, label-coupling, and curvature errors.

5 Extensions: H¨older Hessians and all-epoch rates

The paper weakens componentwise Hessian assumptions to Hölder continuity of the average Hessian, preserving sharp reshuffling rates when ν is sufficiently large. A decreasing schedule under convex components removes the large-epoch requirement while recovering the same two-term scale.

  • Hölder-Hessian extension: The strongly convex Hölder-Hessian theorem applies for every K ≥ 1 under its stated stepsize and stability conditions, with the fixed-stepsize bound matching the quadratic lower bound in (n, K) up to logarithms.The lower-bound comparison is for the constant-stepsize, last-iterate model.
  • Hölder-Hessian extension: At ν = 1/2, the Hölder-curvature term reaches the K-decay exponent 3 of the quadratic-instance term 1/(nK^3); for larger ν, it is higher order.Thus the quadratic-instance scale remains dominant for ν ≥ 1/2.
  • Hölder-Hessian extension: Average Hölder curvature changes only the curvature term, from order n^2η^4 to n^(1+ν)η^(2+2ν) after summing over epochs.No Hölder condition is imposed on component Hessians.
  • All-epoch rates: Under convex components, a decreasing schedule controls the initial large-step phase and applies the sharper centered-prefix recursion later, removing the large-epoch condition.This result also assumes bounded iterates for the varying-stepsize schedule.
  • All-epoch rates: The all-epoch Hölder-Hessian theorem is valid for every K ≥ 1, and once nK exceeds the condition-number scale, ν ≥ 1/2 makes the Hölder term dominated by n^2q_K^-3.When n is at least on the order of the condition number, the two-term scale applies after a constant number of epochs.

6 Composite objectives and epoch-wise proximal reshuffling

The composite extension analyzes one-prox-per-epoch ProxRR using a proximal fixed-point comparison and centered-prefix bounds for the smooth inner pass. Its rate adds an epoch-end proximal-splitting term, which remains unavoidable even with identical components.

  • Composite ProxRR: Epoch-wise ProxRR applies one common proximal map after the n reshuffled gradient updates for P = F + ψ, with ψ proper, closed, and convex.The analysis permits nonconvex component functions while assuming strong convexity and Hölder curvature for the average.
  • Composite ProxRR: The composite recursion combines the reshuffling terms with an additional h^3β_⋆^2 term because ∇F(x†) need not vanish at the composite minimizer.The proximal fixed-point identity transfers the smooth pre-proximal error to the post-proximal iterate through nonexpansiveness.
  • Composite rates: The direct objective guarantee is stated for a certified proximal-gradient output because an extended-valued regularizer need not let squared distance upper-bound the raw objective gap.The theorem is therefore primarily formulated in squared distance to x†.
  • Lower bound: The β_⋆^2/K^2 term is an epoch-level proximal-splitting error, persists when all components are identical, and cannot be improved by better permutation moments.The lower-bound construction has zero centered permutation variance, while the remaining leading terms are genuine reshuffling errors.
  • Lower bound: For ν ≥ 1/2, the composite lower bound matches the three leading terms up to logarithms in the stated constant-stepsize regime.The sharpness scope excludes varying stepsizes, adaptive algorithms, and averaged outputs.

7 Scope and limitations

The results cover specific algorithmic regimes and assumptions, with sharpness established only for stated constant-stepsize settings and selected parameter ranges.

  • Algorithmic scope: The finite-horizon results use fresh reshuffling, constant component stepsizes, and the last epoch iterate, while the composite result controls squared distance to x†.The all-epoch result instead uses decreasing stepsizes, convex components, and a bounded-iterates condition.
  • Algorithmic scope: Corollary 6.6 does not directly bound the composite objective gap because ψ may equal +∞; it instead applies a full proximal-gradient step.The established guarantee is therefore on a transformed output rather than directly on P(y_K) − P(x†).
  • Sharpness scope: The constant-stepsize sharpness claim excludes varying stepsizes, adaptive algorithms, and averaged outputs.It compares the last-iterate upper bound with the quadratic lower bound in the stated regime.
  • Sharpness scope: The ProxRR splitting term β⋆^2/K^2 is unavoidable even when all components are identical, and the combined lower bound matches three leading terms up to logarithms.The combined result requires the additional large-horizon condition and fixed problem-parameter assumptions.
  • Parameter scope: The constant-stepsize corollaries require K ≥128(L/µ)^2 log T or K ≥256(L/µ)^2 log T, whereas the varying-stepsize theorem applies for every K ≥1 under stronger assumptions.The displayed constants are conservative in condition number and problem-dependent gradient bounds.
  • Assumptions: The main theorems assume global smoothness, global strong convexity of the average, and global average-Hessian regularity, and all guarantees are in expectation.A high-probability extension would require concentration for dependent label and evaluation-point errors.
  • Optimality boundaries: For ν < 1/2, the extra Hölder term is not shown necessary, and arbitrary varying schedules lack the cited lower-bound coverage.The ProxRR lower bounds hold only for constant stepsizes in the stated range, with the combined bound requiring an additional large-horizon condition.

8 Conclusion

The paper analyzes reshuffling through centered permutation-prefix decompositions and controls the resulting label and evaluation-point errors. It derives sharp strongly convex, Hölder-Hessian, and epoch-wise proximal rates while identifying finite-population centering and epoch-end splitting as distinct mechanisms.

  • Conclusion: The proof decomposes each permutation prefix into a deterministic mean and centered finite-population fluctuation before expanding the average gradient.This ordering makes the linear term in the centered fluctuation vanish in expectation.
  • Conclusion: Two errors require separate control: dependence of the current component on preceding labels and evaluation at changing inner iterates.A label-transposition argument handles the first, while a reference-prefix comparison handles the second.
  • Conclusion: The sharp last-iterate rate holds for a smooth strongly convex average with a Lipschitz Hessian.The supplied conclusion identifies the rate as sharp but does not reproduce its full displayed expression.
  • Conclusion: A ν-Hölder average Hessian adds only Õ(n^(1+ν)T^(-2-2ν)), so ν ≥1/2 preserves the quadratic rate.With convex components and bounded iterates, varying stepsizes remove the epoch lower bound and reach the same scale near the condition-number threshold.
  • Conclusion: For epoch-wise ProxRR, nonexpansiveness reduces post-proximal distance analysis to the corresponding pre-proximal smooth epoch error.The resulting bound includes an additional β⋆^2/K^2 term.
  • Conclusion: The β⋆^2/K^2 term is intrinsic to applying the common proximal map only once per epoch.The paper presents finite-population centering and epoch-end splitting as distinct rate-governing mechanisms.
  • Conclusion: Future work includes Hölder-specific lower bounds for ν <1/2, high-probability guarantees, and all-epoch results without bounded-iterates assumptions.These directions correspond to explicit gaps or scope boundaries identified by the paper.

A Proofs for the baseline strongly convex results

The baseline proof establishes confinement, contracts epoch endpoints, and controls permutation-prefix fluctuations through deterministic inequalities and conditional expectations.

  • Baseline lemmas: Averaging component smoothness yields Lipschitz continuity of ∇F, while strong convexity and smoothness bound the objective through squared distance to x⋆.These relations connect the distance recursion to objective error.
  • Baseline lemmas: The confinement argument keeps every inner iterate within a controlled ball when the epoch stepsize is sufficiently small.Component smoothness bounds gradients before a hypothetical escape, producing a contradiction.
  • Epoch recursion: The epoch endpoint is decomposed into the initial error, the mean gradient step, and a reshuffling remainder.The endpoint expansion then separates contraction, variance, and state-dependent corrections.
  • Epoch recursion: Cross terms are controlled without assuming independence between fluctuation terms, using deterministic two-vector inequalities and Young’s inequality.The resulting corrections are absorbed into the contraction margin under the stepsize condition.
  • Epoch recursion: Conditional expectation over a fresh permutation converts the one-epoch recursion into a geometric bound across epochs.The proof conditions on the epoch start and uses the uniform gradient-variance bound.
  • Rate extraction: The horizon and stepsize substitutions yield the stated baseline rate, with the initialization term scaled as D^2/T^2.The n^2/T^3 contribution is dominated by n/T^2 under the stated comparison.

A.3 Lipschitz-Hessian regime

The Lipschitz- and Hölder-Hessian analyses preserve the baseline treatment of label and evaluation-point errors while replacing the curvature remainder and deriving the corresponding rate terms.

  • Lipschitz-Hessian regime: The actual iterate differs from the reference prefix because gradients are evaluated at changing inner points rather than the epoch start.The proof bounds this evaluation-point error before applying the conditional-mean decomposition.
  • Lipschitz-Hessian regime: Permutation conditioning and label transpositions control dependence between the current component and previously used labels.Uniform conditional laws and swapped labels yield the comparison needed for the label error.
  • Lipschitz-Hessian regime: The conditional reference remainder splits into label, curvature, and bias vectors.This identity isolates the terms that are bounded separately in the endpoint recursion.
  • Lipschitz-Hessian regime: For Lipschitz Hessians, Taylor expansion and zero conditional mean of the centered fluctuation control the curvature contribution.The Hessian regularity assumption supplies the needed remainder estimate.
  • Lipschitz-Hessian regime: The remaining state corrections are absorbed into contraction, including the evaluation remainder under the epoch stepsize condition.The proof bounds the resulting coefficient and obtains the baseline endpoint recursion.
  • Lipschitz-Hessian regime: The Lipschitz-Hessian theorem follows by conditioning on epoch starts, applying the one-epoch recursion, and summing geometrically.Trajectory confinement supplies the uniform gradient bound used in this step.
  • Hölder-Hessian regime: For a ν-Hölder Hessian, the integral Taylor remainder replaces the Lipschitz-Hessian curvature term and benefits from cancellation of the linear fluctuation term.Lyapunov’s inequality and concavity yield the Hölder-specific bound.
  • Hölder-Hessian regime: Substituting the constant stepsize produces the Hölder rate and compares its extra term with the quadratic benchmark through the fact that quadratic averages have ρν = 0.The supplied proof passage states the substitution but not the full displayed corollary formula.

B.2 All-epoch proof under convex components

The proof establishes the all-epoch recursion by combining per-update control, two regimes for later epochs, and a polynomial summation lemma, then absorbs initialization and first-epoch residuals. It extends the argument to the composite proximal setting through conditional epoch recursions and invariance of a bounded region.

  • Polynomial summation: The summation lemma contracts an error introduced at index j by approximately (q_j/q_N)^a and explains the resulting powers of q_N and the spacing d.Applying it with several (p,r) pairs sums the later-epoch residuals and produces the terms in the theorem’s final bound.
  • Epoch recursion: The proof uses Lemma 5.7 to control individual updates and derives a first-epoch bound under decreasing stepsizes.The stepsizes are at most 2/L, and the resulting recursion tracks expected squared distance plus polynomial residual terms.
  • Epoch recursion: Later epochs are handled in two regimes according to h > µ/(32L^2) or h ≤ µ/(32L^2), with both yielding a common contraction-and-error recursion.The large-h regime applies the per-update lemma successively, while the small-h regime uses the Hölder one-epoch estimate.
  • Final bound: The proof absorbs the first-epoch residuals separately for n ≤ q_0 and n > q_0, completing the all-epoch bound.The initialization contribution is combined with the later-epoch estimate, and fixed factors are absorbed into constants.
  • Final bound: When T = nK exceeds the initial denominator scale, q_K is comparable to T, so the corollary inherits the displayed order for every term.The objective bound then follows from the distance-to-objective relation.
  • Composite extension: The composite analysis controls proximal epochs through a contraction recursion, bounded iterates, and a decomposition of reshuffling, Hölder, and evaluation errors.The error estimates are established before the proximal map; non-expansiveness preserves them, and for ν ≥ 1/2 the Hölder term is dominated by n^2T^-3.

C.2 Proximal-splitting lower bounds

The lower-bound construction combines a random-reshuffling hard quadratic block with a deterministic proximal splitting block. Block separability makes the two lower-bound contributions add, yielding matching squared-distance and objective-gap lower bounds in the stated regime.

  • Splitting block: The splitting recursion produces a 1/K^2 lower bound in the stated constant-stepsize regime.The proof treats naK ≤ 1/4 and naK > 1/4 separately, then identifies the remaining objective gap with a quadratic gap.
  • Splitting block: The splitting block uses a shifted quadratic with an ℓ1-type proximal term and an invariant positive soft-thresholding branch.The construction chooses c > nλ/µ and derives exact recursions for the two coordinates.
  • Product construction: The proximal map acts only on the v-coordinate, while the z-coordinates reproduce the Safran–Shamir random-reshuffling instance.The product minimizer separates across blocks, and the same permutation can be shared without changing either block’s recursion.
  • Reshuffling block: The reshuffling hard block contributes an objective lower bound with scale 1/(nK)^2 + 1/(nK^3).Because the hard block is a smooth quadratic, this objective lower bound also yields a squared-distance lower bound up to a fixed factor.
  • Combined lower bound: Adding the reshuffling and splitting lower bounds proves the final lower bound for both squared distance and objective gap.The second argument of the minimum is active under the stated condition, and the product objective gap decomposes across the two blocks.
Loading 2609.04578v1…