- You are here:
- GT Home
- Home
- News & Events

Series: Analysis Seminar

Series: High Dimensional Seminar

Series: Combinatorics Seminar

Series: Algebra Seminar

Series: ACO Student Seminar

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.

Series: Analysis Seminar

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.

Series: High Dimensional Seminar

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.

Series: Combinatorics Seminar

Series: Stochastics Seminar

The seminar will be the third lecture of the TRIAD Distinguished Lecture Series by Prof. Sara van de Geer. For further information please see http://math.gatech.edu/events/triad-distinguished-lecture-series-sara-van-de-geer-0

Series: Analysis Seminar

TBA