Without-Replacement Sampling for Stochastic Gradient Methods

By Ohad Shamir. 2016

134 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Measuring the Effects of Data Parallelism on Neural Network Training (2018, methodology): “that we call a stochastic gradient. In our larger-scale experiments, when we sample subsequent batches B t, we actually follow the common practice of cycling through permutations of the training set (Shamir, 2016). Variants of SGD commonly used with neural networks include SGD with momentum (Polyak,”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “, Algorithm 4) by following similar analysis in [55] (for generalized linear models) or in [56] (for convex and smooth loss functions).”
Demystifying Parallel and Distributed Deep Learning (2018, background): “ 7: w(t+1)←w mb + ∆w ▷ Store parameters 8: end for epochs[83,250]. As opposed to the original SGD, shuffle-based processing entails without-replacement sampling. Nevertheless, minibatch SGD was proven[213] to provide similar convergence guarantees. 2.2 Unsupervised and Reinforcement Learning Two oth”
Efficient Decentralized Deep Learning by Dynamic Model Averaging (2018, neutral): “We investigate synchronization operators that aggregate models by computing their average [25, 24, 33, 45, 44], i.”
SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, background): “The first set of results in this direction are given by Safran and Shamir [17], who develop a lower bound of Ω (1/(nK)2 + 1/nK3) for RANDOMSHUFFLE under the assumption of constant step size.”
SGD without Replacement: Sharper Rates for General Smooth Convex Functions (2019, methodology): “Furthermore, even in setting of (Shamir, 2016), our result improves upon best known bounds when nK > κ(2).”
Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement (2017, methodology): “Since Shamir (2016) assumes that the concatenation of {Sj}j∈[m] forms a random permutation of {fi}[N ], his method essentially performs the iterative update of SVRG by sampling from {fi}[N ] without replacement.”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, background): “As each component function f i ( · ) may have diﬀer-ent degrees of smoothness, to select the random index i sk from a non-uniform distribution is a much better choice than simple uniform random sampling [4], as well as without-replacement sampling vs. with-replacement sampling [45].”
Closing the convergence gap of SGD without replacement (2020, unknown): “Our upper bound, Theorem 1 Õ ( 1 T 2 + n(2) T 3 ) F is strongly convex and a sum of n smooth functions Lower bound, Safran & Shamir (2019) Ω ( 1 T 2 + n(2) T 3 )”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, background): “The authors can only show convergence to a neighborhood of an optimal solution or a stationary point as in (Shamir, 2016).”
Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis (2017, unknown): “A second line of results for distributed estimation under convexity assumptions consider iterative algorithms that perform multiple communication rounds and are based on distributed gradient computations (some examples include [23, 27, 14, 22, 10, 18]).”
FairBatch: Batch Selection for Model Fairness (2020, methodology): “The batch selection literature for SGD focuses on analyzing the effect of batch sizes (Keskar et al., 2017; Masters and Luschi, 2018) and various sampling techniques (Shamir, 2016; G ¨ urb ¨ uzbalaban et al., 2019).”
Permutation-Based SGD: Is Random Optimal? (2021, methodology): “Speeding up convergence by combining without replacement sampling with other techniques like variance reduction (Shamir, 2016; Ying et al., 2020) and momentum (Tran et al., 2020) has also received some attention.”
Differentially Private Federated Learning: An Information-Theoretic Perspective (2021, background): “To overcome this, we generalize the results on without-replacement SGD [20], proving a similar upper bound on the convergence rate.”
On the Intrinsic Privacy of Stochastic Gradient Descent (2019, background): “Bsamples. We consider the typical scenario where the dataset is shufﬂed in each epoch, and batches are selected sequentially without replacement. This approach provides better convergence properties (Shamir, 2016; Jain et al., 2019), however we expect other variants to share the variability we study”
Distributed learning with compressed gradients (2018, background): “…GD becomes signiﬁcant, and one typically resorts to stochastic gradient descent (where the gradient is evaluated at a single randomly chosen data point in every iteration) or leverages on data-parallelism by distributing the gradient computations on multiple parallel machines; see e.g. in, [1–4].”