A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
SGD without replacement decouples into curvature-following and flatness-regularizing steps.
Stochastic gradient descent without replacement sampling is widely used in practice for model training. However, the vast majority of SGD analyses assumes data is sampled with replacement, and when the function minimized is strongly convex, an rate can be established when SGD is ru…
Differential privacy is a useful tool to build machine learning models which do not release too much information about the training data. We study the Rényi differential privacy of stochastic gradient descent when each training example is sampled without replacement (also known as cyclic SGD). Cyclic SGD is typically f…
We study stochastic gradient descent {\em without replacement} (\sgdwor) for smooth convex functions. \sgdwor is widely observed to converge faster than true \sgd where each sample is drawn independently {\em with replacement} \cite{bottou2009curiously} and hence, is more popular in practice. But it's convergence prope…
Stochastic Gradient Descent underperforms on some problems, contrary to expectations.
New convergence bounds for shuffling-based SGD methods in distributed learning.
While machine learning has achieved remarkable results in a wide variety of domains, the training of models often requires large datasets that may need to be collected from different individuals. As sensitive information may be contained in the individual's dataset, sharing training data may lead to severe privacy conc…
A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to our knowledge) non-asymptotic solution to this problem, which shows that after a "reasonable" numbe…
Optimal SGD rates achieved with shuffling, covering non-convex and convex cases.
The paper analyzes the variance of different shuffling methods in stochastic gradient descent.
Stochastic Gradient Descent (SGD) is a central tool in machine learning. We prove that SGD converges to zero loss, even with a fixed (non-vanishing) learning rate - in the special case of homogeneous linear classifiers with smooth monotone loss functions, optimized on linearly separable data. Previous works assumed eit…
Improved rates for continual learning using SGD and last-iterate analysis.
New bounds for SGD show improved performance in various settings.
We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algor…
New insights into privacy guarantees for subsampled mechanisms under composition.
New method shows hidden state can significantly improve differential privacy in SGD.
SMD outperforms SGD in over-parametrized linear models for certain data distributions.
Random permutations can offer faster convergence than with-replacement sampling for some functions.
Improved Local SGD convergence for general convex objectives with bounded second-order heterogeneity.
New analysis for black-box learning without gradients, improving generalization bounds.
Cheap methods improve uncertainty in SGD solutions.
Smoothed SGD improves quantile estimation without crossing curves.
Mixed-precision CA-SGD for generalized linear models on GPUs
We investigate the dynamical and convergent properties of stochastic gradient descent (SGD) applied to Deep Neural Networks (DNNs). Characterizing the relation between learning rate, batch size and the properties of the final minima, such as width or generalization, remains an open question. In order to tackle this pro…
Minibatch SGD outperforms Local SGD in heterogeneous distributed learning.
Sampling is a fundamental technique, and sampling without replacement is often desirable when duplicate samples are not beneficial. Within machine learning, sampling is useful for generating diverse outputs from a trained model. We present an elegant procedure for sampling without replacement from a broad class of rand…
Paper explores whether gradient normalization can replace clipping for SGD in heavy-tailed noise.
IntSGD compresses SGD gradients without floats, converging as SGD.
Stochastic gradient descent (SGD) is a popular and efficient method with wide applications in training deep neural nets and other nonconvex models. While the behavior of SGD is well understood in the convex learning setting, the existing theoretical results for SGD applied to nonconvex objective functions are far from …
Artificial intelligence is revolutionizing our lives at an ever increasing pace. At the heart of this revolution is the recent advancements in deep neural networks (DNN), learning to perform sophisticated, high-level tasks. However, training DNNs requires massive amounts of data and is very computationally intensive. G…
The Lookahead optimizer improves SGD's performance and generalization without restrictive assumptions.
New stability bounds for SGD on nonsmooth convex losses.
Stochastic gradient descent (SGD) with constant momentum and its variants such as Adam are the optimization algorithms of choice for training deep neural networks (DNNs). Since DNN training is incredibly computationally expensive, there is great interest in speeding up the convergence. Nesterov accelerated gradient (NA…
Paper analyzes how EMA improves SGD in linear regression.
New proof shows D-SGD and SAM are equivalent, revealing advantages of decentralization.
New method improves scalability of SGD for large datasets.
Sampling without replacement speeds up optimization in minimax problems.
Large batch training with DP-SGD reduces model performance due to implicit bias.
We propose a general yet simple theorem describing the convergence of SGD under the arbitrary sampling paradigm. Our theorem describes the convergence of an infinite array of variants of SGD, each of which is associated with a specific probability law governing the data selection rule used to form mini-batches. This is…
The well-known Gumbel-Max trick for sampling from a categorical distribution can be extended to sample elements without replacement. We show how to implicitly apply this 'Gumbel-Top-' trick on a factorized distribution over sequences, allowing to draw exact samples without replacement using a Stochastic Beam Sea…
Due to its efficiency and ease to implement, stochastic gradient descent (SGD) has been widely used in machine learning. In particular, SGD is one of the most popular optimization methods for distributed learning. Recently, quantized SGD (QSGD), which adopts quantization to reduce the communication cost in SGD-based di…
AdaGrad-Norm achieves optimal convergence rates for non-convex objectives without tuning.
The minimization of the loss function is of paramount importance in deep neural networks. On the other hand, many popular optimization algorithms have been shown to correspond to some evolution equation of gradient flow type. Inspired by the numerical schemes used for general evolution equations we introduce a second o…
We analyze the variance of stochastic gradients along negative curvature directions in certain non-convex machine learning models and show that stochastic gradients exhibit a strong component along these directions. Furthermore, we show that - contrary to the case of isotropic noise - this variance is proportional to t…
Privacy-preserving SGD with heavy-tailed noise achieves differential privacy guarantees.
DP-SGD can update fewer coordinates while maintaining privacy.
When using stochastic gradient descent to solve large-scale machine learning problems, a common practice of data processing is to shuffle the training data, partition the data across multiple machines if needed, and then perform several epochs of training on the re-shuffled (either locally or globally) data. The above …
New PAC-Bayes bounds use Wasserstein distances to improve generalization.