Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting
This work addresses a theoretical bottleneck in optimization algorithms for machine learning, offering incremental improvements in complexity analysis for researchers in the field.
The paper tackles the problem of improving gradient complexity in variance reduction methods by proposing Adjusted Shuffling SARAH, which integrates shuffling techniques with dynamic gradient weighting to achieve the best-known gradient complexity for shuffling methods in strongly convex settings, narrowing the gap between uniform sampling and shuffling.
In this paper, we propose Adjusted Shuffling SARAH, a novel algorithm that integrates shuffling techniques with the well-known variance-reduced algorithm SARAH while dynamically adjusting the stochastic gradient weights in each update to enhance exploration. Our method achieves the best-known gradient complexity for shuffling variance reduction methods in a strongly convex setting. This result applies to any shuffling technique, which narrows the gap in the complexity analysis of variance reduction methods between uniform sampling and shuffling data. Furthermore, we introduce Inexact Adjusted Reshuffling SARAH, an inexact variant of Adjusted Shuffling SARAH that eliminates the need for full-batch gradient computations. This algorithm retains the same linear convergence rate as Adjusted Shuffling SARAH while showing an advantage in total complexity when the sample size is very large.