<html><body><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000"><div data-marker="__QUOTED_TEXT__"><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000"><div>Cyril Zhang will present his generals exam Thursday, May 25, 2017 at 3pm in CS 402<br></div><div><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000;"><div><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000;"><div><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000;"><div><div style="font-family: garamond,new york,times,serif; font-size: 12pt; color: #000000;"><div><br>The members of his committee are: Elad Hazan (adviser), Sanjeev Arora, and Matt Weinberg<br><br>Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below.</div></div></div></div></div></div><div style="color: #000000; font-family: 'Times New Roman'; font-size: 14.16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;"><br></span></div><div style="color: #000000; font-family: 'Times New Roman'; font-size: 14.16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;">Topic: Two Views of Non-Convex Regret Minimization</span><br style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;"><br style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;">Abstract: I will discuss the problem of efficient online regret minimization with non-convex loss functions. Two distinct (yet pleasingly nebulously connected) approaches are considered; both results are j</span><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;">oint work with </span><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;">Karan Singh and</span><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;"> Prof. Elad Hazan.</span></div><div style="color: #000000; font-family: 'Times New Roman'; font-size: 14.16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;"><br></span></div><div style="color: #000000; font-family: 'Times New Roman'; font-size: 14.16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;">In the first part of my talk, I will present a new framework for general online non-convex optimization (ONCO). I will introduce the desiderata of such a framework, showing how we must avert issues of computational intractability by defining a suitable notion of regret. I will introduce our time-smoothed regret measure, and justify it with tight upper and lower bounds, along with reductions to the full-information and stochastic offline cases. Finally, I will show some extensions and applications. Primarily, our framework gives rise to a new solution concept in repeated games; I will discuss some natural settings in which our algorithms are practical and give provable guarantees for learning in games.</span></div><div style="color: #000000; font-family: 'Times New Roman'; font-size: 14.16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;"><br></span></div><div style="color: #000000; font-family: 'Times New Roman'; font-size: 14.16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial;"><span style="color: #000000; font-family: garamond, 'new york', times, serif; font-size: 16px;">In the second part, I will present a second approach, in which one leverages the structure of an ONCO problem to make it amenable to the tools of online convex optimization (OCO). We consider the non-convex problem of maximum-likelihood online prediction of linear dynamical systems (LDS). Relying upon the spectral theory of Hankel matrices, we formulate an approximate convex relaxation to this problem. This results in a black-box reduction to OCO, from which we derive a simple, practical method for predicting sequences arising from an LDS.</span></div><div style="color: #000000; font-family: 'Times New Roman'; font-size: 14.16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: #ffffff; text-decoration-style: initial; text-decoration-color: initial;"><br></div><br>Books:<br><br>- Introduction to Online Convex Optimization. Elad Hazan.<br>- Understanding Machine Learning. Shai Shalev-Shwartz and Shai Ben-David.<br><br>Papers:<br><br>- Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming. Saeed Ghadimi and Guanghui Lan.<br>- Cubic regularization of Newton method and its global performance. Yurii Nesterov and B.T. Polyak.<br>- The Multiplicative Weights Update Method: A Meta-Algorithm and Applications. Sanjeev Arora, Elad Hazan, Satyen Kale.<br>- Online Convex Programming and Generalized Infinitesimal Gradient Ascent. Martin Zinkevich.<br>- Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. John Duchi, Elad Hazan, and Yoram Singer.<br>- Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. Rie Johnson and Tong Zhang.<br>- Efficient algorithms for online decision problems. Adam Kalai and Santosh Vempala.<br>- Online Linear Optimization via Smoothing. Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari.<br>- Matrix Completion has No Spurious Local Minimum. Rong Ge, Jason D. Lee, and Tengyu Ma.<br>- Gradient Descent Learns Linear Dynamical Systems. Moritz Hardt, Tengyu Ma, and Benjamin Recht.</div></div></div></div><br></div></div></body></html>