It was love at the nth glance. I can only pinpoint within some epsilon accuracy when this happened. I must say that it took me approximately O(1/epsilon) iterations of personal deliberation to converge to this realization. And even then, with my usual intransigence, I was loath to admit that I had finally fallen irrevocably (I hope) in love. It was only after a colleague brought to my attention how my eyes lit up when this love interest came up in conversation, did I finally let go of the last of my resistance.

Confused? Sorry. Let me start from the beginning.

Last year, during my time at the Science and Engineering Festival in DC, I encountered a middle schooler who couldn’t stop waxing lyrical about the virtues of pi. I didn’t quite understand her fascination with the number pi, but I envied her because she was obviously in love. I was in my third year and I hadn’t yet found that area of Statistics that inspired me to want to immerse myself in it. I was still dabbling in variable selection methods, and though this was an interest of mine, it simply didn’t do it for me. It lacked the excitement and appeal that I craved. The turning point came when I took a class on Artificial Intelligence in the Physics Department of all places. After doing a simulation based on one of my homework assignments, I discovered something that puzzled me. I had noticed that after training my machine learning model using some SGD variant, my test error was appreciably lower than the training error. I went to my advisor to inquire about his thoughts on the matter and that was the beginning of my maddening but altogether glorious relationship with Stochastic Gradient Descent, SGD for short.

Now, a little background. SGD belongs to the family of recursive algorithms known as Stochastic Approximation (SA) algorithms. The first SA algorithm was a result of a partnership between Herbert Robbins and Sutton Monro. Their dream was to find the root of an unknown function expressed as an expected value, given noisy estimates of the function values at different points in the domain. This dream was realized when they deduced that one could start at an arbitrary value in the domain of the function and obtain the next iterate by taking a step in the direction of the negative of the function value. They showed that provided the function is nondecreasing and has a positive gradient at the unique root, and that the step-size satisfies certain requirements, the algorithm will converge to the optimal value.

SGD is used in the field of stochastic optimization, specifically for minimizing convex cost functions for which the analytical form of the gradient is difficult to obtain or computationally expensive to compute. SGD is especially useful when data is not static but rather, streaming in. In this case, noisy estimates of the gradient are obtained using a single observation or a subset of the data. It is also one of the most important methods used in training machine learning models.

Despite its apparent utility, SGD suffers from a sensitivity to the choice of step-size that affects the rate of convergence to a large extent. Since its inception, there have been myriad adaptations of the method to inform the selection of the learning rate to speed up convergence and to modify it to suit specific problems. From Adam and EVE to Pegasos and SAGA, SGD and its many variants are highly suited to solving a wide range of optimization problems.

Although widely used in many different fields, from acoustics to neuroscience, the problem of quantifying the uncertainty around SGD estimates has seen very little work. The goal of my work is, therefore, to explore similarities between the implicit regularization of SGD and classical regularization methods that may give us a deeper understanding of how the algorithm works and enable us to better estimate the variability surrounding SGD iterates.

Even though SGD still frustrates me no end, I still marvel at its versatility and the beauty of its simplicity. Ours is a love-hate relationship, but I’ve heard that those are the best. I hope so!