Georgia Institute of Technology College of Sciences

We present randomized algorithms for sampling the standard Gaussian distribution restricted to a convex set and for estimating the Gaussian measure of a convex set, in the general membership oracle model. The complexity of the integration algorithm is O*(n^3) while the complexity of the sampling algorithm is O*(n^3) for the first sample and O*(n^2) for every subsequent sample. These bounds improve on the corresponding state-of-the-art by a factor of n. Our improvement comes from several aspects: better isoperimetry, smoother annealing, avoiding transformation to isotropic position and the use of the ``speedy walk" in the analysis.

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).

Recently, Bilu and Linial formalized an implicit assumption often made when choosing a clustering objective: that the optimum clustering to the objective should be preserved under small multiplicative perturbations to distances between points. They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor O(\sqrt{n})) perturbations, and subsequently Awasthi et al. considered center-based objectives, giving algorithms for instances resilient to O(1) factor perturbations. In this talk, for center-based objectives, we present an algorithm that can optimally cluster instances resilient to (1+\sqrt{2})-factor perturbations, solving an open problem of Awasthi et al. For k-median, a center-based objective of special interest, we additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small fraction of the points after perturbation. We give the first bounds known for k-median under this more realistic and more general assumption. We also provide positive results for min-sum clustering which is a generally much harder objective than center-based objectives. Our algorithms are based on new linkage criteria that may be of independent interest.

Although production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. In this work, we take a significant step towards understanding computational aspects of markets with production. We first define the notion of separable, piecewise-linear concave (SPLC) production by analogy with SPLC utility functions. We then obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria for Arrow-Debreu markets with SPLC utilities and SPLC production, and we give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. Experiments show that our algorithm runs fast on randomly chosen examples, and unlike previous approaches, it does not suffer from issues of numerical instability. Additionally, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Based on a joint work with Vijay V. Vazirani.