This note closes a gap in the proof of Theorem VI.3 from the article “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory” (2017).

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.

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.

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.

We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness. As a measure of complexity, we use distributional oracle complexity, which subsumes randomized oracle complexity as well as worst case oracle complexity. We obtain strong lower bounds on distributional oracle complexity for the box [-1, 1]n, as well as for the L p-ball for p ≥ 1 (for both low-scale and large-scale regimes), matching worst case upper bounds, and hence we close the gap between distributional complexity, and in particular, randomized complexity and worst case complexity. Furthermore, the bounds remain essentially the same for high-probability and bounded-error oracle complexity, and even for combination of the two, i.e., bounded-error highprobability oracle complexity. This considerably extends the applicability of known bounds.

Yannakakis [27, 26] showed that the matching problem does not have a small symmetric linear program. Rothvoß [23] recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the asymmetric metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size nk. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.

Border bases arise as a canonical generalization of Gröbner bases, using order ideals instead of term orderings. We provide a polyhedral characterization of all order ideals (and hence all border bases) that are supported by a zero-dimensional ideal: order ideals that support a border basis correspond one-to-one to integral points of the order ideal polytope. In particular, we establish a crucial connection between the ideal and its combinatorial structure. Based on this characterization we also provide an adaptation of the border basis algorithm of Kehrein and Kreuzer [J. Pure Appl. Algebra, 205 (2006), pp. 279--295] to allow for computing border bases for arbitrary order ideals, given implicitly via maximizing a preference on monomials (variable selection problem), independent of term orderings. The algorithm requires the same size of resources as the border basis algorithm except for some minor overhead. We also show that the underlying variable selection problem of finding an order ideal that supports a border basis is NP-hard and that any linear description of the associated convex hull of all order ideals requires a superpolynomial number of inequalities.

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.

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.

Recently, Rothvoß established that every linear program (LP) 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 LP inapproximability of the matching problem: for fixed 01-ρn)) provided by the odd-sets of size up to 1/(1-ρ). Thus, matching is the first problem in F, which does not admit a fully polynomial-size LP relaxation scheme (the LP equivalent of an Fully Polynomial-Time Approximation Scheme), which provides a sharp separation from the polynomial-size LP relaxation scheme obtained, e.g., through constant-sized odd-sets mentioned above. Analyzing the size of LP formulations is equivalent to examining the nonnegative rank of matrices. We study the nonnegative rank through an information-theoretic approach; while it reuses key ideas from Rothvoß, the main lower bounding technique is different: we employ the information-theoretic notion of Wyner's common information used for studying LP formulations. This allows us to analyze the nonnegative rank of perturbations of slack matrices, e.g., the approximations of the matching polytope. It turns out that the high extension complexity for the matching problem stems from the same source of hardness as in the case of the correlation polytope: a direct sum structure.

We study the minimum number of constraints needed to formulate random instances of the maximum stable set problem via LPs (more precisely, linear extended formulations), in two distinct models. In the uniform model, the constraints of the LP are not allowed to depend on the input graph, which should be encoded solely in the objective function. There we prove a super-polynomial lower bound with overwhelming probability for every LP that is exact for a randomly selected set of instances with a natural distribution. In the non-uniform model, the constraints of the LP may depend on the input graph, but we allow weights on the vertices. The input graph is sampled according to the Erdös-Renyi model. There we obtain upper and lower bounds holding with high probability for various ranges of p. We obtain a super-polynomial lower bound all the way from essentially p = polylog(n) / n to p = 1 / log n. Our upper bound is close as there is only an essentially quadratic gap in the exponent, which also exists in the worst case model. Finally, we state a conjecture to close the gap both in the average-case and worst-case models.

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.

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.