We present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max Cut, Max 2-SAT, and Max DiCut, and derive new algorithms that are competitive with the best known results. We further show the versatility of our approach by presenting simple and natural variants of it, and we numerically demonstrate that they exhibit nearly optimal approximation guarantees for some problems.

We present a blended conditional gradient algorithm for minimizing a smooth convex function over a polytope P, that combines gradient projection steps with conditional gradient steps, achieving linear convergence for strongly convex functions. It does not make use of away steps or pairwise steps, but retains all favorable properties of conditional gradient algorithms, most notably not requiring projections onto P and maintaining iterates as sparse convex combinations of extreme points. The algorithm decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the efficient lazified conditional gradient algorithms of Braun et al. [2017]. We also present a streamlined algorithm for the special case in which P is a probability simplex, called simplex gradient descent.

Fair allocation of resources has deep roots in early philosophy, and has been broadly studied in political science, economic theory, operations research, and networking. Over the past decades, an axiomatic approach to fair resource allocation has led to the general acceptance of a class of alpha-fair utility functions parametrized by a single non-negative inequality aversion parameter alpha. In theoretical computer science, the most well-studied examples are linear utilities (alpha = 0), proportionally fair or Nash utilities (alpha = 1), and max-min fair utilities (alpha = infinity). Maximization of alpha-fair utility functions over convex sets leads to alpha-fair allocation vectors, whose fairness properties are well-studied and axiomatically justified. For most applications, a natural feasible set is a packing polytope, and we refer to the corresponding problem as the alpha-fair packing. The special case of alpha = 0 is known as the packing linear program, which has been widely studied in theoretical computer science due to the phenomenon of width-independence. Namely, for packing linear programs it is possible to obtain first-order methods whose running times scale poly-logarithmically with the constraint matrix width -- the maximum ratio of its non-zero elements. By contrast, this is not possible for general linear programming. In this talk, I will present distributed and width-independent first-order methods for solving general alpha-fair packing problems and their minimization counterparts -- alpha-fair covering problems. The convergence times (number of distributed iterations) of these algorithms scale as Õ(1/eps^2) and Õ(1/eps), which greatly improves upon Õ(1/eps^5) and Õ(1/eps^4) previously known only for the alpha-fair packing problems. I will further discuss how special, local, structure of these problems relates to the phenomenon of width-independence, and conclude with a few open problems. Joint work with Maryam Fazel and Lorenzo Orecchia.

We consider the $k$-server problem on trees and HSTs. We give an algorithm based on Bregman projections, whose competitive ratio matches those in recent results of Bubeck et al. (STOC 2018). Joint work with Niv Buchbinder, Marco Molinaro, and Seffi Naor.

A selector maps a set (in some set system) to an element in that set. In a metric space, Lipschitz selection is the problem of finding a selector that is Lipschitz with respect to the Hausdorff distance. A classical result is the existence of a Lipschitz selector for convex sets in Euclidean space. In this talk we will prove an *online* version of this classical result. This resolves the 1991 Friedman-Linial conjecture on convex body chasing.

Joint work with Yin Tat Lee, Yuanzhi Li, and Mark Sellke.

We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton's method and linear conjugate gradient, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm closely tracks Newton-conjugate gradient procedures developed in the 1980s, but includes enhancements that allow worst-case complexity results to be proved for convergence to points that satisfy approximate first-order and second-order optimality conditions. Knowledge of such parameters as a bound on the Hessian norm is not required. The complexity results match the best known results in the literature for second-order methods. The talk represents joint work with Clement Royer and Michael O'Neill.

Given labeled points in a high-dimensional vector space, we seek a low-dimensional subspace such that projecting onto this subspace maintains some prescribed distance between points of differing labels. Intended applications include compressive classification. Taking inspiration from large margin nearest neighbor classification, this paper introduces a semidefinite relaxation of this problem. Unlike its predecessors, this relaxation is amenable to theoretical analysis, allowing us to provably recover a planted projection operator from the data. This is joint work with Dustin Mixon and Culver McWhirter.

In this talk, I will explain how to solve linear programs with accuracy epsilon in time n^{omega+o(1)} log(1/epsilon) where omega~2.3728639 is the current matrix multiplication constant. This hits a natural barrier of solving linear programs since linear systems is a special case of linear programs and solving linear systems require time n^omega currently. Joint work with Michael Cohen and Zhao Song.

In the Directed Steiner Tree (DST) problem we are given an n-vertex directed edge-weighted graph, a root r, and a collection of k terminal nodes. Our goal is to find a minimum-cost arborescence that contains a directed path from r to every terminal. We present an O(log^2 k/log log{k})-approximation algorithm for DST that runs in quasi-polynomial-time. By adjusting the parameters in the hardness result of Halperin and Krauthgamer [STOC'03], we show the matching lower bound of Omega(log^2{k}/log log{k}) for the class of quasi-polynomial-time algorithms. This is the first improvement on the DST problem since the classical quasi-polynomial-time O(log^3 k) approximation algorithm by Charikar et al. [SODA'98; J. Algorithms'99] (The paper erroneously claims an O(log^2k) approximation due to a mistake in prior work.) Our approach is based on two main ingredients. First, we derive an approximation preserving reduction to the Label-Consistent Subtree (LCST) problem. The LCST instance has quasi-polynomial size and logarithmic height. We remark that, in contrast, Zelikovsky's heigh-reduction theorem used in all prior work on DST achieves a reduction to a tree instance of the related Group Steiner Tree (GST) problem of similar height, however losing a logarithmic factor in the approximation ratio. Our second ingredient is an LP-rounding algorithm to approximately solve LCST instances, which is inspired by the framework developed by Rothvoss [Preprint, 2011]. We consider a Sherali-Adams lifting of a proper LP relaxation of LCST. Our rounding algorithm proceeds level by level from the root to the leaves, rounding and conditioning each time on a proper subset of label variables. A small enough (namely, polylogarithmic) number of Sherali-Adams lifting levels is sufficient to condition up to the leaves.

This is a joint work with Fabrizio Grandoni and Shi Li.

We study the problem of graph clustering where the goal is to partition a graph into clusters, i.e. disjoint subsets of vertices, such that each cluster is well connected internally while sparsely connected to the rest of the graph. In particular, we use a natural bicriteria notion motivated by Kannan, Vempala, and Vetta [KVV00] which we refer to as expander decomposition. Expander decomposition has become one of the building blocks in the design of fast graph algorithms, most notably in the nearly linear time Laplacian solver by Spielman and Teng [ST04], and it also has wide applications in practice. For the global version, given graph $G$ and parameter $\phi$, we design $\tilde{O}{m/\phi)$ time algorithm to partition the vertices into clusters such that each cluster induces a subgraph of conductance at least $\phi$, while only a $\tilde{O}(\phi)$ fraction of the edges in the graph have endpoints across different clusters. This is the first nearly linear time algorithm when $\phi$ is at least $1/ polylog m$, which is the case in most practical settings and theoretical applications, and only relies on simple and basic flow-based techniques. Previous results either take $m^{1+o(1)}$ time (e.g. [NS17, Wul17]), or attain nearly linear time but with a weaker expansion guarantee where each output cluster is guaranteed to be contained inside some unknown expander (e.g. [ST13, ACL06]). In the local version of the problem, we are given a seed node $s$, and want to find a good cluster contatining $s$ (if there exists one) in time proportional to the size of the (unkown) cluster. While flow and probability mass diffusion (or more generally, spectral methods) have a long history of competing to provide good graph decomposition, local methods are predominantly based on diffusion. We design the first primarily flow-based local method for locating low conductance cuts, and it has exhibited improved theoretical and empirical behavior over classical diffusion methods, e.g. PageRank.