Multiplicative noise and heavy tails in stochastic optimization

Stochastic optimization is the process of minimizing a deterministic objective function via the simulation of random elements, and it is one of the most successful methods for optimizing complex or unknown objectives. Relatively simple stochastic optimization procedures--in particular, stochastic gradient descent (SGD)--have become the backbone of modern machine learning (ML) [50]. To improve understanding of stochastic optimization in ML, and particularly why SGD and its extensions work so well, recent theoretical work has sought to study its properties and dynamics [47]. Such analyses typically approach the problem through one of two perspectives. The first perspective, an optimization (or quenching) perspective, examines convergence either in expectation [11, 20, 28, 60, 84] or with some positive (high) probability [19, 41, 66, 77] through the lens of a deterministic counterpart. This perspective inherits some limitations of deterministic optimizers, including assumptions (e.g., convexity, Polyak-Łojasiewicz criterion, etc.) that are either not satisfied by state-of-the-art problems, or not strong enough to imply convergence to a quality (e.g., global) optimum. More concerning, however, is the inability to explain what has come to be known as the "generalization gap" phenomenon: increasing stochasticity by reducing batch size appears to improve generalization performance [38, 55]. Empirically, existing strategies do tend to break down for inference tasks when using large batch sizes [27].