Stochastic gradient and stochastic gradient MCMC methods for Bayesian learning and non-convex optimization: centralized and decentralized settings
Creators: name: Hu, Yuanhan
Publisher: name: No Publisher Supplied
Year: 2023

description: There are two parts in this thesis. Part I (Chapter I-IV) concerns stochastic gradient and stochastic gradient Markov Chain Monte Carlo (MCMC) methods for large-scale optimization and Bayesian inference problems. We consider the ``centralized setting" when the data is available at a centralized location and the model is trained at the same location. We focus on methods that rely on stochastic unbiased estimates of the gradients. Such a setting arises frequently in many machine learning scenarios such as deep learning or more broadly in risk minimization when the gradients are estimated from randomly sampled data points for scalability purposes to large datasets. Chapters I, II, III, and IV constitute Part I of this thesis. In Chapter I, we develop fractional moment-preserving initialization schemes for deep learning networks. The traditional approach to initialization in deep neural networks (DNNs) is to sample the network weights randomly for preserving the variance of post-activations. On the other hand, several studies show that during the training process, the distribution of stochastic gradients can be heavy-tailed especially for small batch sizes. In this case, weights and therefore post-activations can be modeled with a heavy-tailed distribution that has an infinite variance but a finite fractional moment of order $s$ with $s&lt;2$. Motivated by this fact, we develop initialization schemes for deep neural networks that can provably preserve any given moment of order $sin (0,2]$ over the post-activations for a classof activation functions and show that they can lead to better performance in practice for some problems. Chapter I is based on our conference publication [Gurbuzbalaban and Hu, 2021]. In Chapter II, we propose the ``Non-reversible Stochastic Gradient Langevin Dynamics"(NSGLD) for non-convex optimization. Stochastic Gradient Langevin Dynamics (SGLD) is a powerful algorithm for optimizing a non-convex objective, where a controlled and properly scaled Gaussian noise is added to the stochastic gradients to steer the iterates towards a global minimum. SGDL is based on the overdamped Langevin diffusion which is reversible in time. We get a non-reversible diffusion that converges to the same stationary distribution with a faster convergence rate by adding an anti-symmetric matrix to the drift term of the overdamped Langevin diffusion. We study the NSGLD based on the discretization of this non-reversible Langevin diffusion. Our results lead to non-asymptotic guarantees for both population and empirical risk minimization problems. Chapter II is based on the work [Hu et al., 2020] which appeared earlier online. In Chapter III, we focus on the stochastic gradient Markov Chain Monte Carlomethods for the Bayesian sampling problems under the centralized setting. We consider the constrained sampling problem where the goal is to sample from a target distribution that is constrained on a convex body. Motivated by penalty methods from continuous optimization, we propose penalty-based Stochastic Gradient Langevin Dynamics (PSGLD) and penalty-based Stochastic Gradient Hamiltonian Monte Carlo (PSGHMC) methods for constrained sampling that convert the constrained sampling problem into an unconstrained sampling problem by introducing a penalty function for constraint violations. We provide finite-time performance bounds, iteration complexity results, and numerical results in this chapter. Chapter III is based on our work [Gurbuzbalaban et al., 2022a]. In Chapter IV, we consider the different stepsizes schedules in the SGD algorithm. Cyclic and randomized stepsizes are widely used in the deep learning practice and can often outperform standard stepsize choices such as constant stepsize in SGD. We consider a general class of Markovian stepsizes for learning, which contain i.i.d. random stepsize, cyclic stepsize as well as constant stepsize as special cases. Motivated by the literature which shows that the heaviness of the tails (measured by the so-called "tail-index") in the SGD iterates is correlated with generalization, we study the tail-index and provide a number of theoretical results that demonstrate how the tail-index varies on the stepsize scheduling. Our results bring a new understanding of the benefits of cyclic and randomized stepsizes compared to constant stepsize in terms of the tail behavior. We illustrate our theory on linear regression experiments and show through deep learning experiments that Markovian stepsizes can achieve even a heavier tail and be a viable alternative to cyclic and i.i.d. randomized stepsize schedules. Chapter IV is based on the work [Gurbuzbalaban et al., 2023] which is also available online. In Part I, we consider the case where all data and model is available in a centralizednode. However, there has been exponential growth in the amount of data collected and stored in recent decades. Due to the size of modern datasets, it is often impossible or impractical to gather all data for centralized processing in practice. Besides the size of modern datasets, other concerns such as communication constraints among data-collecting devices and privacy constraints about sharing data will also make centralized settings infeasible in many situations. As a result, decentralized machine learning algorithms have received a lot of attention for such applications where agents can collaboratively learn a model without sharing their own data but sharing only their local models with their immediate neighbors. In Part II of this thesis which consists of Chapters V and VI, we investigate stochastic gradient and stochastic gradient MCMC algorithms in the decentralized setting. In Chapter V, we study two algorithms: Decentralized Stochastic Gradient Langevin Dynamics(DE-SGLD) and Decentralized Stochastic Gradient Hamiltonian Monte Carlo (SGHMC), which are adaptations of SGLD and SGHMC methods that allow scaleable Bayesian inference in the decentralized setting for large datasets. We show that when the posterior distribution is strongly log-concave and smooth, the iterates of these algorithms converge linearly to a neighborhood of the target distribution in the 2-Wasserstein distance if their parameters are selected appropriately. We also showcase the efficiency of our algorithms on several Bayesian learning tasks. Chapter V is based on the work [Gurbuzbalaban et al., 2021] which was published in the Journal of Machine Learning Research. Chapter VI concerns heavy tails in decentralized stochastic optimization. In particular, recent theoretical studies have shown that heavy-tails can emerge in stochastic optimizationdue to multiplicative noise. While these studies have uncovered several interesting phenomena, they consider conventional stochastic optimization problems, which exclude decentralized settings that naturally arise in modern machine learning applications. In Chapter VI, we study the emergence of heavy-tails in decentralized stochastic gradient descent (DE-SGD), and investigate the effect of decentralization on the tail behavior. We provide theoretical and empirical results showing that DE-SGD has heavier tails than centralized SGD and discuss the implications of these results to machine learning practice. Chapter VI is based on the work [Gurbuzbalaban et al., 2022]. We note that Part I and Part II use different notations, and the notations used in each part are summarized in Table 0.1 and Table 4.2 for the reader's convenience.