PaperlayerView exact revision on arXiv

Source-linked AI summary

Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods

Amirkeivan Mohtashami, Sebastian Stich, Martin Jaggi

arXiv:2202.01838v1cs.LG

TL;DR

The paper asks how deterministic data orderings affect sequential gradient convergence when existing bounds treat all orders by their worst case. It develops order-specific convergence analysis, structured shuffling, and a greedy order-selection method, which can improve accuracy by more than 14 percent over random reshuffling in certain scenarios.

  • Problem

    Existing incremental-gradient bounds do not distinguish good from bad deterministic orderings, despite evidence that suitable orders can outperform random reshuffling.

  • Method

    The paper measures ordering suitability, derives bounds for arbitrary permutation sequences, and uses the measure for greedy and structured shuffling strategies.

  • Results

    The greedy ordering algorithm improves accuracy by more than 14 percent over random reshuffling in certain CIFAR10 training scenarios.

  • Takeaways & Limitations

    Order-specific analysis can guide practical data ordering, while structured shuffling can benefit optimization when dataset functions have multiple abstraction levels.

  • Takeaways & Limitations

    A gap remains between the best lower and upper convergence bounds achievable by optimizing order in the proposed framework.

Abstract

from arXiv · show

While SGD, which samples from the data with replacement is widely studied in theory, a variant called Random Reshuffling (RR) is more common in practice. RR iterates through random permutations of the dataset and has been shown to converge faster than SGD. When the order is chosen deterministically, a variant called incremental gradient descent (IG), the existing convergence bounds show improvement over SGD but are worse than RR. However, these bounds do not differentiate between a good and a bad ordering and hold for the worst choice of order. Meanwhile, in some cases, choosing the right order when using IG can lead to convergence faster than RR. In this work, we quantify the effect of order on convergence speed, obtaining convergence bounds based on the chosen sequence of permutations while also recovering previous results for RR. In addition, we show benefits of using structured shuffling when various levels of abstractions (e.g. tasks, classes, augmentations, etc.) exists in the dataset in theory and in practice. Finally, relying on our measure, we develop a greedy algorithm for choosing good orders during training, achieving superior performance (by more than 14 percent in accuracy) over RR.

1 Introduction

The paper studies how dataset ordering affects sequential gradient convergence, addressing bounds that distinguish neither good nor bad deterministic orders. It introduces order-specific analysis, structured shuffling, and a greedy ordering method that can outperform random reshuffling.

  • 1 Introduction: Random reshuffling uses a new random permutation each epoch, whereas single shuffling reuses a random permutation and incremental gradient descent uses a deterministic one.Existing rates for these fixed-order variants are worse than random reshuffling, with the gap depending on the ordering.
  • 1 Introduction: The proposed measure quantifies each ordering's suitability and yields convergence bounds tailored to any sequence of dataset permutations.These bounds recover and unify earlier results for incremental gradient descent and random reshuffling.
  • 1 Introduction: 14 percent higher accuracy than random reshuffling is achieved in certain scenarios by a greedy algorithm that selects training orders using the proposed measure.The method searches for orders that minimize the measure and is demonstrated on CIFAR10 image classification.
  • 1 Introduction: Two-level shuffling first orders higher-level functions and then shuffles their lower-level component functions, benefiting theory and practice when data has multiple abstraction levels.The framework targets settings such as federated learning, where each function may represent a worker or another larger data entity.
  • 1 Introduction: The contributions unify order-specific convergence analysis, provide a practical greedy ordering method, and establish benefits of structured random order selection.The structured selection samples permutations from a limited set with a prescribed structure rather than choosing uniformly from all permutations.

2 Related Works

Prior work analyzes permutation-based optimization under progressively broader assumptions, including convexity, smoothness, and non-convexity. Related directions also study adversarial ordering, subset selection, and extensions of reshuffling theory.

  • 2 Related Works: Some work studies how ordering changes training robustness or speed, including loss-based selection and adversarially chosen orders.The paper also notes simultaneous work deriving order-dependent bounds and finding good orders in practice.
  • 2 Related Works: Prior analyses derive convergence bounds for random reshuffling and incremental gradient methods, with rates depending on convexity, smoothness, and order selection.For smooth non-convex objectives, cited results include O(1/(N^1/3 T^2/3)) for reshuffling and O(1/T^2/3) for worst-case incremental ordering.
  • 2 Related Works: Extending variance-reduced stochastic methods and random reshuffling to order-specific convergence bounds remains future work.Related bounds also cover non-convex components and impose additional assumptions such as bounded parameters or Lipschitz Hessians.
  • 2 Related Works: Importance sampling reduces computation by using a subset of data, while curriculum learning begins with easy samples before introducing the full dataset.The present framework mainly studies complete dataset traversal but can accommodate subsets under suitable assumptions.

3 Order-Dependent Convergence Bound

The paper develops an epoch-based framework whose convergence bounds depend on the selected ordering sequence, covering permutations, repeated or omitted functions, and noisy gradient access. A sequence-heterogeneity measure quantifies order effects, recovers RR and IG bounds, and supports convergence analysis for structured or subsampled data.

  • Setup: The framework permits noisy individual-function gradients, assuming zero-mean bounded-variance oracle noise, while modeling functions at data-point, augmentation, class, or worker levels.The functions are assumed L-smooth, and higher-level functions may require noisy approximations computed from constituent data points.
  • Epoch-Based Gradient Descent: Epoch-based gradient descent unifies random reshuffling, incremental gradient descent, SGD, and broader update sequences within one epoch-wise template.Each epoch selects a sequence of function indices; sequences may be permutations, combinations of permutations, or more general selections satisfying bounded sample bias.
  • Quantifying Order Effects: The proposed sequence-heterogeneity quantity σ⋆ measures how the chosen order affects convergence speed under bounded sequence heterogeneity.The analysis allows expectations over randomly selected sequences and extends previous heterogeneity assumptions through a more general order-dependent formulation.
  • Main Results: Under Assumptions 1–4 and a step-size restriction, Theorem 1 gives an order-specific convergence bound for the generalized algorithm.The theorem accommodates oracle noise, bounded sample bias, and positive sequence-heterogeneity parameters, with its proof extending prior random-reshuffling analysis.
  • Recovering Existing Bounds: Specializing the measure and bound recovers convergence results for random reshuffling and incremental gradient descent, while the same framework also recovers SGD results.The paper uses σ⋆ = M⋆ = 0 for the single-function SGD formulation and identifies a trade-off between sampling with replacement and permutation-based methods.
  • Discussion: Assumption 3 can justify convergence for data subsets, including curriculum-style schemes, but the paper leaves deeper sub-sampling analysis for future work.The main focus remains iterating dataset permutations at each epoch.

4 Finding Good Permutations

The paper shows that convergence can vary substantially with the chosen order and proposes a greedy procedure for finding orders with low σ⋆ during training.

  • 4.1 Effectiveness of Choosing the Right Order: The order can change the convergence speed by up to a factor of n^2 under Assumption 5.The framework relates order quality to σ⋆, with σ⋆ bounded below by a quantity on the order of σ^2.
  • 4.1 Effectiveness of Choosing the Right Order: An order with smaller σ⋆ can yield a strictly better convergence bound than random reshuffling in the constructed example.
  • 4.2 Algorithm for Finding Good Permutations: The greedy method chooses each next function among the remaining functions by minimizing a φ-based criterion at the current epoch parameters.The method queries gradients and builds the order sequentially.
  • 4.2 Algorithm for Finding Good Permutations: On the example functions, the algorithm finds the favorable order by alternating between the two function groups.
  • 4.2 Algorithm for Finding Good Permutations: The proposed ordering procedure is applied to neural-network training on CIFAR10 to evaluate its practical effectiveness.

5 Structured Shuffling

The paper analyzes structured shuffling when functions contain lower-level components, showing that the number of local steps can trade off convergence quality against communication costs.

  • 5.1 Two-Level Shuffling: The framework covers structured orders arising from augmentations, federated workers, labels, and other abstractions in the data.Standard shuffling corresponds to a fully random combined permutation, whereas two-level shuffling preserves hierarchical structure.
  • 5.1 Two-Level Shuffling: Two-level K-shuffling alternates orders of top-level functions with K consecutive updates from each function’s internal sequence.The construction generalizes two-level shuffling and models K local steps when a worker is selected.
  • 5.2 Theoretical Analysis: Choosing K = √m can match simple shuffling’s bound while reducing federated-learning communication costs by √m.
  • 5.2 Theoretical Analysis: When σtop ≫ σlow, K = 1 can improve the bound by a factor of √m, whereas K = m can improve it by a factor of √N when σtop ≪ σlow.In federated learning, these settings correspond respectively to highly heterogeneous and homogeneous worker data.
  • 5.3 Comparing Two-Level Shuffling and Standard Shuffling: Internal SGD sampling has slower decay for lower-level variance, while shuffling permits faster decay of other terms and can be preferable early in training.The paper suggests that combining internal SGD with later shuffling may be beneficial as the learning rate decays.

6 Experiments

Experiments test greedy ordering and two-level shuffling on CIFAR10 and controlled functions, finding gains in structured settings while exposing computational trade-offs.

  • 6.1 Finding Good Orders with Algorithm 2: Same-class batching preserves between-batch variance, unlike standard batching, which reduces it by a factor of τ.This design is used to make order effects more observable after mini-batching.
  • 6.1 Finding Good Orders with Algorithm 2: The experiments use a ResNet-18 on CIFAR10 without batch normalization, trained for 200 epochs with scheduled learning-rate decay.
  • 6.1 Finding Good Orders with Algorithm 2: The Greedy algorithm significantly outperforms RR with same-class batching, while achieving similar accuracy to RR with standard batching.Table 1 reports final test accuracies averaged over three runs.
  • 6.1 Finding Good Orders with Algorithm 2: Updating the greedy order every 10 epochs causes a small accuracy drop but noticeably reduces computation cost.Computing a full gradient is the main source of this cost.
  • 6.2 Two-Level Shuffling: In controlled experiments, two-level shuffling requires fewer steps than simple shuffling as σtop increases.The comparison targets reaching ||x||2 < 0.2 while varying σtop and m with σlow fixed at 10.

7 Future Work

Future work targets the computational cost of selecting good orders, broader evaluation of two-level shuffling, and a remaining gap between lower and upper convergence bounds.

  • 7 Future Work: Running the order-selection algorithm every epoch is costly; reducing this cost while preserving accuracy is an open problem.Running it every few epochs caused only a small accuracy impact, but finding equally accurate efficient methods remains future work.
  • 7 Future Work: The effectiveness of two-level shuffling in additional practical scenarios remains to be explored.
  • 7 Future Work: Theoretical work remains to close the gap between the best lower bound O(1/N^3T^2) and upper bound O(1/N^2T^2) achievable by optimizing order.

8 Conclusion

The paper quantifies how ordering affects gradient-descent convergence, uses that measure to select orders, and shows that structured shuffling can improve performance theoretically and practically.

  • 8 Conclusion: The framework provides convergence bounds tailored to custom orderings and supports algorithms for selecting good orders during training.
  • 8 Conclusion: Structured shuffling, including two-level shuffling, can be beneficial and is shown superior in theoretical and practical settings.

A Proof of Theorem 1

The proof of Theorem 1 bounds the epoch-wise update behavior under noisy component gradients and derives a convergence inequality under a step-size restriction.

  • A Proof of Theorem 1: The proof defines the noisy epoch update and sequence of noises, then bounds the distance between averaged updates and the true gradient.
  • A Proof of Theorem 1: Under Assumption 4 and γ ≤ 1/(2L(n+P)), Lemma 5 supplies a bound used in the theorem proof.
  • A Proof of Theorem 1: The intermediate bound includes terms depending on n, P, M⋆, σ⋆, and ζ, capturing update-gradient, oracle-noise, and heterogeneity contributions.
  • A Proof of Theorem 1: Applying the step-size condition γ < 1/(8L(n+nM⋆+P)) to Lemma 5 yields the key gradient-norm inequality for Theorem 1.
  • A Proof of Theorem 1: Averaging the resulting inequalities over steps and taking expectations produces the theorem's convergence statement, with the learning rate selected using Lemma 17 of [13].

B Proof of Lemma 2

The proof of Lemma 2 introduces separate representations for full, low-level, and top-level permutations, then uses their randomness to derive the required bound.

  • B Proof of Lemma 2: The proof defines r0 and r1 so each full permutation can be represented by its low-level and top-level components.
  • B Proof of Lemma 2: It applies the randomness of rlow and rtop and separates the cases a = 0 and a ≥ 1, using a ≤ m for the final bound.
  • B Proof of Lemma 2: The resulting expression is then written using Assumption 4 to complete the lemma's bound.

D Test Accuracy During Training With and Without Algorithm 2

Figure 2 compares test accuracy during training for random reshuffling and Algorithm 2 using same-class batching, including a slow-update variant.

  • The plot compares test accuracy for random reshuffling and the greedy ordering method, Algorithm 2, with same-class batching.
  • Algorithm 2 clearly outperforms random reshuffling in the comparison.
  • The advantage remains when the order is updated only every 10 epochs, labeled Slow Update.
Loading 2202.01838v1…