<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><span id="docs-internal-guid-de668218-7fff-220a-42c4-c3d01efd7aaf" class=""><div class="" style="font-family: -webkit-standard; line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"></div><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><b class="" style="orphans: 2; widows: 2;"><font size="4" class="">Jason Lee</font></b></div></span><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div class="" style="orphans: 2; widows: 2;"><div class="" style="margin: 0in 0in 0.0001pt;"><i class=""><font size="3" class="">University of Southern California</font></i></div><div class="" style="margin: 0in 0in 0.0001pt;"><div class=""><span class="" style="font-size: 14px;"><i class=""><span class="Apple-tab-span" style="white-space: pre;"> </span></i></span></div></div><div class="" style="margin: 0in 0in 0.0001pt;"><b class=""><font class="" style="font-size: 14px;"><br class=""></font></b></div><div class="" style="margin: 0in 0in 0.0001pt;"><span class=""><b class=""><font class="" size="4">Monday, February 25, 2019 at 10:30 am<br class="">Crerar 390</font></b><br class=""></span></div></div><div class="" style="orphans: 2; widows: 2;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class=""><br class=""></div><div class=""><div class=""><font class="" style="font-size: 15px;"><span class=""><b class="" style="color: rgb(33, 33, 33);">Title: <span class="Apple-tab-span" style="white-space: pre;"> </span></b></span></font><font color="#212121" class=""><span class="" style="font-size: 15px;">On the Foundations of Deep Learning: SGD, Overparametrization, and Generalization</span></font></div><div class="" style="color: rgb(33, 33, 33);"><b class=""><font class="" style="font-size: 15px;"><br class=""></font></b></div><div class="" style="color: rgb(33, 33, 33);"><b class=""><font class="" style="font-size: 15px;">Abstract:</font></b></div><div class=""><font class=""><span class=""><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><div class=""><font class=""><span class=""><span id="docs-internal-guid-bf351367-7fff-5067-8c8e-0130cc54a81c" class=""><div class="" style="line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span class=""><span class="" style="font-size: 15px; white-space: pre-wrap;">We provide new results on the effectiveness of SGD and overparametrization in deep learning.<br class=""><br class="">a) SGD: We show that SGD converges to stationary points for general nonsmooth, nonconvex functions, and that stochastic subgradients can be efficiently computed via Automatic Differentiation. For smooth functions, we show that gradient descent, coordinate descent, ADMM, and many other algorithms, avoid saddle points and converge to local minimizers. For a large family of problems including matrix completion and shallow ReLU networks, this guarantees that gradient descent converges to a global minimum.<br class=""><br class="">b) Overparametrization: We show that gradient descent finds global minimizers of the training loss of overparametrized deep networks in polynomial time. <br class=""><br class="">c) Generalization: For general neural networks, we establish a margin-based theory. The minimizer of the cross-entropy loss with weak regularization is a max-margin predictor, and enjoys stronger generalization guarantees as the amount of overparametrization increases. <br class=""><br class="">d) Algorithmic and Implicit Regularization: We analyze the implicit regularization effects of various optimization algorithms on overparametrized networks. In particular we prove that for least squares with mirror descent, the algorithm converges to the closest solution in terms of the bregman divergence. For linearly separable classification problems, we prove that the steepest descent with respect to a norm solves SVM with respect to the same norm. For over-parametrized non-convex problems such as matrix sensing or neural net with quadratic activation, we prove that gradient descent converges to the minimum nuclear norm solution, which allows for both meaningful optimization and generalization guarantees.<br class=""> <br class=""></span></span></div></span></span><b class="" style="font-size: 15px; color: rgb(33, 33, 33);">Bio:</b></font></div></div></span></font></div><div class=""><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font class=""><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class="">Jason Lee is an assistant professor of Data Sciences and Operations in Marshall School of Business, Computer Science Department (courtesy), and a member of the Machine Learning Center. Previously, he was a postdoc in the Computer Science Department at UC Berkeley working with Michael Jordan, and also collaborated with Ben Recht. Prior to that, he was a PhD student in Computational Mathematical Engineering at Stanford University advised by Trevor Hastie and Jonathan Taylor. He received a BS in Mathematics from Duke University advised by Mauro Maggioni. His research interests are broadly in Statistics (Statistical Learning and High-dimensional Statistics), Machine Learning, and Optimization. </i></span></font><br class=""></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><br class=""></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><b class="">Host: Rebecca Willett</b></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><b class=""><br class=""></b></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><b class="">PDF:</b></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><b class=""><br class=""></b></i></span></font></div><div class="" style="font-variant-ligatures: normal; background-color: rgb(255, 255, 255);"><font color="#222222" class=""><span class="" style="font-size: 15px;"><i class=""><b class=""></b></i></span></font></div></div></div></div></div></div></div></div></div></body></html>