Gábor Braun

ICML Conference 2019 Conference Paper

Blended Conditonal Gradients

• Gábor Braun
• Sebastian Pokutta
• Dan Tu
• Stephen J. Wright 0001

We present a blended conditional gradient approach for minimizing a smooth convex function over a polytope P, combining the Frank{–}Wolfe algorithm (also called conditional gradient) with gradient-based steps, different from away steps and pairwise steps, but still achieving linear convergence for strongly convex functions, along with good practical performance. Our approach retains all favorable properties of conditional gradient algorithms, notably avoidance of projections onto P and maintenance of iterates as sparse convex combinations of a limited number of extreme points of P. The algorithm is lazy, making use of inexpensive inexact solutions of the linear programming subproblem that characterizes the conditional gradient approach. It decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the lazy conditional gradient algorithms of Braun et al. 2017. We also present a streamlined version of the algorithm that applies when P is the probability simplex.

JMLR Journal 2019 Journal Article

Lazifying Conditional Gradient Algorithms

• Gábor Braun
• Sebastian Pokutta
• Daniel Zink

Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls. [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

ICML Conference 2017 Conference Paper

Lazifying Conditional Gradient Algorithms

• Gábor Braun
• Sebastian Pokutta
• Daniel Zink

Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls.

SODA Conference 2016 Conference Paper

The matching problem has no small symmetric SDP

• Gábor Braun
• Jonah Brown-Cohen
• Arefin Huq
• Sebastian Pokutta
• Prasad Raghavendra
• Aurko Roy
• Benjamin Weitz
• Daniel Zink

STOC Conference 2015 Conference Paper

Inapproximability of Combinatorial Problems via Small LPs and SDPs

• Gábor Braun
• Sebastian Pokutta
• Daniel Zink

Motivated by [12], we provide a framework for studying the size of linear programming formulations as well as semidefinite programming formulations of combinatorial optimization problems without encoding them first as linear programs. This is done via a factorization theorem for the optimization problem itself (and not a specific encoding of such). As a result we define a consistent reduction mechanism that degrades approximation factors in a controlled fashion and which, at the same time, is compatible with approximate linear and semidefinite programming formulations. Moreover, our reduction mechanism is a minor restriction of classical reductions establishing inapproximability in the context of PCP theorems. As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constraints) for several problems that are not 0/1-CSPs: we obtain a 3/2-epsilon inapproximability for Vertex Cover (which is not of the CSP type) answering an open question in [12], we answer a weak version of our sparse graph conjecture posed in [6] showing an inapproximability factor of 1/2+ε for bounded degree IndependentSet, and we establish inapproximability of MaxMULTICUT (a non-binary CSP). In the case of SDPs, we obtain relative inapproximability results for these problems.

SODA Conference 2015 Conference Paper

The matching polytope does not admit fully-polynomial size relaxation schemes

• Gábor Braun
• Sebastian Pokutta

The groundbreaking work of Rothvoß [2014] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the matching polytope has exponential extension complexity). We generalize this result by deriving strong bounds on the polyhedral inapproximability of the matching polytope: for fixed 0 < ε < 1, every polyhedral (1 + ε/ n )-approximation requires an exponential number of inequalities, where n is the number of vertices. This is sharp given the well-known ρ -approximation of size provided by the odd-sets of size up to ρ/ ( ρ — 1). Thus matching is the first problem in P, whose natural linear encoding does not admit a fully polynomial-size relaxation scheme (the polyhedral equivalent of an FPTAS), which provides a sharp separation from the polynomial-size relaxation scheme obtained e. g. , via constant-sized odd-sets mentioned above. Our approach reuses ideas from Rothvoß [2014], however the main lower bounding technique is different. While the original proof is based on the hyperplane separation bound (also called the rectangle corruption bound), we employ the information-theoretic notion of common information as introduced in Braun and Pokutta [2013], which allows to analyze perturbations of slack matrices. It turns out that the high extension complexity for the matching polytope stems from the same source of hardness as for the correlation polytope: a direct sum structure.

FOCS Conference 2013 Conference Paper

Common Information and Unique Disjointness

• Gábor Braun
• Sebastian Pokutta

We provide a new framework for establishing strong lower bounds on the nonnegative rank of matrices by means of common information, a notion previously introduced in [1]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with He linger distance estimations we can compute the (almost) exact common information of UDISJ partial matrix. We also establish robustness of this estimation under various perturbations of the UDISJ partial matrix, where rows and columns are randomly or adversarially removed or where entries are randomly or adversarially altered. This robustness translates, via a variant of Yannakakis' Factorization Theorem, to lower bounds on the average case and adversarial approximate extension complexity. We present the first family of polytopes, the hard pair introduced in [2] related to the CLIQUE problem, with high average case and adversarial approximate extension complexity. We also provide an information theoretic variant of the fooling set method that allows us to extend fooling set lower bounds from extension complexity to approximate extension complexity.

FOCS Conference 2012 Conference Paper

Approximation Limits of Linear Programs (Beyond Hierarchies)

• Gábor Braun
• Samuel Fiorini
• Sebastian Pokutta
• David Steurer

We develop a framework for proving approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that quadratic approximations for CLIQUE require linear programs of exponential size. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem) Moreover, we establish a similar result for approximations of semi definite programs by linear programs. Our main technical ingredient is a quantitative improvement of Razborov's rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjoint ness matrix.