- 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
- Studying structured data orderings beyond random reshuffling is a relevant direction.
Critical weaknesses
- 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.
- 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 with directly, which ignores that a block contains samples. At an equal number of processed samples, the prefix variance of block reshuffling relative to random reshuffling is about . Block reshuffling is therefore better only if , i.e., when blocks are internally heterogeneous. In the "locally coherent" regime invoked by the authors, and block reshuffling is up to times worse than random reshuffling. A simple sanity check shows the issue: for (incremental gradient), , 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.
- The bounded gradient assumption is too strong.
Assumption (9) requires for all . 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.
- 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 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.
- 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 bound improves on the one only when , i.e., in the regime where, according to the authors' own Figure 1c, all schemes are indistinguishable.
- 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