More Like this

1. Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions

   Raj, Anant; Zhu, Lingjiong; Gurbuzbalaban, Mert; Simsekli, Umut (October 2023, Proceedings of Machine Learning Research)

   Heavy-tail phenomena in stochastic gradient de- scent (SGD) have been reported in several empirical studies. Experimental evidence in previous works suggests a strong interplay between the heaviness of the tails and generalization behavior of SGD. To address this empirical phenom- ena theoretically, several works have made strong topological and statistical assumptions to link the generalization error to heavy tails. Very recently, new generalization bounds have been proven, indicating a non-monotonic relationship between the generalization error and heavy tails, which is more pertinent to the reported empirical observations. While these bounds do not require additional topological assumptions given that SGD can be modeled using a heavy-tailed stochastic differential equation (SDE), they can only apply to simple quadratic problems. In this paper, we build on this line of research and develop generalization bounds for a more general class of objective functions, which includes non-convex functions as well. Our approach is based on developing Wasserstein stability bounds for heavy- tailed SDEs and their discretizations, which we then convert to generalization bounds. Our results do not require any nontrivial assumptions; yet, they shed more light to the empirical observations, thanks to the generality of the loss functions. 

   more » « less
2. SGD and Hogwild! Convergence Without the Bounded Gradients Assumption

   Nguyen, Lam M.; Nguyen, Phuong Ha; Dijk, Marten van; Richtárik, Peter; Scheinberg, Katya; Takáč, Martin (January 2018, Proceedings of Machine Learning Research)

   Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep neural networks. The classical analysis of convergence of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is always violated for cases where the objective function is strongly convex. In (Bottou et al.,2016) a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. Here we show that for stochastic problems arising in machine learning such bound always holds. Moreover, we propose an alternative convergence analysis of SGD with diminishing learning rate regime, which is results in more relaxed conditions that those in (Bottou et al.,2016). We then move on the asynchronous parallel setting, and prove convergence of the Hogwild! algorithm in the same regime, obtaining the first convergence results for this method in the case of diminished learning rate. 

   more » « less
3. Particle Deposition Driven by Evaporation in Membrane Pores and Droplets

   https://doi.org/10.1137/22S1532937  

   Jiang, Juliet; Zhang, Ruohan; Jeong, Dominic (January 2023, SIAM Undergraduate Research Online)

   This paper investigates particle deposition driven by fluid evaporation in a single pore channel representative of those found in porous membranes. A moving boundary problem for the 2D heat equation is coupled with an evolution equation for the pore radius, and describes the physical processes of fluid evaporation, diffusion of the particle concentration, and deposition on the pore channel wall. Furthermore, a stochastic differential equation (SDE) approach based on a Brownian motion particle-level description of diffusion is used as a similar phenomenological representation to the partial differential equation (PDE) model. Sensitivity analysis reveals trends in dominant model parameters such as evaporation rate, deposition rate, the volume scaling coefficient, and investigates the monotonicity of concentration. Evaluations of the asymptotically reduced model and the SDE model against the 2D PDE model are done in terms of the pore radius and solute concentration over time. For further exploration, we apply the model to a 2D droplet as well with both deterministic and stochastic approaches. 

   more » « less
4. Stochastic Gradient Descent in Correlated Settings: A Study on Gaussian Processes

   Chen, H; Zheng, L; al Kontar, R; Raskutti, G. (January 2020, Advances in neural information processing systems)

   null (Ed.)

   Stochastic gradient descent (SGD) and its variants have established themselves as the go-to algorithms for large-scale machine learning problems with independent samples due to their generalization performance and intrinsic computational advantage. However, the fact that the stochastic gradient is a biased estimator of the full gradient with correlated samples has led to the lack of theoretical understanding of how SGD behaves under correlated settings and hindered its use in such cases. In this paper, we focus on the Gaussian process (GP) and take a step forward towards breaking the barrier by proving minibatch SGD converges to a critical point of the full loss function, and recovers model hyperparameters with rate O(1/K) up to a statistical error term depending on the minibatch size. Numerical studies on both simulated and real datasets demonstrate that minibatch SGD has better generalization over state-of-the-art GP methods while reducing the computational burden and opening a new, previously unexplored, data size regime for GPs. 

   more » « less
5. On the insufficiency of existing momentum schemes for Stochastic Optimization

   Kidambi, Rahul; Netrapalli, Praneeth; and Jain, Prateek; Kakade, Sham M. (January 2018, International Conference on Learning Representations)

   Momentum based stochastic gradient methods such as heavy ball (HB) and Nesterov's accelerated gradient descent (NAG) method are widely used in practice for training deep networks and other supervised learning models, as they often provide significant improvements over stochastic gradient descent (SGD). Rigorously speaking, fast gradient methods have provable improvements over gradient descent only for the deterministic case, where the gradients are exact. In the stochastic case, the popular explanations for their wide applicability is that when these fast gradient methods are applied in the stochastic case, they partially mimic their exact gradient counterparts, resulting in some practical gain. This work provides a counterpoint to this belief by proving that there exist simple problem instances where these methods cannot outperform SGD despite the best setting of its parameters. These negative problem instances are, in an informal sense, generic; they do not look like carefully constructed pathological instances. These results suggest (along with empirical evidence) that HB or NAG's practical performance gains are a by-product of minibatching. Furthermore, this work provides a viable (and provable) alternative, which, on the same set of problem instances, significantly improves over HB, NAG, and SGD's performance. This algorithm, referred to as Accelerated Stochastic Gradient Descent (ASGD), is a simple to implement stochastic algorithm, based on a relatively less popular variant of Nesterov's Acceleration. Extensive empirical results in this paper show that ASGD has performance gains over HB, NAG, and SGD. The code for implementing the ASGD Algorithm can be found at https://github.com/rahulkidambi/AccSGD. 

   more » « less