Technical Summary: Adjusted Shuffling SARAH

Problem Statement

The paper addresses the finite-sum minimization problem common in machine learning:
$$\min_{w \in \mathbb{R}^d} P(w) := \frac{1}{n} \sum_{i=1}^n f_i(w)$$
where $n$ is the number of data samples and each $f_i$ is a smooth function. While Gradient Descent (GD) offers fast linear convergence, its $O(n)$ per-iteration cost is prohibitive for large-scale datasets. Stochastic Gradient Descent (SGD) reduces this to $O(1)$ but suffers from high variance, necessitating diminishing step sizes and resulting in sub-linear convergence. Variance Reduction (VR) methods like SARAH and SVRG improve convergence rates but typically require computing the full gradient $\nabla P(\tilde{w})$ at the start of every outer loop, maintaining an $O(n)$ bottleneck.

Existing shuffling-based VR methods (e.g., Shuffling SARAH, Shuffling SVRG) attempt to combine the practical efficiency of sampling without replacement (shuffling) with variance reduction. However, current theoretical analyses show that these methods generally retain a linear dependence on the dataset size $n$ in their total complexity (e.g., $O(n\kappa \log(1/\varepsilon))$). This linear scaling limits their efficiency in modern large-scale regimes where $n$ is massive.

Methodology: Adjusted Shuffling SARAH

The authors propose Adjusted Shuffling SARAH, a novel algorithm that integrates shuffling strategies into the recursive SARAH framework. The core innovation is a dynamic weighting mechanism within the inner loop and a dual-mode operational structure.

Algorithm Structure

The algorithm operates in epochs $s = 1, \dots, S$. Within each epoch, it performs an inner loop of size $m$ using a permutation $\pi_s$ of the dataset indices.

1. Initialization: Set $w_0 = \tilde{w}_{s-1}$. Compute a stochastic approximation of the full gradient $v_0$ using a mini-batch of size $m$.
2. Inner Loop Update: For $t = 1, \dots, m$, the gradient estimator is updated recursively:
   $$v_t = \left( \frac{m+1}{m+1-t} \right) \left( \nabla f_{\pi_t^s}(w_t) - \nabla f_{\pi_t^s}(w_{t-1}) \right) + v_{t-1}$$
   The parameter $w_{t+1}$ is updated via $w_{t+1} = w_t - \eta v_t$.
3. Epoch Completion: Set $\tilde{w}_s = w_{m+1}$.

Key Mechanisms

• Dynamic Weighting: Unlike standard SARAH or shuffling SARAH, which use a coefficient of 1, this algorithm multiplies the gradient difference term by $\frac{m+1}{m+1-t}$. As $t \to m$, this coefficient grows, amplifying the contribution of gradient differences near the end of the inner loop. This design ensures that every data point in the permutation contributes equally to the total epoch update, balancing the weights of early and late terms in the permutation.
• Dual Modes:
  • Exact Mode ($m=n$): Uses a full permutation of the dataset. It computes the full gradient (or a full-batch approximation) at the start of the epoch. This mode targets high-precision convergence.
  • Inexact Mode ($m < n$): Uses a random reshuffling of a subset of size $m$. The initial vector $v_0$ is a mini-batch estimator. This mode is designed for scalability in massive datasets.

Theoretical Analysis and Results

The paper provides convergence analysis for both strongly convex and non-convex settings under standard assumptions ($L$-smoothness, $\mu$-strong convexity, and bounded variance).

1. Exact Mode Performance

In the Exact Mode ($m=n$), the algorithm matches the best-known theoretical guarantees for shuffling variance-reduced methods:

• Strongly Convex: Achieves a total complexity of $O(n\kappa \log(1/\varepsilon))$.
• Non-Convex: Achieves a total complexity of $O(nL/\varepsilon^2)$.
  These results confirm that the dynamic weighting does not degrade the convergence rate compared to existing state-of-the-art shuffling VR methods.

2. Inexact Mode Performance (Scalability)

The primary theoretical contribution is the analysis of the Inexact Mode ($m < n$). The authors prove that by carefully choosing the inner loop size $m$, the total complexity can be made independent of the dataset size $n$ when $n$ is sufficiently large.

• Strongly Convex: The total complexity is $O\left( \min\left\{ \frac{\sigma^2}{\mu\varepsilon}, n \right\} \kappa \log\left(\frac{1}{\varepsilon}\right) \right)$. When $n$ is large, the complexity scales as $O\left( \frac{\sigma^2}{\mu\varepsilon} \kappa \log(1/\varepsilon) \right)$, removing the linear dependence on $n$.
• Non-Convex: The total complexity is $O\left( \min\left\{ \frac{\sigma^2 L}{\varepsilon^4}, \frac{nL}{\varepsilon^2} \right\} \right)$. In the large-scale regime, this becomes $O\left( \frac{\sigma^2 L}{\varepsilon^4} \right)$, again independent of $n$.

This represents a significant improvement over existing shuffling VR algorithms, which typically scale linearly with $n$ regardless of the dataset size.

Empirical Validation

The authors evaluated Adjusted Shuffling SARAH on binary classification tasks using logistic regression with $l_2$-regularization on three datasets: w8a, ijcnn1, and fashion-mnist.

• Comparison: The method was compared against Random Reshuffling (RR) SVRG and RR SARAH.
• Results: The algorithm demonstrated competitive performance. In some datasets (e.g., w8a), it initially converged slower than competitors but achieved the smallest gradient norm and superior long-term convergence after approximately 20 epochs. In other datasets, it maintained comparable performance to the baselines. The results validate that the dynamic weighting mechanism does not hinder practical performance while offering theoretical scalability benefits.

Significance and Claims

The paper claims that Adjusted Shuffling SARAH is the first shuffling variance-reduced algorithm to achieve a total complexity independent of the dataset size $n$ in the large-scale regime.

• Scalability: By decoupling computational complexity from $n$ in the Inexact Mode, the method offers a strictly superior alternative for massive datasets compared to existing shuffling methods.
• Theoretical Balance: The algorithm successfully balances the trade-off between convergence accuracy (Exact Mode) and computational scalability (Inexact Mode).
• Limitations: The authors modestly note that while their Exact Mode matches the best-known rates for shuffling algorithms, it remains an open question whether shuffling methods can reach the optimal rates achieved by standard uniform-sampling VR methods (like standard SVRG/SARAH) under standard assumptions.

In summary, the work advances the complexity analysis of shuffling methods by introducing a dynamic weighting scheme that enables a scalable, $n$-independent complexity regime without sacrificing the theoretical guarantees of the exact regime.