Seminars and Colloquia by Series

Wednesday, September 19, 2018 - 13:55 , Location: Skiles 005 , Marcin Bownik , University of Oregon , Organizer: Shahaf Nitzan
Wednesday, September 19, 2018 - 12:55 , Location: Skiles 006 , Han Huang , University of Michigan , , Organizer: Konstantin Tikhomirov
Friday, September 14, 2018 - 15:00 , Location: Skiles 005 , Ernie Croot , Georgia Tech , Organizer: Lutz Warnke
Friday, September 14, 2018 - 14:00 , Location: Skiles 005 , Ethan Cotterill , Universidade Federal Fluminense , Organizer: Yoav Len
Friday, September 14, 2018 - 13:05 , Location: Skiles 005 , Matthew Fahrbach , CS, Georgia Tech , , Organizer: He Guo
As a generalization of many classic problems in combinatorial optimization, submodular optimization has found a wide range of applications in machine learning (e.g., in feature engineering and active learning).  For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel.  While low adaptivity is ideal, it is not sufficient for a (distributed) algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive.  Motivated by such applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint $k$ that achieves a $(1-1/e-\varepsilon)$-approximation in expectation.  Furthermore, this algorithm runs in $O(\log(n))$ adaptive rounds and makes $O(n)$ calls to the function evaluation oracle in expectation.  All three of these guarantees are optimal, and the query complexity is substantially less than in previous works.  Finally, to show the generality of our simple algorithm and techniques, we extend our results to the submodular cover problem.
Wednesday, September 12, 2018 - 13:55 , Location: Skiles 006 , Galyna Livshyts , Georgia Institute of Technology , , Organizer: Galyna Livshyts
Koldobsky showed that for an arbitrary measure on R^n, the measure of the largest section of a symmetric convex body can be estimated from below by 1/sqrt{n}, in with the appropriate scaling. He conjectured that a much better result must hold, however it was recemtly shown by Koldobsky and Klartag that 1/sqrt{n} is best possible, up to a logarithmic error. In this talk we will discuss how to remove the said logarithmic error and obtain the sharp estimate from below for Koldobsky's slicing problem. The method shall be based on a "random rounding" method of discretizing the unit sphere. Further, this method may be effectively applied to estimating the smallest singular value of random matrices under minimal assumptions; a brief outline shall be mentioned (but most of it shall be saved for another talk). This is a joint work with Bo'az Klartag. 
Wednesday, September 12, 2018 - 12:55 , Location: Skiles 006 , Santosh Vempala , Georgia Institute of technology , , Organizer: Galyna Livshyts
The concentration of Lipschitz functions around their expectation is a classical topic and continues to be very active. In these talks, we will discuss some recent progress in detail, including:  A tight log-Sobolev inequality for isotropic logconcave densities A unified and improved large deviation inequality for convex bodies An extension of the above to Lipschitz functions (generalizing the Euclidean squared distance)The main technique of proof is a simple iteration (equivalently, a Martingale process) that gradually transforms any density into one with a Gaussian factor, for which isoperimetric inequalities are considerably easier to establish.  (Warning: the talk will involve elementary calculus on the board, sometimes at an excruciatingly slow pace).   Joint work with Yin Tat Lee. 
Friday, September 7, 2018 - 15:00 , Location: Skiles 005 , Joshua Cooper , University of South Carolina , Organizer: Lutz Warnke
Thursday, September 6, 2018 - 15:05 , Location: Skiles 006 , Sara van de Geer , ETH Zurich , Organizer: Mayya Zhilova
The seminar will be the third lecture of the TRIAD Distinguished Lecture Series by Prof. Sara van de Geer. For further information please see
Wednesday, September 5, 2018 - 13:55 , Location: Skiles 006 , Ionel Popescu , Georgia Institute of Technology , Organizer: Galyna Livshyts