acceptodds
Withdrawn from ICLR 2027

Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Shuffling strategies for stochastic gradient descent (SGD), including incremental gradient, shuffle-once, and random reshuffling, are supported by rigorous convergence analyses for arbitrary within-epoch permutations. In particular, random reshuffling is known to improve optimization constants relative to cyclic and shuffle-once schemes. However, existing theory offers limited guidance on how to design new data-ordering schemes that further improve optimization constants or stability beyond random reshuffling. In this paper, we design a pipeline using a large language model (LLM)-guided program evolution framework to discover an effective shuffling rule for without-replacement SGD. Abstracting from this instance, we identify two fundamental structural components: block reshuffling and paired reversal. We analyze these components separately and show that block reshuffling strictly reduces prefix-gradient variance constants within the unified shuffling framework, yielding provable improvements over random reshuffling under mild conditions. Separately, we show that paired reversal symmetrizes the epoch map and cancels the leading order-dependent second-order term, reducing order sensitivity from quadratic to cubic in the step size. Numerical experiments with the discovered algorithm validate the theory and demonstrate consistent gains over standard shuffling schemes across convex and nonconvex benchmarks.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
LLM-guided program evolution, shuffling, optimization

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_A6bNOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper uses an LLM-guided program evolution pipeline (OpenEvolve with Phi-4) to discover a data-ordering rule for without-replacement SGD, called APR. The authors then isolate two components of this rule, block reshuffling and paired reversal, and study them separately. They claim that block reshuffling reduces the variance constants of prefix gradient sums compared to random reshuffling, and that paired reversal cancels the order-dependent second-order term of the epoch map. Experiments on small convex problems and MLPs on MNIST/FashionMNIST compare APR with standard shuffling schemes.

Critical strengths
  1. Studying structured data orderings beyond random reshuffling is a relevant direction.
Critical weaknesses
  1. The purpose of the work is unclear.

The main algorithmic contribution, APR, is obtained by an LLM-guided search, but the discovered components are already known (see Weaknesses 2 and 5), and the search itself is not analyzed: there are no details on the search budget, the number of candidates, or the prompts, and no comparison with simple baselines such as random search over the same program space. It is therefore unclear what the LLM-guided discovery contributes. At the same time, the theory does not analyze APR itself (its adaptive switching is not studied at all), and the theory for its components is either incorrect or known. As a result, the paper offers neither a new algorithm with guarantees nor new insight into data ordering.

  1. The theoretical results are known or incorrect.

The variance result for random reshuffling (Lemma A.1, Proposition A.2) is the classic sampling-without-replacement identity from Mishchenko et al. (2020). Proposition A.3 applies the same identity to block means, and Lemma 3.1 is the law of total variance. The conclusion that block reshuffling "strictly reduces" the variance constants rests on comparing σblk2\sigma^2_{\rm blk} with σind2\sigma^2_{\rm ind} directly, which ignores that a block contains bb samples. At an equal number of processed samples, the prefix variance of block reshuffling relative to random reshuffling is about bb. Block reshuffling is therefore better only if σblk2<σind2/b\sigma^2_{\rm blk}<\sigma^2_{\rm ind}/b, i.e., when blocks are internally heterogeneous. In the "locally coherent" regime invoked by the authors, σblk2≈σind2\sigma^2_{\rm blk}\approx\sigma^2_{\rm ind} and block reshuffling is up to bb times worse than random reshuffling. A simple sanity check shows the issue: for b=nb=n (incremental gradient), σblk2=0\sigma^2_{\rm blk}=0, yet incremental gradient is known to be worse than random reshuffling. Well-designed orderings that do improve on random reshuffling, such as GraB (Lu et al., NeurIPS 2022), are not discussed.

  1. The bounded gradient assumption is too strong.

Assumption (9) requires ∣∣∇fi(x)∣∣≤G||\nabla f_i(x)||\le G for all xx. This is incompatible with strongly convex or quadratic objectives (Nguyen et al., ICML 2018), including the authors' own examples in Propositions 3.5 and 3.7 and the least-squares problems in the experiments. Modern analyses of shuffling methods avoid this assumption (e.g., Mishchenko et al., 2020), so results relying on it are of limited value.

  1. There are no convergence guarantees.

Despite the claim of "provable improvements over random reshuffling", the paper contains no convergence theorem for block reshuffling, paired reversal, or APR. The results concern variance constants and the one-epoch map; no rate is derived, and the claimed improvements are never connected to convergence. For comparison, recent work already obtains convergence guarantees with O(γ3)O(\gamma^3) bias for constant stepsize SGD with random reshuffling combined with Richardson–Romberg extrapolation (Emmanouilidis et al., ICLR 2026), which also averages runs over the same permutation; the present one-epoch statement is weaker and is not connected to such guarantees.

  1. The paired reversal technique is known, and the analysis does not match the algorithm.

Reversing the permutation in the next epoch is the FlipFlop scheme of Rajput, Lee & Papailiopoulos (ICLR 2022), which already provides convergence rates showing improvements over random reshuffling, shuffle-once, and incremental gradient on quadratics. This work is not cited, and the claim that these components "have not been previously formalized" is incorrect. Moreover, the expansion in Lemma 3.2 is standard, and Theorem 3.3 analyzes the average of two epoch maps started from the same point, which is neither what FlipFlop does (composition of epochs) nor what APR does. APR applies the reversal every third epoch to a newly sampled permutation, so no pairs of a permutation and its reverse occur at all. Finally, the O(γ3)O(\gamma^3) bound improves on the Θ(γ2)\Theta(\gamma^2) one only when γnL≪1\gamma nL\ll1, i.e., in the regime where, according to the authors' own Figure 1c, all schemes are indistinguishable.

  1. The experiments are weak.

The problems are very small (boston, diabetes, breast_cancer, digits, a9a, california, and MLPs on MNIST/FashionMNIST). The only metric is the best-so-far training loss; no test metrics are reported. Differences are typically in the third or fourth digit, with overlapping standard deviations, and on MNIST all methods reach the same value. Neural networks are trained with Adam, whereas the theory concerns SGD with per-sample steps; the experiments use mini-batches. There are no ablations isolating block reshuffling or reversal, so the theory for the components is not tested. FlipFlop and GraB are not included as baselines. APR was selected for its performance on the benchmark datasets, apparently the same ones used for evaluation, with no held-out tasks. The blocks are contiguous segments of the original dataset order, which, as discussed above, determines whether block reshuffling helps or hurts; this order is neither controlled nor reported.

Questions for authors

See Weaknesses

Reviewer_24vkOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This work proposes new ways of shuffling the data in random reshuffling methods. In particular, this paper suggests block reshuffling, where the reshuffling is applied to block-partitioned dataset, rather than allowing the order of the individual datapoints to be permuted. Some additional tricks, such as order reversal and even-odd interleaving, are also mentioned.

Critical strengths

A novel shuffling method is proposed, with some empirical results in favor of the claim.

Critical weaknesses

It is very difficult to understand what the main point of the paper is. The title is already quite misleading; what is "learned" exactly? The authors say that the LLM-guided program evolution framework is used, but without much description on how it was used and how one can reproduce the procedure. Also, it is unclear why LLMs or program evolution frameworks should have been used in the first place; the proposed method involves very basic permutations only.

The theoretical analyses are also weak, and are overclaimed in some places. In line 140, it is said that "...can be analyzed using existing unified shuffling theory", but this is not necessarily the case, as block shuffling induces dependencies between πe\pi_e and πe+1\pi_{e+1} which existing theories do not cover. Section 3.1 explains nothing about the actual method proposed; we are not evaluating gi(w)g_i(w) at fixed ww, and this is exactly where the difficulties arise in the theoretical analyses in stochastic methods with reshuffling.
The reversal of the permutation was already considered under the name of flip-flop shuffling (Rajput et al., 2022; Chae et al., 2024), and the fact that the stochastic error term is reduced into the order of O(γ3)O(\gamma^3) from O(γ2)O(\gamma^2) by that approach has already been established by Chae et al. (2024) in a more general setting. Moreover, the advantages of order reversal are claimed through Tˉπ\bar{T}_\pi, which is never actually used in the proposed algorithm.

 

Rajput, Lee, and Papailiopoulos, Permutation-based SGD: Is random optimal?, ICLR 2022

Chae, Yun, and Kim, Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements, NeurIPS 2024

Questions for authors
  1. What was the search space of the evolution framework? In section D it is mentioned that the search space was restricted to "permutations that can be produced in O(n)O(n) time", but exactly which permutations fall into that category? If the set of such permutations consists of block permutations, reversals, and even-odd intertwining (and the compositions of those), the permutation rules are not actually "learned"; it is just doing what it can do.

  2. As mentioned in the Critical Weaknesses section above, the theoretical analyses, as far as I am concerned, explain almost nothing about the proposed method, and the novelty also seems quite weak. Can the authors elaborate further on this?

Reviewer_GRXoOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper uses offline LLM-guided search to develop APR, a data-ordering rule that switches between block and random reshuffling based on training progress, with periodic sequence transformations. It analyzes block-gradient variance and paired reversal, and evaluates the discovered rule on convex optimization tasks and small neural networks. No LLM is used during training.

Critical strengths
  1. The paired-reversal analysis provides a useful explanation of how averaging forward and reverse epoch updates cancels leading order-dependent effects.
  2. APR is inexpensive to apply and improves training loss over random reshuffling in most reported settings. These results make structured data ordering worth investigating further.
Critical weaknesses
  1. The block-variance argument does not establish the claimed advantage over random reshuffling. Lower variance of block averages is insufficient when both methods are compared after processing the same number of samples. The formulas in Appendix A have different sampling factors, and the paper needs an explicit condition under which block reshuffling actually improves the relevant prefix variance.
  2. The reversal theory analyzes a different procedure from APR. It averages forward and reverse trajectories from the same starting point, while APR periodically reverses a single ordering. The experiments lack component ablations that would show whether reversal, block structure, or loss-based switching explains the gains. Consequently, the results do not yet validate the proposed theoretical explanation.
Questions for authors
  1. Under what precise conditions does block reshuffling reduce prefix variance at an equal sample budget, and do those conditions hold in the experiments?
  2. What evidence connects the paired-reversal result to APR's actual reversal rule? Can the authors isolate the effects of reversal and loss-based switching relative to plain block reshuffling?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.