Vanilla SGD learns SIM from anisotropic data without explicit covariance estimation.
problem Learning SIM from anisotropic Gaussian inputs.
method Vanilla Stochastic Gradient Descent (SGD) trained on SIM with anisotropic input.
result Vanilla SGD adapts to anisotropic data's covariance structure.
SQuARM-SGD improves decentralized SGD efficiency with momentum.
problem Efficient decentralized training of large-scale models over networks.
method Fixed local SGD steps with Nesterov's momentum, sparsified and quantized updates, locally computed triggering criterion.
result Convergence rate matches vanilla SGD, momentum improves test performance.
Stagewise training strategy is widely used for learning neural networks, which runs a stochastic algorithm (e.g., SGD) starting with a relatively large step size (aka learning rate) and geometrically decreasing the step size after a number of iterations. It has been observed that the stagewise SGD has much faster conve…
PAGE is a simple gradient estimator for nonconvex optimization problems.
problem Nonconvex optimization problems in machine learning.
method PAGE is a probabilistic gradient estimator that uses vanilla SGD with probability and a small adjustment with probability 1-p.
result PAGE achieves optimal convergence rates for nonconvex finite-sum and online problems.
A new SGD variant chooses the sample with lowest loss to make the model more robust to outliers.
problem Outliers can skew the parameters of machine learning models trained via SGD.
method Choose a set of k samples, then select the one with the smallest current loss for update.
result The new method makes SGD more robust for ML problems that are sums of convex losses.
Adaptive optimization methods bias neural network trajectories towards regions of lower local geometry.
problem The success of adaptive optimization methods in neural networks is not fully explained by traditional second-order methods.
method Local trajectory analysis and introduction of a new statistic RextmedextOPT. result Adaptive methods like Adam bias trajectories towards regions of lower local geometry, leading to faster convergence.
Communication bottleneck has been identified as a significant issue in distributed optimization of large-scale learning models. Recently, several approaches to mitigate this problem have been proposed, including different forms of gradient compression or computing local models and mixing them iteratively. In this paper…
Large scale machine learning is increasingly relying on distributed optimization, whereby several machines contribute to the training process of a statistical model. In this work we study the performance of asynchronous, distributed settings, when applying sparsification, a technique used to reduce communication overhe…
Stochastic Gradient Descent (SGD) based training of neural networks with a large learning rate or a small batch-size typically ends in well-generalizing, flat regions of the weight space, as indicated by small eigenvalues of the Hessian of the training loss. However, the curvature along the SGD trajectory is poorly und…
New framework limits SGD for multi-index models, addressing SQ framework shortcomings.
problem Limitations of SGD for multi-index models beyond SQ framework.
method Developed a new non-SQ framework to study SGD limitations for single-index and multi-index models.
result Applies to broad settings and architectures, including neural networks.
MDA optimizer performs similarly to SGD+M in CV and Adam in NLP.
problem Performance degradation due to choosing the wrong optimizer.
method Modernized Dual Averaging (MDA) optimizer, inspired by dual averaging.
result MDA performs as well as SGD+M in CV and as Adam in NLP.
To reduce the long training time of large deep neural network (DNN) models, distributed synchronous stochastic gradient descent (S-SGD) is commonly used on a cluster of workers. However, the speedup brought by multiple workers is limited by the communication overhead. Two approaches, namely pipelining and gradient spar…
New analysis improves sample complexity for vanilla policy gradient methods.
problem Improving sample complexity guarantees for vanilla policy gradient methods.
method Adapting tools from SGD analysis to policy gradient methods, with smoothness and gradient approximation assumptions.
result Established improved sample complexity bounds for convergence and global optimum.
New bounds for shallow neural networks with deterministic parameters.
problem Developing generalisation bounds for shallow neural networks.
method PAC-Bayesian theory applied to shallow neural networks with deterministic parameters.
result Empirical non-vacuous bounds for shallow neural networks trained with vanilla SGD.
Neural networks learn the support of the target function through SGD's implicit regularization effect.
problem Learning the support of the target function in neural networks.
method Investigation of mini-batch SGD's ability to learn the support in the first layer of a neural network.
result Mini-batch SGD effectively learns the support in the first layer by shrinking irrelevant weights, while vanilla GD requires an explicit regularization term.
The paper proves D-SGD's stability and generalization bound, highlighting the importance of communication topology.
problem The stability and generalization of decentralized stochastic gradient descent (D-SGD).
method Theoretical analysis of D-SGD's stability and generalization bound, considering spectral gap and communication topology.
result D-SGD's generalization bound is positively correlated with the spectral gap of the communication topology.
Momentum SGD fails to track nonstationary optima due to drift amplification.
problem Tracking nonstationary optima in stochastic optimization.
method Theoretical analysis of SGD and momentum variants under strong convexity and smoothness.
result Momentum incurs a drift-amplification penalty that diverges as the momentum parameter approaches 1, leading to systematic lag.
A new method improves training speed and robustness for deep learning models.
problem Training deep learning models with heavy-tailed gradient noise.
method Per-sample gradient clipping combined with SGD.
result PS-Clip-SGD achieves optimal convergence rates and high-probability guarantees.
This paper studies the problem of error-runtime trade-off, typically encountered in decentralized training based on stochastic gradient descent (SGD) using a given network. While a denser (sparser) network topology results in faster (slower) error convergence in terms of iterations, it incurs more (less) communication …
New method trains deep networks robustly without adaptive methods.
problem Training deep networks with robustness and efficiency.
method Scale invariant architecture + SGD + weight decay + gradient clipping.
result SGD can achieve similar performance to adaptive methods like Adam.
Variance reduced stochastic gradient (SGD) methods converge significantly faster than the vanilla SGD counterpart. However, these methods are not very practical on large scale problems, as they either i) require frequent passes over the full data to recompute gradients---without making any progress during this time (li…
Fault-tolerant federated learning for non-uniform data.
problem Faulty workers corrupting data in federated learning.
method Fault-resilient proximal gradient (FRPG) algorithm with Nesterov's acceleration and local FRPG for reduced communication.
result FRPG and LFRPG converge faster than robust stochastic aggregation.
SGD methods fail to converge to global minimizers in deep neural networks with ReLU activation.
problem Failure of SGD methods to converge to global minimizers in deep neural networks.
method Stochastic Gradient Descent (SGD) and its variants like Adam, RMSProp, etc.
result SGD methods fail to converge to global minimizers with high probability in deep neural networks with ReLU activation.
Study on rich regime training in deep learning, finding active parameters in bottom layers.
problem Understanding the practical success of deep learning models.
method Empirical study on rich regime training with benchmark datasets, re-initialization analysis, and probabilistic Layer-Wise Sparse SGD.
result Probabilistic Layer-Wise Sparse SGD matches vanilla SGD's generalization performance with improved efficiency.
Recurrent Neural Networks (RNNs) are among the most popular models in sequential data analysis. Yet, in the foundational PAC learning language, what concept class can it learn? Moreover, how can the same recurrent unit simultaneously learn functions from different input tokens to different output tokens, without affect…
Huge scale machine learning problems are nowadays tackled by distributed optimization algorithms, i.e. algorithms that leverage the compute power of many devices for training. The communication overhead is a key bottleneck that hinders perfect scalability. Various recent works proposed to use quantization or sparsifica…
MoE outperforms vanilla networks in detecting latent cluster structures in regression tasks.
problem Detecting latent cluster structures in regression tasks with gradient-based learning.
method Theoretical analysis of Mixture of Experts (MoE) using stochastic gradient descent (SGD).
result MoE can successfully divide the problem into subproblems, allowing each expert to recover simpler functions corresponding to individual clusters.
The paper analyzes Adam and SGD in nonstationary optimization, revealing tradeoffs between noise and drift.
problem Analyzing Adam and SGD in nonstationary optimization problems.
method Theoretical analysis of Adam and SGD under non-stationary stochastic objectives, separating two regimes.
result Characterizes the tradeoff between noise and drift in Adam and SGD, revealing when adaptive step-sizing is beneficial or harmful.
New algorithm resists Byzantine attacks in distributed SGD for heterogeneous data.
problem Byzantine attacks in distributed SGD for heterogeneous data.
method Polynomial-time outlier-filtering for robust mean estimation, new matrix concentration result.
result Tolerates up to 25% Byzantine workers and achieves optimal convergence rates.
Distributed stochastic gradient descent~(DSGD) has been widely used for optimizing large-scale machine learning models, including both convex and non-convex models. With the rapid growth of model size, huge communication cost has been the bottleneck of traditional DSGD. Recently, many communication compression methods …
In this paper, we explore techniques centered around periodic sampling of model weights that provide convergence improvements on gradient update methods (vanilla \acs{SGD}, Momentum, Adam) for a variety of vision problems (classification, detection, segmentation). Importantly, our algorithms provide better, faster and …
Adaptive gradient approaches that automatically adjust the learning rate on a per-feature basis have been very popular for training deep networks. This rich class of algorithms includes Adagrad, RMSprop, Adam, and recent extensions. All these algorithms have adopted diagonal matrix adaptation, due to the prohibitive co…
In this paper, we propose a StochAstic Recursive grAdient algoritHm (SARAH), as well as its practical variant SARAH+, as a novel approach to the finite-sum minimization problems. Different from the vanilla SGD and other modern stochastic methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple recursive framewor…
Last-iterate guarantees for learning in co-coercive games under noisy feedback.
problem Learning in co-coercive games with noisy feedback.
method Vanilla stochastic gradient descent with a new noise model.
result Last-iterate bound of order O(log(t)/t1/3) for co-coercive games. Momentum affects optimization differently at small vs large batch sizes near instability.
problem Understanding how momentum impacts optimization near the edge of stability.
method Demonstrated through batch-size dependent behavior of SGD with momentum.
result Momentum operates in two distinct regimes: amplifying stochastic fluctuations at small batch sizes and stabilizing at large batch sizes.
Adam optimizer converges to zeros of a new vector field, not just gradient zeros.
problem Prove convergence rates for Adam optimizer in simple quadratic optimization problems.
method Introduced Adam vector field to analyze Adam optimizer's convergence.
result Established optimal convergence rates for Adam optimizer.
This paper is concerned with sequential filtering based stochastic optimization (FSO) approaches that leverage a probabilistic perspective to implement the incremental proximity method (IPM). The present FSO methods are derived based on the Kalman filter (KF) and the extended KF (EKF). In contrast with typical methods …
Paper analyzes CLT for TTSA with Markovian noise, broadening its applications.
problem Analyzing asymptotic behavior of TTSA under Markovian noise.
method Central Limit Theorem applied to TTSA with Markovian noise.
result Uncovered coupled dynamics of TTSA influenced by Markov chain.
Stochastic gradient descent (\textsc{Sgd}) methods are the most powerful optimization tools in training machine learning and deep learning models. Moreover, acceleration (a.k.a. momentum) methods and diagonal scaling (a.k.a. adaptive gradient) methods are the two main techniques to improve the slow convergence of \text…
Study on dynamics of non-linear autoencoders learning principal components.
problem Technical difficulty in studying non-linear autoencoders due to non-trivial correlations.
method Derive asymptotically exact equations for SGD training of shallow, non-linear autoencoders.
result Autoencoders learn principal components sequentially and tie weights are ineffective.
New algorithm improves OT map estimation for semi-discrete settings.
problem Improving estimation of OT maps in semi-discrete settings.
method Stochastic Gradient Descent with adaptive entropic regularization and averaging acceleration.
result Achieves nearly minimax rate of O(t−1) for OT map estimation. Optimal hedging strategies for exotic options using vanilla options.
problem Hedging exotic options with illiquid vanilla options.
method Simple approximations and variational techniques in a market model and stochastic volatility model framework.
result Optimal Delta and Vega hedging strategies can be computed easily.
This paper proves SGD converges to global minimum for over-parameterized ReLU networks.
problem Theoretical understanding of implicit neural networks is limited.
method Gradient flow analysis of ReLU activated implicit neural networks.
result Randomly initialized gradient descent converges to global minimum at a linear rate for square loss function in over-parameterized ReLU networks.
Vanilla GANs are connected to Wasserstein distance for better understanding.
problem Understanding the statistical properties of Vanilla GANs.
method Connecting Vanilla GANs to Wasserstein distance and proving an oracle inequality.
result An oracle inequality for Vanilla GANs in Wasserstein distance is obtained.
ICA reveals deep learning's feature learning mechanisms from non-Gaussian data.
problem Understanding feature learning from non-Gaussian inputs in deep neural networks.
method Investigates ICA and SGD on synthetic and real data.
result FastICA requires n≳d4 samples for single non-Gaussian direction recovery, while SGD outperforms and optimised SGD reaches n≳d2. Rescaled ASGD optimizes distributed learning under heterogeneous data.
problem Vanilla ASGD biases towards a frequency-weighted average of local objectives.
method Rescale worker stepsizes by their computation times.
result Rescaled ASGD converges to the correct global objective in fixed-computation model.
We introduce Parseval networks, a form of deep neural networks in which the Lipschitz constant of linear, convolutional and aggregation layers is constrained to be smaller than 1. Parseval networks are empirically and theoretically motivated by an analysis of the robustness of the predictions made by deep neural networ…
This paper uses basket option formulas to price vanilla options with discrete dividends.
problem Pricing vanilla options on stocks with discrete cash dividends.
method Uses existing basket option formulas for European options on a single asset with cash dividends in the piecewise lognormal model.
result Explains the use of basket option formulas for a specific problem in the piecewise lognormal model.