Complexity Theoretic Limitations on Learning Halfspaces

Amit Daniely

Source-linked AI summary

Complexity Theoretic Limitations on Learning Halfspaces

Amit Daniely

arXiv:1505.05800v2May 21, 2015cs.CCcs.LG

TL;DR

The paper asks whether agnostic halfspaces can be efficiently learned with guarantees meaningfully close to the best halfspace, even when the data are nearly realizable. Using a reduction framework based on the hardness of refuting random K-XOR formulas, it proves strong hardness on binary distributions, extending to very small error levels and outperforming prior proper-learning lower bounds.

Problem
Agnostic halfspace learning lacks strong hardness results for general, including improper, algorithms, while existing results mainly rule out exact learning.
Method
The paper applies the author, Linial, and Shalev-Shwartz framework under assumptions that refuting random K-XOR formulas is hard.
Results
No polynomial-time algorithm has non-trivial performance on binary η-almost-realizable distributions for constant η, and under a stronger assumption this holds for η = 2^-log^(1-ν)(n).
Takeaways & Limitations
The results rule out constant approximation ratios under the basic assumption and 2^log^(1-ν)(n) ratios under the stronger assumption, improving prior exact-learning lower bounds.
Takeaways & Limitations
The hardness results rely on assumptions about the intractability of refuting random K-XOR formulas, with stronger conclusions requiring the stronger assumption.

Abstract

from arXiv · show

We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution $\mathcal{D}$ on $\mathbb{Q}^n\times \{\pm 1\}$. We define $\mathrm{Err}_{\mathrm{HALF}}(\mathcal{D})$ as the least error of a halfspace classifier for $\mathcal{D}$. A learner who can access $\mathcal{D}$ has to return a hypothesis whose error is small compared to $\mathrm{Err}_{\mathrm{HALF}}(\mathcal{D})$. Using the recently developed method of the author, Linial and Shalev-Shwartz we prove hardness of learning results under a natural assumption on the complexity of refuting random $K$-$\mathrm{XOR}$ formulas. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that $\mathrm{Err}_{\mathrm{HALF}}(\mathcal{D}) \le η$ for arbitrarily small constant $η>0$, and that $\mathcal{D}$ is supported in $\{\pm 1\}^n\times \{\pm 1\}$. Namely, even under these favorable conditions its error must be $\ge \frac{1}{2}-\frac{1}{n^c}$ for every $c>0$. In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where $K$ can be poly-logarithmic in $n$), we can take $η= 2^{-\log^{1-ν}(n)}$ for arbitrarily small $ν>0$. Interestingly, this is even stronger than the best known lower bounds (Arora et. al. 1993, Feldamn et. al. 2006, Guruswami and Raghavendra 2006) for the case that the learner is restricted to return a halfspace classifier (i.e. proper learning).

1 Introduction

The paper establishes strong computational hardness for agnostically learning halfspaces, even on binary, nearly realizable distributions. Under random K-XOR refutation assumptions, efficient algorithms cannot achieve non-trivial performance or constant-factor approximation, including in large-margin and statistical-query settings.

1 Introduction: Agnostic halfspace learning seeks a hypothesis whose error is close to that of the best halfspace, allowing improper output hypotheses.The approximation ratio is defined relative to Err_HALF(D), and efficient hypotheses must also be efficiently evaluable.
1 Introduction: Existing general-learning hardness results ruled out exact learning but did not exclude algorithms only slightly worse than the best halfspace.The paper highlights that prior results did not rule out a 1.001 approximation ratio.
1.3 Results: Under the random K-XOR refutation assumption, no polynomial-time algorithm has non-trivial performance on η-almost-realizable binary distributions for any constant η > 0.The result applies to distributions supported on {±1}^n × {±1}.
1.3 Results: Under a stronger assumption permitting poly-logarithmic K, hardness extends to η = 2^-log^(1-ν)(n) for every ν > 0.This yields hardness against approximation ratios of 2^log^(1-ν)(n).
1.3 Results: The results imply that no efficient algorithm achieves a constant approximation ratio under the basic assumption or a 2^log^(1-ν)(n) ratio under the stronger one.The paper states that these bounds substantially improve earlier results showing only hardness of exact learning.
1.3 Results: The same hardness extends to large-margin learning and statistical-query algorithms, and is stronger than prior lower bounds for proper learning.The statistical-query result is unconditional, while the main computational results rely on random K-XOR assumptions.

2 Main proof ideas

The proof reduces hardness of distinguishing nearly realizable halfspace samples from strongly scattered samples to the difficulty of refuting random K-XOR formulas. A sequence of reductions amplifies completeness, randomizes labels, and replaces the XOR hypothesis class with halfspaces.

Methodology: The framework argues that distinguishing small-error samples from strongly scattered samples is hard, which rules out efficient non-trivial learning of halfspaces.The learner’s output is tested on the sample to distinguish the two cases.
Intermediate hardness: For every K > 4, hardness of refuting random K-XOR formulas yields no efficient learner with non-trivial performance on 2/100-almost-realizable distributions over {−1,1,0}^n × {±1}.The proof obtains this intermediate theorem before extending the result to the full theorem.
Replacing HK by HALF: The XOR hypothesis class HK contains functions hψ that evaluate each K-tuple constraint under an assignment ψ, but the target reduction must measure error against halfspaces.This mismatch motivates the subsequent scattering and embedding reductions.
From XOR to learning: The reduction maps random K-XOR instances to strongly scattered samples while preserving the error of the XOR-induced hypotheses.Randomly flipping the first literal and changing labels preserves each hψ’s error.
Final reduction: The final reduction tests pseudo-randomness, outputs “not-random” when the test fails, and otherwise maps each constraint through χ into a Boolean-cube sample.Random inputs produce strongly scattered outputs, while low-error inputs produce outputs with small halfspace error.

A.1 Pseudo-random formulas

The appendix defines pseudo-random formulas by requiring frequencies of partial K-tuples to approximate their random expectations. Concentration and a union bound show that random formulas satisfy these conditions with high probability, and pseudo-randomness transfers to near-uniform evaluations under every assignment.

Definitions: A partial K-tuple fixes literals in a subset A of coordinates and leaves all remaining coordinates equal to ∗.Its size is |A|, and Xn,K,A denotes the collection supported on A.
Frequency control: For a partial tuple C supported on t coordinates, its random frequency has expectation 1/|Xn,K,A|.This frequency is an average of m independent Bernoulli variables.
Frequency control: Hoeffding’s bound controls deviations of every partial-tuple frequency from its expectation, and a union bound extends the control to all partial tuples.The resulting condition defines τ-pseudo-randomness.
High-probability property: A random formula is not τ-pseudo-random with probability at most (2n)^(2K^2) exp(...).The supplied passage truncates the exponential term, but states the polynomial prefactor and exponential form.
Evaluation distributions: If J is (t,τ)-pseudo-random, then for every assignment ψ, the evaluation distribution D(J,ψ) is (t,ntτ)-close to uniform.This transfers combinatorial frequency control into distributional pseudorandomness.

A.2 Approximately realizing assignments by polynomials

The proof uses pseudo-randomness to show that, for every assignment, XOR evaluations on K-tuples can be approximately represented by a low-degree polynomial. Indicator-vector embeddings and composition transfer the polynomial representation back to the original formula domain.

Polynomial realization: For a pseudo-random formula and assignment ψ, the map C ↦ XOR(C(ψ)) is approximately realized by a low-degree polynomial on most K-tuples.The polynomial is constructed after representing K-tuples as concatenated indicator vectors.
Embedding: The indicator embedding π(C) concatenates K vectors, with each vector recording the signed literal associated with one coordinate of C.This represents each K-tuple as a vector in {0,−1,1}^{nK}.
Polynomial construction: A distribution close to uniform admits a degree-≤d polynomial that approximates XOR under conditions relating K, d, and the closeness parameter.The construction first represents XOR as a function of the sum of its coordinates and interpolates it on at most d+1 values.
Parameter conditions: The approximation conditions require d ≤ t together with bounds on the distributional error and polynomial degree parameters.These conditions are used to apply the pseudo-randomness-to-polynomial transfer.
Composition: The linear map T sends the embedded tuple to the evaluations of its K literals under ψ.For every C, T(π(C)) = C(ψ), so composing with the polynomial on evaluations yields a polynomial on embedded tuples.

Step I: Amplifying the gap – from XOR to majority of XORs

The first amplification step replaces XOR constraints with majorities of groups of random XOR constraints, pushing completeness toward one while preserving the distinction between random and high-value instances. A subsequent randomization step balances labels without changing the optimum value.

Amplification: Each MXOR constraint is a majority of q random XOR constraints, producing q-ary bundles from the original K-XOR formula.The construction randomly samples and partitions tuples into ordered bundles.
Completeness and soundness: If J is random, the bundled formula J′ is also random.This preserves the random side of the distinguishing problem after amplification.
Completeness and soundness: When VALXOR(J) ≥ 1−η, a random bundle has overwhelmingly small probability of making most constituent XOR constraints evaluate to −1 under a near-optimal assignment.The bound is obtained using Lemma A.8.
Amplified problem: The amplified problem distinguishes random formulas from formulas with value at least 1−η and is used to reduce XORK to a CSP problem.The definition specifies efficient randomized algorithms for this distinction.
Label randomization: Randomly replacing each bundled constraint by either its original labeled version or a first-literal-flipped version preserves every assignment’s MXOR value.Thus high-value instances remain high-value while the resulting instances become suitable for the scattering step.

Step III: Enforcing pseudo-randomness

The reduction tests whether an input formula is pseudo-random and uses this test to distinguish random formulas from formulas with sufficiently large satisfiable value. Under the pseudo-randomness condition, random inputs produce the desired instance with probability 1−o_n(1).

A labeled formula is called (t,τ)-pseudo-random when the K-formula formed by its appearing K-tuples has that property.
The reduction checks whether the input is pseudo-random, declaring it non-random when the check fails.
For VAL_M XOR(J)≥η, the procedure either declares J non-random or produces the target output.
Random labeled formulas are sampled uniformly from the (t,τ)-pseudo-random formulas, with tuples and labels chosen independently and uniformly.
When J is random, the procedure produces an instance with probability at least 1−o_n(1).

Step IV: From MXOR to polynomials

This step maps labeled MXOR formulas to samples over {−1,1,0} coordinates and constructs a low-degree polynomial when the formula is nearly satisfiable. The resulting polynomial classification errs on only a small fraction of samples.

The target problem distinguishes strongly scattered samples from samples having polynomial error at most η.
The reduction maps each labeled formula constraint to a sample point π(C_i) with its original label y_i.
If J is random, the resulting sample S is scattered; if VAL_M XOR(J)≥1−η, a degree-≤d polynomial has error at most η′.
A satisfying assignment for at least 1−η of J’s tuples yields a degree-≤d polynomial matching the corresponding XOR values on 1−2·exp(...) of the relevant K-tuples.
The constructed polynomial p′ evaluates the encoded constraints, and its sign disagrees with their labels on at most η+2^q·exp(...) of the samples.

Step V: From polynomials to halfspaces

The reduction converts low-degree polynomial threshold instances into ordinary halfspace instances while preserving the relevant error and scatteredness properties. It does so through a polynomial feature map followed by a ternary-to-binary encoding.

Together, the maps reduce distinguishing strongly scattered binary samples from samples with Err_HALF(S)≤η to the corresponding polynomial problem.
The first map ρ embeds each ternary input into coordinates indexed by degree-≤d monomials, representing degree-≤d polynomials linearly.
For the intermediate sample, polynomial and halfspace errors coincide: Err_POL_{u,d}(S)=Err_HALF(ρ(S)).
The second map Ψ replaces each ternary coordinate by two binary coordinates, producing a sample in {±1}^{2(u+1)d}×{±1}.
The binary encoding preserves the scatteredness property of the sample.

Connecting the dots

The reductions connect hardness of distinguishing MXOR instances to hardness of learning halfspaces on almost-realizable binary distributions. The resulting lower bounds include arbitrarily small constant error levels and, under a stronger assumption, a subexponential-in-logarithm level.

Hardness for XOR formulas is reduced to the polynomial-scattering problem and then to HALF by discarding selected random examples when necessary.
The degree d is chosen subject to d=o(r) and d=ω(1), with the exact choice depending on the starting assumption.
No efficient learner can return a hypothesis with non-trivial error on a distribution supported on {±1}^{n′}×{±1} that is η′-almost realizable by halfspaces.
Because K can be arbitrarily large in the constant-K setting, η′ can be made arbitrarily small.
Under the stronger assumption with K=log^s(n), the construction achieves η′≤2^−log^{1−ν}(n′).

A.4 How to prove Theorems 1.4 and 1.5?

The extensions to Theorems 1.4 and 1.5 reuse the proof of Theorem 1.3 while adding theorem-specific verification or statistical-query requirements. For Theorem 1.5, the argument reduces uniform K-sparse-parity learning to agnostic halfspace learning through a query-preserving mapping.

Theorem 1.4: Theorem 1.4 follows the proof of Theorem 1.3 after verifying coefficient-sum and margin properties of the halfspace vector.The vector's coefficient sum must be polynomial in the dimension, and correct predictions must have inner product at least 1 in absolute value.
Theorem 1.5: Theorem 1.5 requires both statistical-query hardness of the starting problem and statistical-query implementability of every reduction step.The text presents this as an analogue of Theorem 1.3 and notes an SQ-hardness route via Feldman, Perkins, and Vempala.
Theorem 1.5: A simpler route reduces uniform K-sparse-parity learning to agnostic halfspace learning using a polynomial threshold approximation for XOR functions.For uniformly distributed x in {±1}^n, the parity learner receives examples (x,h(x)), where h computes the XOR of K unknown variables; the approximation agrees with h on all but a small fraction of examples.
Theorem 1.5: The reduction maps x to Ψ(x) and transforms each target query Q into Q̃(x,y)=Q(Ψ(x),y), allowing expectations to be evaluated through the original statistical-query oracle.The mapping has the form Ψ:{±1}^n→{±1}^{nr}, and the transformed query preserves the required expectation.