{"645841":{"#nid":"645841","#data":{"type":"event","title":"PhD Defense by Tianyi Liu","body":[{"value":"\u003Cp\u003EDear faculty members and fellow students,\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EYou are cordially invited to attend my thesis defense.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThesis Title: Theoretical Analysis of Stochastic Gradient Descent in Stochastic Optimization\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAdvisors:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Enlu Zhou, School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Tuo Zhao, School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECommittee members:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Alexander Shapiro, School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Robert D. Foley, School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Zhengyuan Zhou, Stern School of Business, New York University\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDate and Time: 10:00 am (EST), Friday, April 9th, 2021\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMeeting URL:\u0026nbsp;\u0026nbsp; \u003Ca href=\u0022https:\/\/nam12.safelinks.protection.outlook.com\/?url=https%3A%2F%2Fbluejeans.com%2F287756905\u0026amp;data=04%7C01%7Ctatianna.richardson%40grad.gatech.edu%7Cd790acc29aa546e00e7b08d8f2bc7168%7C482198bbae7b4b258b7a6d7f32faa083%7C0%7C0%7C637526238453774734%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000\u0026amp;sdata=UXgyQCZKB%2FyUYcwlBRcLDM%2BUyahi01lH%2BSXx%2F6B4Vik%3D\u0026amp;reserved=0\u0022\u003Ehttps:\/\/bluejeans.com\/287756905\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMeeting ID:\u0026nbsp; 287 756 905 (BlueJeans)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EStochastic Gradient Descent (SGD) type algorithms have been widely applied to many\u003C\/p\u003E\r\n\r\n\u003Cp\u003Estochastic optimization problems, such as machine learning. Despite its empirical success,\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ethere is still a lack of theoretical understanding of convergence properties of SGD and its\u003C\/p\u003E\r\n\r\n\u003Cp\u003Evariants. The major bottleneck comes from the highly nonconvex optimization landscape\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eand the complicated noise structure. This thesis aims to provide useful insights on the good\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eperformance of SGD type algorithms through theoretical analysis with the help of diffusion\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eapproximation and martingale theory. Specifically, we answer the following questions:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EChapter 1: What is the effect of Momentum in nonconvex optimization? We propose to\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eanalyze the algorithmic behavior of Momentum Stochastic Gradient Descent (MSGD) by\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ediffusion approximation for general nonconvex optimization problems. Our study shows\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ethat the momentum helps escape from saddle points, but hurts the convergence within the\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eneighborhood of optima (if without the step size annealing or momentum annealing). Our\u003C\/p\u003E\r\n\r\n\u003Cp\u003Etheoretical discovery partially corroborates the empirical successes of MSGD in training\u003C\/p\u003E\r\n\r\n\u003Cp\u003Edeep neural networks.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EChapter 2: How does noise in SGD help the algorithm avoid spurious local optima?\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe answer this question through a simple two-layer convolutional neural network model,\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ewhich has a spurious local optimum and a global optimum. Our theory shows that perturbed\u003C\/p\u003E\r\n\r\n\u003Cp\u003Egradient descent and perturbed mini-batch stochastic gradient algorithms in conjunction\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ewith noise annealing is guaranteed to converge to a global optimum in polynomial time\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ewith arbitrary initialization. This implies that the noise enables the algorithm to efficiently\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eescape from the spurious local optimum.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EChapter 3: How does noise in SGD help select optima that have good generalization\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eperformance? We further investigate the role of noise when multiple global optima exist by\u003C\/p\u003E\r\n\r\n\u003Cp\u003Econsidering nonconvex rectangular matrix factorization problem, which has infinitely many\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eglobal minima due to rotation and scaling invariance. Gradient descent (GD) can converge\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eto any optimum, depending on the initialization. In contrast, we show that a perturbed\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eform of GD with an arbitrary initialization converges to a global optimum that is uniquely\u003C\/p\u003E\r\n\r\n\u003Cp\u003Edetermined by the injected noise. Our result implies that the noise imposes implicit bias\u003C\/p\u003E\r\n\r\n\u003Cp\u003Etowards certain optima.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EChapter 4: Does reusing past samples in SGD help improve the efficiency in simulation\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eoptimization? We consider a special type of stochastic optimization problem, simulation\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eoptimization. The main challenge of simulation optimization is the limited simulation\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ebudget because of the high computational cost of simulation experiments. One approach\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eto overcome this challenge is to reuse simulation outputs from previous iterations in the\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ecurrent iteration of the optimization procedure. However, due to the dependence among iterations,\u003C\/p\u003E\r\n\r\n\u003Cp\u003Esimulation replications from different iterations are not independent, which leads\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eto the lack of theoretical justification for the good empirical performance. We fill this gap\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eby theoretically studying the stochastic gradient descent method with reusing past simulation\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ereplications. We show that reusing past replications does not change the convergence\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eof the algorithm, which implies the bias of the gradient estimator is asymptotically negligible.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMoreover, we justify that reusing past replications reduces the variance of gradient\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eestimators around local optima, which implies that the algorithm can achieve faster convergence.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Theoretical Analysis of Stochastic Gradient Descent in Stochastic Optimization"}],"uid":"27707","created_gmt":"2021-03-29 15:28:57","changed_gmt":"2021-03-29 15:28:57","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2021-04-09T11:00:00-04:00","event_time_end":"2021-04-09T13:00:00-04:00","event_time_end_last":"2021-04-09T13:00:00-04:00","gmt_time_start":"2021-04-09 15:00:00","gmt_time_end":"2021-04-09 17:00:00","gmt_time_end_last":"2021-04-09 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}