Georgia Institute of Technology College of Sciences

Accelerated gradient methods play a central role in optimization, achieving the optimal convergence rates in many settings. While many extensions of Nesterov's original acceleration method have been proposed, it is not yet clear what is the natural scope of the acceleration concept. In this work, we study accelerated methods from a continuous-time perspective. We show there is a Bregman Lagrangian functional that generates a large class of accelerated methods in continuous time, including (but not limited to) accelerated gradient descent, its non-Euclidean extension, and accelerated higher-order gradient methods. We show that in continuous time, these accelerated methods correspond to traveling the same curve in spacetime at different speeds. This is in contrast to the family of rescaled gradient flows, which correspond to changing the distance in space. We show how to implement both the rescaled and accelerated gradient methods as algorithms in discrete time with matching convergence rates. These algorithms achieve faster convergence rates for convex optimization under higher-order smoothness assumptions. We will also discuss lower bounds and some open questions. Joint work with Ashia Wilson and Michael Jordan.

In 1973 Erdos asked whether there are n-vertex partial Steiner triple systems with arbitrary high girth and quadratically many triples. (Here girth is defined as the smallest integer g \ge 4 for which some g-element vertex-set contains at least g-2 triples.) We answer this question, by showing existence of approximate Steiner triple systems with arbitrary high girth. More concretely, for any fixed \ell \ge 4 we show that a natural constrained random process typically produces a partial Steiner triple system with (1/6-o(1))n^2 triples and girth larger than \ell. The process iteratively adds random triples subject to the constraint that the girth remains larger than \ell. Our result is best possible up to the o(1)-term, which is a negative power of n. Joint work with Tom Bohman.

Given a finite partially ordered set (poset) of width $w$, Dilworth's theorem gives an existence and minimality of a chain partition of size $w$. First-Fit is an online algorithm for creating a chain partition of a poset. Given a linear ordering of the points of the poset, $v_1, \cdots, v_n$, First-Fit assigns the point $v_i$ to the first available chain in the chain partition of the points $v_1, \cdots, v_{i-1}$. It is a known fact that First-Fit has unbounded performance over the family of finite posets of width 2. We give a complete characterization of the family of finite posets in which First-Fit performs with subexponential efficiency in terms of width. We will also review what is currently known on the family of posets in which First-Fit performs with polynomial efficiency in terms of width. Joint work with Kevin Milans.

Given a convex polytope P, what is the number of integer points in P? This problem is of great interest in combinatorics and discrete geometry, with many important applications ranging from integer programming to statistics. From computational point of view it is hopeless in any dimensions, as the knapsack problem is a special case. Perhaps surprisingly, in bounded dimension the problem becomes tractable. How far can one go? Can one count points in projections of P, finite intersections of such projections, etc? We will survey both classical and recent results on the problem, emphasizing both algorithmic and complexity aspects. Some elegant hardness results will make an appearance in dimension as small as three. If time permits, we will discuss connections to Presburger Arithmetic and decidability problems for irrational polyhedra. Joint work with Danny Nguyen.