Georgia Institute of Technology College of Sciences

First-order (a.k.a. subgradient) methods in convex optimization are a popular choice when facing extremely large-scale problems, where medium accuracy solutions suffice. The limits of performance of first-order methods can be partially understood under the lens of black box oracle complexity. In this talk I will present some of the limitations of worst-case black box oracle complexity, and I will show two recent extensions of the theory: First, we extend the notion of oracle compexity to the distributional setting, where complexity is measured as the worst average running time of (deterministic) algorithms against a distribution of instances. In this model, the distribution of instances is part of the input to the algorithm, and thus algorithms can potentially exploit this to accelerate their running time. However, we will show that for nonsmooth convex optimization distributional lower bounds coincide to worst-case complexity up to a constant factor, and thus all notions of complexity collapse; we can further extend these lower bounds to prove high running time with high probability (this is joint work with Sebastian Pokutta and Gabor Braun). Second, we extend the worst-case lower bounds for smooth convex optimization to non-Euclidean settings. Our construction mimics the classical proof for the nonsmooth case (based on piecewise-linear functions), but with a local smoothening of the instances. We establish a general lower bound for a wide class of finite dimensional Banach spaces, and then apply the results to \ell^p spaces, for p\in[2,\infty]. A further reduction will allow us to extend the lower bounds to p\in[1,2). As consequences, we prove the near-optimality of the Frank-Wolfe algorithm for the box and the spectral norm ball; and we prove near-optimality of function classes that contain the standard convex relaxation for the sparse recovery problem (this is joint work with Arkadi Nemirovski).

This is not a mathematics talk but it is a talk for mathematicians. Too often, we think of historical mathematicians as only names assigned to theorems. With vignettes and anecdotes, I'll convince you they were also human beings and that, as the Chinese say, "May you live in interesting times" really is a curse.

We'll prove the simplest case of Hirzebruch's signature theorem, which relates the first Pontryagin number of a smooth 4-manifold to the signature of its intersection form. If time permits, we'll discuss the more general case of 4k-manifolds. The result is relevant to Prof. Margalit's ongoing course on characteristic classes of surface bundles.

We conclude the proof of the linearization theorem for fibered holomorphic maps by showing that the iteration scheme we proposed converges. If time allows, we will comment on related work by Mario Ponce and generalizations of the theorem for fibered holomorphic maps in higher dimensions.