Superlinear integrality gaps
for the minimum majority problem
Philip M. Long
Googleplong@google.com

Abstractm×n, minimize
PnThe minimum majority problem is +asnfollows: given a matrix A ∈ {−1, 1}xsubject
to
Ax
≥
1
and
x
∈
(Z
)
.
An
approximation
algorithm
that
finds
a solutionii=1
with value O(opt2 log m) in poly(m, n, opt) time is known, which can be obtained by rounding
a linear programming relaxation.
We establish integrality gaps that limit the prospects for improving on this guarantee throughimproved rounding and/or the application of Lovász-Schrijver (LS) or Sherali-Adams (SA) tightening of the relaxation. These gaps show that applying LS and SA relaxations cannot improveon the O(opt2 log m) guarantee by more than a constant factor in polynomial time.

1

Introduction

P
This paper is about the minimum majority problem: given A ∈ {−1, 1}m×n , minimize ni=1 xi
subject to Ax ≥ 1 and x ∈ (Z+ )n . This problem is motivated by the margin analysis of boosting[44] (see [33, 34]). It also formalizes the problem of compressing a learned ensemble [42, 8]; startingfrom a classifier that takes a vote over a large number of classifiers, find a small multiset of thevoters that produce the same results on training data.
It is known [25] that, in poly(m, n, opt) time, an algorithm can find a solution with valueO(opt2 log m). This has been proved using boosting [25] and randomized rounding [33]. A simple
and direct proof which borrows ideas from the analysis of boosting [19, 45, 16, 37] is provided in
Section 7. Our work is motivated by the following question: is this O(opt2 log m) algorithm thebest possible?
For many discrete optimization problems, the best polynomial-time approximation algorithm
known may be constructed by rounding the solution of an appropriate relaxation of the problem[39, 2]. While the “natural” LP relaxation suffices for many problems, adding carefully chosen
constraints can sometimes help get better relaxations. Effective systematic methods for generatingsuch stronger relaxations have been developed. A popular example of such a “lift-and-project”
method, which recovers the best approximation algorithms in many cases, is the Lovász-Schrijver(LS) technique [36]. This technique generates a sequence of semi-definite programs with the same
objective function as the original problem, but with feasible regions that approximate the convex
hull of the feasible region of an integer programming problem progressively closely. If N is the sizeof the original problem, the rth LS relaxation has size poly(N r ), which is polynomial in N if r
is a constant. Arora et al. [4, 2] argued persuasively that the strength of this approach and the1breadth of its applicability motivates study of its limitations. The main such mode of analysis is an
integrality gap [35], demonstrating that a solution of the relaxed problem obtained after r roundsof the Lovász-Shrijver method has a solution that is significantly better than the best solution tothe original integer programming problem.
Strong integrality gaps, sometimes for small values of r, have been obtained for several problems
of central interest [35, 20, 52, 47, 11, 21, 2, 29, 31, 5, 17, 27]. Typically, these limit the prospects
for improvements on the approximation ratio that can be achieved in polynomial time (and even insubexponential time) through LS relaxations: i.e., if opt is the value of the optimal solution, they
limit the prospects for achieving optf (n) for some f (n) (which may be a constant).
In this work, we establish integrality gaps for LS and related lift-and-project relaxations for theminimum majority problem. We first show that a constant number of levels of LS cannot yield an
improvement on the O(opt2 log m) guarantee. This is a special case of a more general result: forlarge enough k, r < k5 − 1, and m ≥ k 3 /(r + 1)2 , there is an instance A of the minimum majority
problem such that (a) the rth level Lovász-Schrijver relaxation has value k, and (b) any integer
solution has value Ω((k 2 /(r + 1)2 ) log m). In additional to providing evidence that LS relaxations
cannot improve on the O(opt2 log m) bound in polynomial time, it also demonstrates dim prospects
for substantially improving on this guarantee while using significantly less than the O(nopt ) timeused by a brute-force algorithm.
Another popular lift-and-project method uses Sherali-Adams (SA) [49] relaxations which areincomparable in strength with LS relaxations1 [32]. We next establish a bound for Sherali-Adams(SA) relaxations analogous to the one proved for LS relaxations.
As mentioned above, the minimum majority problem is motivated by applications to machinelearning, but the possibility that O(opt2 log m) might be the best possible approximation guarantee
achievable in polynomial time may be of more fundamental and broader interest, since this form isqualitatively unlike other known bounds.
Other Related Work. For a comparison of various lift-and-project methods, we refer thereader to the survey by Laurent [32], and to the survey by Chlamtac and Tulsiani [13]. In recent
years, several integrality gaps for SA relaxations have been shown (see e.g. [15, 46, 10, 28, 38, 26,
22, 6, 43, 7, 12]). Other kinds of hardness results for some other sparse learning problems can befound in [3, 51, 14, 53, 18].
Techniques. Our analysis uses the probabilistic method, choosing the entries of A ∈ {−1, 1}m×n
independently at random from a distribution that assigns slightly more probability to 1 than −1.
To prove the lower bound for the integer programming solution, we need to show that any small
ensemble is likely to violate one of the constraints – for the candidate solution x, we need a lower
bound on the probability that one of the rows a of A will satisfy a · x ≤ 0. For this, we need a lower
bound on the tail of a sum of independent random variables. The Berry–Esseen inequality does
not appear to provide enough leverage, and it was also not clear how to apply anti-concentration
techniques such as [50, 40, 48, 30] to get the bounds needed here. (The challenges include thepossibility of relatively large summands and their assymmetric distribution.) Instead, we argue
roughly as follows. First, only the components of a corresponding to nonzero components of x
matter. However, if x is a good solution, then there are few of those components, and, thus, typically, the probability of the projection of −a onto those components is not too much more thanthe probability of the projection of a. It follows that the probability that a · x ≤ 0 cannot be too
1

The LS relaxations analyzed here are usually denoted by LS+ , and are sometimes tighter than the “plain” LSrelaxations.

2much smaller than the probability that a · x ≥ 0, which in turn means that it cannot be very small,period.
In contrast, the fractional solution benefits from the stability conferred by averaging over allof the variables. This can be established using standard techniques such as Hoeffding bounds andthe union bound for the linear programming relaxation. Applying a “protection lemma” of [23]demonstrates that it survives multiple rounds of LS tightening; we prove a similar protection lemma
for SA relaxations. The fractional solution qualifies for these protection lemmas because it is far
from violating any of the constraints.
As mentioned above, this work suggests that the unusual O(opt2 log m) guarantee may be thebest possible for this problem. Based on our proof, this is in part because a fractional solution isespecially good when the constraints depend on a lot of variables. In this respect, the minimum
majority problem differs fundamentally from many of the problems whose approximation properties are frequently studied – many of these concern graphs and/or have sparse constraints. The
minimum majority problem may be a representative of a class of problems with fundamentallydifferent approximation properties, and as such may be an interesting subject for further study.

2

Preliminaries

Pn+ n
Let opt(A) be the minimum of
i=1 xi subject to Ax ≥ 1 andPx ∈ (Z ) . (If Ax ≥ 1 isnunsatisfiable, define opt(A) = ∞.) Let optL (A) be the minimum of i=1 xi subject to Ax ≥ 1 andx ≥ 0.
Lemma 1 ([41]) Let U1 , ..., U` be independent random variables
with 
each Ui taking values in

P`
−2η 2
[ai , bi ] and let S = i=1 Ui . Then Pr(S ≥ E(S) + η) ≤ exp P`.
2
i=1 (bi −ai )3An integrality gap for linear programming

As a warmup, we prove the following integrality gap theorem for the linear programming relaxation.
Theorem 2 There are constants k0 , c > 0 and a polynomial p, such that, for all k ≥ k0 andm ≥ k 3 , there is an n ∈ N such that n ≤ p(k, ln m), and A ∈ {−1, 1}m×n , such that optL (A) ≤ k
and opt(A) ≥ ck 2 ln m.

3.1

Setup

The proof uses the probabilistic
analyzing matrices A chosen at random. Setting, withj 2
k method, 2
1
k ln mforesight, γ = k , d =, n = 4k ln m , consider A ∈ {−1, 1}m×n whose entries are drawn
43
i.i.d., with Pr(Aij = 1) = 1/2 + γ, for γ ≤ 1/5. (We can ensure that γ ≤ 1/5 by setting
Pn k ≥ 5.)+n
We set up some notation next. Let S(n, d) consist of all x ∈ (Z ) such that i=1 xi ≤ d (or,equivalently, all multisets of at most d elements of [n]).
P
Say that x ∈ S(n, d) is hit by row i, if row i witnesses the infeasibility of x, i.e., if nj=1 Aij xj ≤ 0.
Say x is hit by A if it is hit by some row of A.

3

3.2

The hit probability

This section analyzes the probability that a prospective solution is hit by a single row. Let Q be
the distribution governing the choice of a single row of A, n i.i.d. draws from a distribution over{−1, 1} that assigns probability 1/2 + γ to 1. For some realization a of a row of A, we will use theshorthand Q(a) for Q({a}), the probability of generating a.
The following will be proved in this subsection.
Lemma 3 For all large enough k0 , for any x ∈ S(n, d), we have Pra∼Q (a·x ≤ 0) ≥ exp(−14γ 2 d).
Proof (of Lemma 3): First, for any realization a, we haveQ(−a)(1/2 + γ)|{j:aj =−1}| (1/2 − γ)|{j:aj =1}|=Q(a)(1/2 + γ)|{j:aj =1}| (1/2 − γ)|{j:aj =−1}|
Pnj=1 aj
1 − 2γ=.
(1)
1 + 2γPn is balanced if | n a | ≤ 3γn and let B be the event that a random
Let us say that a ∈ {−1, 1}Pi=1 i
row is balanced. Since Ea∼Q ( ni=1 ai ) = 2γn, Lemma 1 implies
!
 2 
n
X
γ n
Q(B) = Pra∼Qai ≤ 3γn ≥ 1 − 2 exp −
.
(2)
2
i=1

Furthermore, for a ∈ B,
Q(−a)
=
Q(a)



1 − 2γ
1 + 2γPi ai≤

1 + 2γ1 − 2γ3γn2≤ e13γ nsince γ ≤ 1/5.
We have
Pra∼Q (a · x ≤ 0) + Pra∼Q (a · x ≥ 0)
1≤
Pra∼Q (a · x ≤ 0)
Pra∼Q (a · x ≤ 0)
Pra∼Q (−a · x ≤ 0)
=1+.
Pra∼Q (a · x ≤ 0)

4

(3)

Furthermore
P
Pra∼Q (−a · x ≤ 0)a:(−a)·x≤0 Q(a)= P
Pra∼Q (a · x ≤ 0)Q(a)P a:a·x≤0
a:a·x≤0 Q(−a)= P
Q(a)P a:a·x≤0P
Q(−a)
a∈B:a·x≤0 Q(−a) +Pa6∈B:a·x≤0= Pa∈B:a·x≤0 Q(a) +a6∈B:a·x≤0 Q(a)PP
13γ 2 n +Q(−a)
a∈B:a·x≤0 Q(a)eP
P a6∈B:a·x≤0≤a∈B:a·x≤0 Q(a) +a6∈B:a·x≤0 Q(a)(by (3))P

a6∈B:a·x≤0 Q(−a)
P+Pa∈B:a·x≤0 Q(a) +a6∈B:a·x≤0 Q(a)P2a6∈B:a·x≤0 Q(−a).
= e13γ n +Pra∼Q (a · x ≤ 0)≤e

13γ 2 nFinally,X

Q(−a) ≤

a6∈B:a·x≤0X

Q(−a) =

a6∈B

X

2

Q(a) ≤ 2e−γ n/2a6∈B

by (2).
Tracing back, we get212e−γ n/2
2≤ 1 + e13γ n +.
Pra∼Q (a · x ≤ 0)
Pra∼Q (a · x ≤ 0)
Solving for Pra∼Q (a · x ≤ 0) yields
2

Pra∼Q (a · x ≤ 0) ≥1 − 2e−γ n/2.
1 + e13γ 2 nNote that the truth or falsehood of a · x ≤ 0 is determined by {ai : i ∈ [n], xi 6= 0}. Sincex ∈ S(n, d), when proving this lemma, ignoring the irrelevant components of a, we may assume
without loss of generality that n ≤ d. Thus,2

1 − 2e−γ d/22Pra∼Q (a · x ≤ 0) ≥≥ e−14γ d
2d
13γ
1+e
for all large enough k0 , since m ≥ k 3 and d = Ω(k 2 ln m), completing the proof.

3.3

Analyzing optL and opt

Proof (of Theorem 2): Armed with Lemma 3, we are ready to analyze optL (A) and opt(A) fora random A. Let Q be the distribution governing the random choice of A, and, as before, let Q be
the distribution of any row of A.
5

First, we claim
Pnthat PrA∼Q (optL (A) ≤ k) ≥ 2/3. To see this, consider the solution x1 = ... =xn = k/n. Then i=1 xi = k, and, for any row a of A, Ea∼Q (a · x) = 2γk = 2. Applying Lemma 1
and a union bound,




−2
−n
PrA∼Q (¬Ax ≥ 1) ≤ m exp=
mexp≤ m exp (−2 ln m) ≤ 1/3
n(2k/n)2
2k 2
for large enough k (since m ≥ k 3 ), proving that PrA∼Q (optL (A) ≤ k) ≥ 2/3.
Now we want a lower bound on the probability that opt(A) > d. If, for all x ∈ S(n, d), x is hit
by some row of A, then opt(A) > d. Thus, if we denote the set of rows of A by A, we may apply
Lemma 3 to get
PrA∼Q (opt(A) ≤ d) = Pr(∃x ∈ S(n, d), ∀a ∈ A, a · x > 0)
X Y≤
(1 − Pra∼Q (a · x ≤ 0))x∈S(n,d) a∈A

≤

X

Y


1 − exp(−14γ 2 d)(by Lemma 3)x∈S(n,d) a∈A



m
d+n
=
1 − exp(−14γ 2 d)d  n 
≤ exp d 1 + ln
− m exp(−14γ 2 d) .
d
Substituting the values of d, n, and γ, recalling m ≥ k 3 , for all large enough values of k0 , we have
14 ln m2,
PrA∼Q (opt(A) ≤ d) ≤ exp k ln m − m exp −43
and, once again since m ≥ k 3 , for a large enough value of k, this implies
PrA∼Q (opt(A) ≤ d) ≤ 1/3.
Combining this with PrA∼Q (optL (A) ≤ k) ≥ 2/3, this completes the proof

4

A 0/1 integer programming formulation

Systematic methods for constructing more refined relaxations of integer programming problems
often are designed for the case in which the variables are constrained to 0/1 values. If algorithms
are allowed time polynomial in opt, as well as n and m, then they can make use of integer programs
that use poly(n, m, opt) variables. A natural formulation of the minimum majority problem as a 0/1
integer programming problem satisfies this requirement. Define the q-bounded minimum majority
problem to be the minimum majority problem under the additional restriction that each variable
is included the solution with multiplicity at most q. We may formulate the q-bounded minimum
majority problem as follows, where U is an n × q matrix:
min

q
n X
X
j=1 `=1

Uj,` , s.t. ∀i,

n
X

Aij

q
X

j=1

`=1

6

Uj` ≥ 1, ∀j, `, Uj` ∈ {0, 1}.

When q ≥ opt, this is equivalent to the original minimum majority problem. An (approximation)
algorithm may then solve the original minimum majority problem by “guessing”
P a suitable upperbound q. One may view Uj` as an indicator function for xj ≥ `, so that xj = q`=1 Uj` .
Another alternative uses a binary encoding:
min

q
n X
X

`−1

2

Uj,` , s.t. ∀i,

j=1 `=1

n
X

Aij

q
X

j=1

2`−1 Uj` ≥ 1, ∀j, `, Uj` ∈ {0, 1}.

`=1This is equivalent to the original minimum majority problem when q ≥ log2 opt, and, again, an
approximation algorithm could “guess” a suitable value of q.
Both of these fall within the class of algorithms that perform
min

q
n X
X
j=1 `=1β` Uj,` , s.t. ∀i,

n
X

Aij

j=1

q
X

β` Uj` ≥ 1, ∀j, `, Uj` ∈ {0, 1}`=1for β1 = 1 and β2 , ..., βq ∈ N. The natural linear programming relaxation of such an integer program
replaces each constraint that Uj` ∈ {0, 1} with Uj` ∈ [0, 1]. We will prove integrality gaps for all
such programs.

5

Gaps for Lovász-Schrijver relaxations

In this section, we establish integrality gaps for Lovász-Schrijver (LS) relaxations of 0/1 integer
programming formulations of the minimum majority problem.

5.1

Definition of LS relaxations and statement of gap theorem

Lovász-Schrijver relaxations are obtained through rounds, which progressively tighten the relaxation. Here is the definition of one round, following [23, 2]. (For intuition, please see [36, 13].)
Before the round, the feasible region is P = {x : Ax ≥ b, x ∈ [0, 1]n }.
The first step is to embed P into Rn+1 , to produce a cone K that may be regarded as equivalent:
K = {(x0 , x) : Ax ≥ x0 b, x ∈ [0, x0 ]n }. When analyzing K, we will number indices from 0 as usual;for each i ∈ {0, ..., n}, let ei be the element of {0, 1}n+1 with a 1 only in position i.
Next is the “lifting” step, which defines a subset M (K) of R(n+1)×(n+1) , which might be thoughtof as constraints on products of pairs of variables. A symmetric Y is in M (K) if• Y e0 = diag(Y ), and• Y ei , Y (e0 − ei ) ∈ K for all i ∈ {1, ..., n}.
The set M+ (K) is obtained from M (K) by adding the constraint that Y is positive semi-definite.
Next is the “project” step, producing N+ (K) = {diag(Y ) : Y ∈ M+ (K)}. The extra variable
added when K was defined is still present in N+ (K). To get N+ (P ), it is removed, by setting
N+ (P ) = {(x1 , ...., xn ) : (1, x1 , ..., xn ) ∈ N+ (K)}.
This process can be iterated: N+0 (P ) = P and N+r (P ) = N+ (N+r−1 (P )).
Definition 4 P
For q P
∈ N and β = (β1 , ..., βq ), let optLS,r,β (A) be the value of the optimal solution
to minimizing nj=1 q`=1 β` Uj` subject to membership in N+r (P ).
7

Note that, for q ≥ opt(A), we have optL (A) = optLS,0,β (A). Here is the gap theorem for LS
relaxations.
Theorem 5 For all r ∈ N, there are constants k0 , c > 0 and a polynomial p, such that, forall k ∈ Z+ such that k > max{k0 , 5(r + 1)} and m ≥ k 3 /(r + 1)2 , there is an n ∈ N withn ≤ p(k, ln m), and A ∈ {−1, 1}m×n , such that, for any q ≥ 1, for any β ∈ Nq , optLS,r,β (A) ≤ k,2kbut opt(A) ≥ c r+1
ln m.

5.2

Setup

r+1
As in thekproof lof Theoremjm 2, this proof analyzes matrices A chosen at random. Let γ = k , d =22k ln mln m, n = 4k
, consider A ∈ {−1, 1}m×n whose entries are drawn i.i.d., with Pr(Aij =43(r+1)2(r+1)2
1) = 1/2 + γ. (Note that, since k > 5(r + 1), we have γ P< 1/5.)P
n×q
Let S(n, d, β) consist of all U ∈ {0, 1}
such that ni=1 qj=1 βj Uij ≤ d.

Lemma 6 If k0 is large enough,Pr(opt(A) ≤ d) ≤ 1/3.
Proof: By construction, for any U ∈ S(n, d, β), there is in x ∈ (Z+ )n such that Ax ≥ 1 iff U is
feasible.
k
l
j
m
m
m
, n = 4 ln
Noting that, as before, d = γln2 43, and γ ≤ 1/5, exactly the same analysis as inγ2
the proof of Theorem 2 then implies that 
 n 
− m exp(−14γ 2 d) .
Pr(opt(A) ≤ d) ≤ exp d 1 + lndUsing the values of d, n and γ from this proof, we get 2k ln m14 ln mPr(opt(A) ≤ d) ≤ exp− m exp −,r2
43which, as before, is at most 1/3 for large enough k, since m ≥ k 3 /(r + 1)2 .

5.3

A protection lemma

Recall that the LS technique works by tightening the constraints so that N+r (P ) is an increasingly
accurate approximation to the feasible region for the 0/1 integer program associated with A. So,
to establish an integrality gap, we would like to show that a fractional solution that is much better
than the best integer solution can survive many LS lift-project rounds.
The first step is a “protection lemma”, which describes conditions under which a fractional
solution survives one round.
To state this protection lemma, the following definition will be helpful. For x ∈ [0, 1]n , i ∈{1, ..., n} and b ∈ {0, 1}, let round(x, i, b) be the element of [0, 1]n obtained by replacing xi with b.
We will use Lemma 9 of [9], attributed there to [23] (see also the third paragraph after Lemma
2.1 in [1]).
Lemma 7 ([23]) If x ∈ P and, for any i ∈ {1, ..., n}, round(x, i, 0) ∈ P and round(x, i, 1) ∈ P ,then x ∈ N+ (P ).
8For I ⊆ {1, ..., n} and b ∈ {0, 1}|I| , define round(x, I, b) analogously to round(x, i, b). As observedin [2], Lemma 7 has the following corollary, which can be proved by induction.
Lemma 8 ([2]) If x ∈ P and, for any I ∈ {1, ..., n} with |I| = r and any b ∈ {0, 1}r , round(x, I, b) ∈P , then x ∈ N+r (P ).

5.4

Bounding optLS,r,β

Lemma 9 Pr(optLS,r,β (A) ≤ k) ≥ 2/3.
Proof: Consider the solution U with U11 = ... = Un1 = nk and Uij = 0 for all j > 1.
For a subset I of index pairs, which index into components of U , and b ∈ {0, 1}|I| , defineround(U, I, b) analogously to round(x, I, b) to be the result of rounding the values indexed by I
using the values in b. For any row a of A, since the components of a are all in {−1, 1}, rounding
any entry in U can change any component of AU 1 by at most 1. Thus, if x = U 1, we have
PrA (∃I, |I| = r, b ∈ {0, 1}r , ¬A round(U, I, b) 1 ≥ 1) ≤ PrA (¬AU 1 ≥ (r + 1)1)
= PrA (¬Ax ≥ (r + 1)1).
For any row a of A, Ea (a · x) = 2γk = 2(r + 1). Applying Lemma 1 and a union bound,−2(r + 1)2
Pr(¬Ax ≥ (r + 1)1) ≤ m exp= m exp (−2 ln m) ≤ 1/3
n(2k/n)2
for large enough k, proving that Pr(optLS,r,β (A) ≤ k) ≥ 2/3.

5.5

Putting it together

Proof (of Theorem 5): Combining Lemmas 6 and 9, a random A satisfies the requirements ofTheorem 5 with probability at least 1/3.

6

Gaps for Sherali-Adams relaxations

In this section, we establish integrality gaps for Sherali-Adams (SA) relaxations of an integer
programming formulation of the minimum majority problem.

6.1

Definition of SA relaxations and statement of gap theorem

The description is based on [13], which also gives useful intuition.
Let P = {x : Ax ≥ b}. Assume that the constraints that define P include 0 ≤ xi ≤ 1 for all
variables i.
The level-r SA relaxation is obtained through the following steps: For each constraint a · x ≥ bfrom the original problem, and each pair I and J of disjoint subsets of [n] such that |I| + |J| = r,
add the constraint!YY(a · x − b)xi  (1 − xj ) ≥ 0.
i∈I

j∈J

9

Expand each LHS to express it as a sum of monomials. For each term, replace any xkj for k > 1
with xj (the degree reduction step). Define a variable YS for each set of at most r + 1 variables. For
each LHS, replace each term (which is now a product of a set S of at most r + 1 variables) with YS .
(The P
result isa set of linear inequalities over {YS : S ⊆ [n], |S| ≤ r + 1}, which defines a polytopen
Q in r+1
j=0 j dimensions.) Finally, project the result onto {YS : S ⊆ [n], |S| = 1}.
If we denote SAr (P ) be the level-r SA relaxation of P , then x ∈ SAr (P ) if and only if there isan assignment y to {YS : S ⊆ [n], |S| ≤ r + 1} such that y ∈ Q and xi = y{i} for all i ∈ [n].
PnLet N = r+1
k=0 k be the dimension of this higher dimensional space.
Definition 10 Let optSA,r,β (A) be the value of the optimal solution to minimizingqn X
Xβ` Uj`

j=1 `=1

subject to membership in SAr (P ).
Theorem 11 For all r ∈ N , there are constants k0 , c > 0 and a polynomial p such that, for allk ∈ Z+ such that k > max{k0 , 5(r + 1)} and m ≥ k 3 /(r + 1)2 , there is an n ∈ N with n ≤ p(k, ln m)and there is an A ∈ {−1, 1}m×n , such that, for any q ≥ 1, for any β ∈ Nq , optSA,r,β (A) ≤ k, but2kopt(A) ≥ c r+1
ln m.

6.2

A protection lemma

A protection lemma analogous to Lemma 8 also holds for SA relaxations.
Lemma 12 If x ∈ P and, for any I ∈ {1, ..., n} with |I| ≤ r and any b ∈ {0, 1}|I| , round(x, I, b) ∈P , then x ∈ SAr (P ).
Proof: Let Q be the polytope in RN whose projection yields SAr (P ). Let φ be the mapping from
Rn toQ
RN defined by φ(x) = y, where y is indexed by subsets of at most r + 1 elements of [n], andyS = i∈S xi . Note that, if φ(x) ∈ Q, we have x ∈ SAr (P ).
Now, choose x satisfying the hypotheses of the lemma. To prove that x ∈ SAr (P ), it suffices
to prove that φ(x) ∈ Q. Choose a constraint from among those defining Q: suppose that it wasderived from the original constraint ax ≥ b together
with indexinP
Pn sets I and J. The constraint0
0
0
RN arising from the Sherali-Adams process is J 0 ⊆J (−1)|J |
a
Y
−
bY
≥
0
(see
S∪J
`=1 i S∪J ∪{`}[13]). Thus, it suffices to prove


n
X
X
Y
Y
0
x`  ≥ 0.
(4)(−1)|J | aix` − bJ 0 ⊆J

i=1`∈I∪J 0 ∪{i}`∈I∪J 0

Toward this end, consider x0 obtained by rounding x as follows. Note that the LHS of (4) is linear
in each x` , if the other components of x are fixed. Thus, for each ` ∈ I ∪ J, the LHS of (4) iseither non-increasing or non-decreasing in x` as it varies between 0 and 1. Thus, there is a choiceof how to round x` to either 0 or 1 that does not change the sign of the LHS from non-negative tonegative, or from negative to non-negative. Let x0 be constructed from x by rounding elements of
I ∪ J one at a time in this manner.
10

We consider two cases. First supposethatof I was rounded to 0 or a member of JQ
Q a member000
was rounded to 1. Then (a · x − b)( i∈I xi )( j∈J (1 − xj )) = 0, and, since all the variables affectedby the degree reduction step are in I ∪ J, and this degree reduction has no effect for elements of{0, 1}, this implies


n
X
Y
X
Y
0
(−1)|J | x0` − bx0`  = 0.
ai
J 0 ⊆J

i=1`∈I∪J 0 ∪{i}`∈I∪J 0Since the transformation from x to x0 did not change the sign from negative to non-negative, this
implies that (4) holds.
Now, suppose that all membersof I were rounded to 1, andall members of J were roundedPQ
Q
0 | Pn|J0000
to 0. Then J 0 ⊆J (−1)`∈I∪J 0 x` = a · x − b ≥ 0, since x was
i=1 ai`∈I∪J 0 ∪{i} x` − bobtained from x by rounding at most r components. This completes the proof.

6.3

Putting it together

Proof (of Theorem 11): The proof is exactly the same as the proof of Theorem 5, except
replacing Lemma 8 with Lemma 12.

7

A simple and direct proof of an upper boundP
The algorithm solves the more general problem: for A ∈ {−1, 1}m×n and b ∈ Zm , minimize ni=1 xi
subject to Ax ≥ b, and x ∈ (Z+ )n . We have a problem for each (A, b) pair; let opt(A, b) be thevalue of its optimal solution. (Let us use the shorthand opt(A) for opt(A, (1, 1, ..., 1)T ). Then, if,for each variable i, we denote the ith column of A by Ai , we haveopt(A, b) = 1 + min opt(A, b − Ai ).

(5)i

To see this, consider commiting to make xi ≥ 1. This gives rise to a subproblem of a similar
form with the constraints updated as indicated. Obviously, if no component of b is positive, thenopt(A, b) = 0.
The algorithm exploits this recursive structure using a parameter η ∈ (0, 1/2) that will be set
using the analysis:• if no component of b is positive, return (0, 0, ..., 0) and halt,• otherwise,– choose i to minimize

Pm

t=1 exp(η(bt − Ati )),– recurse to solve the problem with b replaced by b − Ai , getting x,– return the solution obtained from x by adding 1 to xi .
PLet us call m
t=1 exp(ηbt ) the potential.
Our analysis of this algorithm uses the following, which is essentially the discriminator lemma
[24].
T

r b
Lemma 13 For any r ∈ [0, ∞)m , there is an i such that rT Ai ≥ opt(A,b).

11

Proof: First, since all components of r are non-negative, rT Ax ≥ rT b for all feasible x. If x∗ isT∗
Tan optimum, if we sample i from x∗ /||x∗ ||1 = x∗ /opt(A, b), we have E(rT Ai ) = r||xAx≥ ||xr ∗ ||b 1 ,∗ ||1completing the proof.
Lemma 13 implies that,r · Ai1∀r ∈ (R+ )m , ∃i,≥.
(6)||r||1opt(A)
Note that this is a property of A, and that A does not change as the algorithm progresses, so that
(6) always remains true throughout the recursion.
Now,Pwe want to bound the reduction in the potential priorPto the recursive call. Let Pnew =mmini∈[n] mt=1 exp(η(bt − Ati )) be the new potential, and Pold =t=1 exp(ηbt ) be the old potential.
We have
Pnew /Pold
m

X
1
min
exp(η(bt − Ati ))Pold i∈[n]t=1
m  −η
X
e + eη
1e−η − eηmin
= Pm+
Ati exp(ηbt )2
2
t=1 exp(ηbt ) i∈[n]=t=1e−η + eηe−η − eη
≤
+
,
2
2opt
by (6). Applying Taylor series, we have
Pnew /Pold ≤ 1 −η
+ (1/2 + o(1))η 2 .
opt

1(and we may assume w.l.o.g. that the algorithm “knows” opt, since it can guess
Setting η = opt
progressively larger values), we get

Pnew /Pold ≤ 1 − (1/2 − o(1))

1
.
opt2

If b = (1, 1, ...1), the potential starts at m exp(η). After s recursive calls, it is at mosts1
1 − (1/2 − o(1))
m exp(η).
opt2
When all components of b are at most 0, we may stop. If we have not stopped, the potential is atleast eη . Thus, on input (A, (1, 1, ..., 1)T ), the number of recursive calls before stopping is at most
(2 + o(1))opt(A)2 ln m. This bounds the total number of times that the solution is incremented
when returning from the nested recursion, completing the proof.

Acknowledgments
I would like to thank Dave Helmbold and Kunal Talwar for valuable conversations. I am also
grateful to anonymous reviewers for their careful reading of the paper, and their helpful comments
and suggestions.
12References[1] Michael Alekhnovich, Sanjeev Arora, and Iannis Tourlakis. Towards strong nonapproximability
results in the Lovász-Schrijver hierarchy. In STOC, pages 294–303, 2005.
[2] Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis. Towards strong nonapproximability
results in the Lovász-Schrijver hierarchy. Computational Complexity, 20(4):615–648, 2011.
[3] Edoardo Amaldi and Viggo Kann. On the approximability of minimizing nonzero variables or
unsatisfied relations in linear systems. Theoretical Computer Science, 209(1-2):237–260, 1998.
[4] Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis. Proving integrality gaps
without knowing the linear program. Theory of Computing, 2(2):19–51, 2006.
[5] Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, and Ola Svensson. No small linear programapproximates vertex cover within a factor 2 - ε. Math. Oper. Res., 44(1):147–172, 2019.
[6] Siavosh Benabbas and Avner Magen. Extending SDP integrality gaps to Sherali-Adams withapplications to quadratic programming and maxcutgain. In International Conference on Integer Programming and Combinatorial Optimization, pages 299–312. Springer, 2010.
[7] Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, andYuan Zhou. Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In
Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages
388–405. Society for Industrial and Applied Mathematics, 2012.
[8] Cristian Bucilu, Rich Caruana, and Alexandru Niculescu-Mizil. Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data
mining, pages 535–541. ACM, 2006.
[9] Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi.
Rank bounds and integrality gaps for cutting planes procedures. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 318–327. IEEE, 2003.
[10] Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Integrality gaps for SheraliAdams relaxations. In Proceedings of the forty-first annual ACM symposium on Theory ofcomputing, pages 283–292. ACM, 2009.
[11] Jeff Cheeger, Bruce Kleiner, and Assaf Naor. A (log n)Ω(1) integrality gap for the sparsest cut
SDP. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposiumon, pages 555–564. IEEE, 2009.
[12] Eden Chlamtác and Pasin Manurangsi. Sherali-Adams integrality gaps matching the logdensity threshold. In APPROX, pages 10:1–10:19, 2018.
[13] Eden Chlamtac and Madhur Tulsiani. Convex relaxations and integrality gaps. In Handbook
on semidefinite, conic and polynomial optimization, pages 139–169. Springer, 2012.
[14] Ali Civril. A note on the hardness of sparse approximation. Information Processing Letters,
113(14):543–545, 2013.
13

[15] Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu. Linear programming relaxationsof maxcut. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 53–61. Society for Industrial and Applied Mathematics, 2007.
[16] N. Duffy and D. Helmbold. Potential boosters? In Proceedings of NIPS, pages 258–264, 1999.
[17] Noah Fleming, Pravesh Kothari, Toniann Pitassi, et al. Semialgebraic proofs and efficientalgorithm design. Foundations and Trends R in Theoretical Computer Science, 14(1-2):1–221,
2019.
[18] Dean Foster, Howard Karloff, and Justin Thaler. Variable selection is hard. In Conference on
Learning Theory, pages 696–709, 2015.
[19] Y. Freund and Robert E. Schapire:. A decision-theoretic generalization of on-line learningand an application to boosting. J. Comput. Syst. Sci., 55(1):119–139, 1997. Special Issue for
EuroCOLT ’95.
[20] Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997.
[21] Konstantinos Georgiou, Avner Magen, Toniann Pitassi, and Iannis Tourlakis. Integrality gapsof 2-o(1) for vertex cover SDPs in the Lovász–Schrijver hierarchy. SIAM Journal on Computing,39(8):3553–3570, 2010.
[22] Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. Optimal Sherali-Adams gaps
from pairwise independence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 125–139. Springer, 2009.
[23] Michel X Goemans and Levent Tunçel. When does the positive semidefiniteness constraint
help in lifting procedures? Mathematics of Operations Research, 26(4):796–815, 2001.
[24] A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, and G. Turán. Threshold circuits of bounded
depth. J. Comp. Sys. Sci., 46:129–154, 1993.
[25] J. Jackson and M. Craven. Learning sparse perceptrons. In NIPS 8, pages 654–660, 1996.
[26] Anna R Karlin, Claire Mathieu, and C Thach Nguyen. Integrality gaps of linear and semidefinite programming relaxations for knapsack. In International Conference on Integer Programming and Combinatorial Optimization, pages 301–314. Springer, 2011.
[27] Steven Kelk and Georgios Stamoulis. Integrality gaps for colorful matchings. Discrete Optimization, 32:73–92, 2019.
[28] Subhash Khot and Rishi Saket. SDP integrality gaps with local `1 -embeddability. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on, pages 565–574.
IEEE, 2009.
[29] Subhash A Khot and Nisheeth K Vishnoi. The unique games conjecture, integrality gap for cut
problems and embeddability of negative-type metrics into `1 . Journal of the ACM (JACM),
62(1):8, 2015.

14

[30] M. Krishnapur. Anti-concentration inequalities, 2016.
[31] Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Victor Verdugo, andAndreas Wiese. Semidefinite and linear programming integrality gaps for scheduling identicalmachines. Math. Program., 172(1-2):231–248, 2018.
[32] Monique Laurent. A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Mathematics of Operations Research, 28(3):470–496, 2003.
[33] P. M. Long. Using the pseudo-dimension to analyze approximation algorithms for integer
programming. Proceedings of the Seventh International Workshop on Algorithms and Data
Structures, 2001.
[34] P. M. Long. Minimum majority classification and boosting. Proceedings of the The Eighteenth
National Conference on Artificial Intelligence, 2002.
[35] L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics,
13:383–390, 1975.
[36] László Lovász and Alexander Schrijver. Cones of matrices and set-functions and 0–1 optimization. SIAM Journal on Optimization, 1(2):166–190, 1991.
[37] L. Mason, J. Baxter, P. L. Bartlett, and M. Frean. Boosting algorithms as gradient descent.
In Advances in Neural Information Processing Systems 12, pages 512–518. MIT Press, 2000.
[38] Claire Mathieu and Alistair Sinclair. Sherali-Adams relaxations of the matching polytope. In
Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 293–302.
ACM, 2009.
[39] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
[40] V. V. Petrov. Limit theorems of probability theory. Oxford Science Publications, Oxford,
England, 1995.
[41] D. Pollard. Convergence of Stochastic Processes. Springer Verlag, Berlin, 1984.
[42] J. R. Quinlan. Some elements of machine learning. Proceedings of the Sixteenth International
Conference on Machine Learning, pages 523–524, 1999.
[43] Prasad Raghavendra and David Steurer. Integrality gaps for strong SDP relaxations of uniquegames. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposiumon, pages 575–585. IEEE, 2009.
[44] R. E. Schapire, Y. Freund, P. L. Bartlett, and W. S. Lee. Boosting the margin: A new
explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651–1686,
1998.
[45] R.E. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions.
Machine Learning, 37(3):297–336, 1999.

15

[46] Grant Schoenebeck. Linear level Lasserre lower bounds for certain k-CSPs. In Foundations ofComputer Science, 2008. FOCS’08. IEEE 49th Annual IEEE Symposium on, pages 593–602.
IEEE, 2008.
[47] Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani. Tight integrality gaps for LovászSchrijver LP relaxations of vertex cover and max cut. In STOC, pages 302–310. ACM, 2007.
[48] R. A. Servedio. Every linear threshold function has a low-weight approximator. Computational
Complexity, 16(2):180–209, 2007.
[49] Hanif D. Sherali and Warren P. Adams. A hierarchy of relaxations between the continuous andconvex hull representations for zero-one programming problems. SIAM Journal on Discrete
Mathematics, 3(3):411–430, 1990.
[50] E. Slud. Distribution inequalities for the binomial law. Annals of Probability, 5:404–412, 1977.
[51] Christino Tamon and Jie Xiang. On the boosting pruning problem. In European Conference
on Machine Learning, pages 404–412. Springer, 2000.
[52] Iannis Tourlakis. Towards optimal integrality gaps for hypergraph vertex cover in the LovászSchrijver hierarchy. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 233–244. Springer, 2005.
[53] Yuchen Zhang, Martin J Wainwright, and Michael I Jordan. Lower bounds on the performanceof polynomial-time algorithms for sparse linear regression. In Conference on Learning Theory,
pages 921–948, 2014.

16