PaperlayerView exact revision on arXiv

Source-linked AI summary

Agnostic Learning of Monomials by Halfspaces is Hard

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

arXiv:1012.0729v1cs.CCcs.AIcs.LG

TL;DR

The paper asks whether agnostic learning of simple monomials remains tractable when hypotheses may be halfspaces. It combines moment-matching distributions, invariance principles, structural analysis of non-regular halfspaces, and Label Cover reductions to prove strong NP-hardness. The result also yields hardness for decision lists and avoids assuming the Unique Games conjecture.

  • Problem

    Agnostic learning must compete with the best concept in a class under arbitrary labeled-example distributions, raising the question whether monomials remain learnable when hypotheses may be halfspaces.

  • Method

    The proof uses moment-matching example distributions, invariance principles for regular halfspaces, critical-index structure for non-regular halfspaces, dictatorship tests, and a Label Cover reduction.

  • Results

    For every constant ε > 0, it is NP-hard to find a halfspace agreeing with (1/2 + ε) of examples when some monomial agrees with (1 − ε), implying hardness for proper agnostic learning of decision lists.

  • Takeaways & Limitations

    Weak agnostic learning of monomials is hard even with the substantially larger halfspace hypothesis class, and the result provides an NP-hardness route that avoids the Unique Games assumption.

Abstract

from arXiv · show

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\eps)$ of the examples, it is NP-hard to find a halfspace that is correct on $(1/2+\eps)$ of the examples, for arbitrary constants $\eps > 0$. In learning theory terms, weak agnostic learning of monomials is hard, even if one is allowed to output a hypothesis from the much bigger concept class of halfspaces. This hardness result subsumes a long line of previous results, including two recent hardness results for the proper learning of monomials and halfspaces. As an immediate corollary of our result we show that weak agnostic learning of decision lists is NP-hard. Our techniques are quite different from previous hardness proofs for learning. We define distributions on positive and negative examples for monomials whose first few moments match. We use the invariance principle to argue that regular halfspaces (all of whose coefficients have small absolute value relative to the total $\ell_2$ norm) cannot distinguish between distributions whose first few moments match. For highly non-regular subspaces, we use a structural lemma from recent work on fooling halfspaces to argue that they are ``junta-like'' and one can zero out all but the top few coefficients without affecting the performance of the halfspace. The top few coefficients form the natural list decoding of a halfspace in the context of dictatorship tests/Label Cover reductions. We note that unlike previous invariance principle based proofs which are only known to give Unique-Games hardness, we are able to reduce from a version of Label Cover problem that is known to be NP-hard. This has inspired follow-up work on bypassing the Unique Games conjecture in some optimal geometric inapproximability results.

1 Introduction

The paper proves that agnostic learning of monomials remains NP-hard even when the learner may output halfspaces, and derives corresponding hardness for decision lists. Its result extends prior hardness work while avoiding reliance on the Unique Games conjecture.

  • Main result: Theorem 1.1 shows that, for any constant ε > 0, finding a halfspace agreeing with (1/2 + ε) of Boolean examples is NP-hard even when a monomial agrees with (1 − ε).The agreement is measured on the given examples; agreement rate 1/2 is trivially achievable.
  • Consequences: Because monomials are contained in decision lists and decision lists are contained in halfspaces, the result implies optimal hardness for proper agnostic learning of decision lists.
  • Relation to prior work: The hardness subsumes prior results on maximum agreement for halfspaces, monomials, and decision lists, while excluding only the result for learning monomials by t-CNFs.
  • Beyond Unique Games: Unlike earlier invariance-principle proofs yielding only Unique-Games hardness, the reduction uses a uniquely-on-average Label Cover variant known to be NP-hard.
  • Noise model: The result separates agnostic learning from more benign noise settings: the earlier positive results do not extend to any constant adversarial noise rate ε > 0.
  • Proof framework: The paper’s hardness proof uses a dictatorship-test and Label Cover framework, with Boolean halfspaces defined as threshold functions of weighted variables.

2 Proof Overview

The proof reduces k-Label Cover to agnostic learning of monomials by designing a dictatorship test whose completeness comes from consistent labelings and whose soundness decodes any successful halfspace into a violated Label Cover structure. Matching moments and the invariance principle handle regular halfspaces, while critical-index structure handles non-regular ones; the reduction ultimately yields NP-hardness without assuming the Unique Games Conjecture.

  • Completeness: A strongly satisfiable Label Cover instance supplies a disjunction agreeing with labels on at least 1−ε of generated examples.The reduction constructs examples so every consistently labeled edge has a corresponding high-agreement disjunction.
  • Reduction: The reduction encodes vertex labelings as disjunctions over one block of R Boolean coordinates per vertex.A labeling Λ: V → [R] determines a disjunction over {0,1}^{|V|×R}.
  • Soundness: If a halfspace agrees on at least 1/2+ε of examples, a decoding procedure produces a labeling that weakly satisfies an edge with non-negligible probability.This decoding property is the soundness bridge from successful learning to Label Cover satisfaction.
  • Dictatorship test: The dictatorship test is complete for shared dictators and sound because acceptance above 1/2+ε forces two linear functions close to the same dictator.The test queries k linear functions once each and accepts according to their combined halfspace value.
  • Soundness analysis: Critical-index analysis identifies a small set of influential coordinates, while moment matching and invariance prevent regular halfspaces from distinguishing the test distributions.For a halfspace passing the test, the analysis forces overlap between critical-index sets of two rows.
  • Hardness consequence: Using a Label Cover variant with unique-on-average projections makes the hardness result NP-hard rather than merely Unique-Games-hard.The construction therefore establishes the theorem under P ≠ NP, and De Morgan’s law transfers the disjunction formulation to monomials.

3 Preliminaries

The preliminaries introduce critical-index structure for analyzing halfspaces and an invariance principle for comparing linear forms under moment-matched ensembles. Together, these tools support the later separation of regular and highly non-regular halfspaces.

  • Critical Index: The critical index is the first ordered coordinate whose magnitude is at most τ times the remaining ℓ2 norm.If no such coordinate exists, the critical index is infinite; critical index one corresponds to a τ-regular vector.
  • Critical Index: A large critical index implies a geometrically decreasing subsequence, with weights shrinking by a factor of at least three after sufficiently many positions.The bound applies when the index gap exceeds (4/τ^2) ln(1/τ).
  • Regular halfspaces: For τ-regular weight vectors, the preliminaries establish small-interval bounds for weighted sums under a randomized smoothing of a distribution.The smoothing independently replaces coordinates by random bits with probability γ.
  • Critical Index: Deleting the coordinates in Cτ(w), the largest coordinates through the critical index, makes w τ-regular.Cτ(w) is defined as Hcτ(w), the set of coordinates removed to obtain regularity.
  • Supporting constructions: The truncation and smoothing constructions provide the analytic mechanisms for replacing or deleting coordinates while controlling the resulting weighted sums.These definitions and lemmas prepare the regularity-based soundness analysis.
  • Invariance Principle: The invariance principle compares linear functions evaluated on independent bounded ensembles whose corresponding variables match moments through degree three.It is formulated using a fourth-derivative-bounded test function and a spread function controlling the comparison.

4 Construction of the Dictatorship Test

The dictatorship test uses carefully constructed distributions with matching low-degree moments, then shows that halfspaces lacking shared influential coordinates cannot distinguish the test’s two cases. Completeness comes from dictator-like structure, while soundness is established through invariance and critical-index truncation.

  • Moment-matching distributions: The test is built from distributions D0 and D1 on {0, 1}^k whose moments match through degree 4.Their noisy versions also retain matching moments through degree 4, including after suitable conditioning.
  • Test construction: The test samples a random label bit, generates a hypercube vector from the corresponding distribution, adds noise, and accepts when the halfspace output matches the bit.The construction can equivalently be viewed as mixing negative and positive samples from noisy distributions.
  • Reduction role: The resulting dictatorship test supplies the completeness and soundness properties needed for the subsequent Label Cover reductions.The paper first describes the Unique Label Cover reduction and then removes the Unique Games assumption using smooth k-Label Cover.
  • Soundness: If critical-coordinate sets of the halfspace’s component vectors are disjoint, invariance implies that its acceptance behavior differs between the two noisy distributions by O(1/k).The proof conditions on selected coordinates, uses moment matching through degree 3 after conditioning, and applies the invariance principle.
  • Soundness: A halfspace that passes with high probability therefore yields intersecting coordinate lists, while a structural lemma permits truncating vectors with large critical index to their top t coordinates.This converts influential-coordinate structure into a bounded list-decoding argument.

5 Reduction from Label Cover

The paper removes the Unique Games assumption by reducing from a smooth k-Label Cover problem whose hardness is known under P ≠ NP. The reduction distinguishes strongly satisfiable instances from instances with very limited weak satisfaction.

  • Reduction framework: The reduction from smooth k-Label Cover yields Theorem 1.1 without assuming the Unique Games Conjecture.It targets agnostic learning of disjunctions by halfspaces.
  • Source hardness: The source problem is NP-hard to distinguish between instances with a labeling strongly satisfying every hyperedge and instances lacking a sufficiently weakly satisfying labeling.The theorem specifies the hard gap using the stated parameters M, N, and γ.
  • Source hardness: The k-Label Cover instances additionally satisfy smoothness and bounded projection-preimage properties.These properties constrain how labels project across randomly selected incident hyperedges.

5.2 Reduction from Smooth k-Label Cover

The smooth k-Label Cover reduction constructs a labeled-example distribution by grouping coordinates according to projection relationships. Coordinates associated with equal projected labels become almost identical copies, enabling the dictatorship-test analysis.

  • Reduction construction: Starting from a smooth k-Label Cover instance, the reduction in Figure 5.2 produces a random labeled example distribution E.The construction uses the instance’s projection maps to organize the coordinates of each example.

5.3 Proof of Theorem 1.1

The proof establishes Theorem 1.1 by combining completeness and soundness properties of a Label Cover reduction, then choosing k = O(1/ε^2) to obtain the stated hardness result.

  • Completeness: A strongly satisfiable smooth k-Label Cover instance yields a disjunction agreeing with a random example with probability at least 1 − O(1/⋯).The construction uses a disjunction based on the strongly satisfying labeling.
  • Soundness: If the instance is not 2k^2 2−γk-weakly satisfiable, no halfspace agrees with a random example with probability exceeding the soundness bound.This is the soundness property asserted for smooth instances with specified parameters J and d.
  • Conclusion: Combining the reduction theorem with Theorem 5.1 and taking k = O(1/ε^2) yields Theorem 1.1.The parameter choice converts the reduction's completeness and soundness gap into the main hardness statement.
  • Proof structure: The soundness analysis is the more complicated part of the proof and is deferred to Section 5.4.The paper separates the completeness proof from the detailed soundness argument.

5.4 Soundness Analysis

The soundness proof handles halfspaces by separating regular and concentrated coefficients, exploiting smooth Label Cover structure, moment matching, and invariance-based bounds to derive the final approximation limit.

  • Structural preparation: Most hyperedges are 2τ-nice, allowing the soundness analysis to control how influential coordinates project across vertices.Lemma 5.4 states that at least 1 − O(1/k) of hyperedges are 2τ-nice.
  • Hyperedge analysis: For a fixed nice hyperedge, the proof analyzes the probability that a halfspace agrees with a random example restricted to that hyperedge.The analysis introduces projected coordinates and decomposes the halfspace's weights relative to influential coordinate sets.
  • Moment matching: The ensembles A and B match moments through degree 3, enabling the invariance principle to compare their behavior under a regular linear function.The proof conditions on shared coordinates, establishes a spread property, and then applies the invariance principle.
  • Non-regular halfspaces: For non-regular halfspaces, the proof truncates influential coordinates and adjusts the threshold, using concentration bounds to control the approximation error.The truncation keeps selected top coordinates while replacing the remaining contribution by a conditional mean.
  • Global soundness: The resulting per-edge agreement bound combines with a labeling strategy to contradict Label Cover soundness when a halfspace exceeds the permitted agreement.The final propositions state the global halfspace bound and the contradiction with weak satisfiability.

A Probabilistic Inequalities

This appendix collects standard concentration and normal-approximation inequalities used in the paper's probabilistic arguments.

  • Hoeffding’s inequality: Hoeffding’s inequality bounds sums of independent real variables with bounded individual ranges.The variables need not share the same interval, provided each lies within its specified bounds.
  • Berry–Esseen theorem: Berry–Esseen’s theorem compares normalized sums of independent unbiased ±1 variables with a unit Gaussian.The theorem applies under a bound on the largest coefficient.
  • Chebyshev’s inequality: Chebyshev’s inequality bounds the probability that a random variable deviates from its mean by more than a specified threshold.The bound depends on the variable's variance and the chosen deviation level.

B Proof of Lemma 3.3

The proof of Lemma 3.3 studies a noisy weighted sum by conditioning on which coordinates were randomized, then combines concentration and Berry–Esseen bounds to control interval probabilities.

  • Noise decomposition: Each coordinate is generated either as a copy of x(i) or as an independent random bit, and z records which generation occurred.The weighted sum is written as S = Σ_i w(i)y(i).
  • Combining the bounds: The probability that S lies in an interval is decomposed by conditioning on a high-probability event and its complement.This combines the two claims through the indicator-function expression for interval membership.
  • Concentration claims: Claim B.1 uses Hoeffding’s inequality to control the contribution from randomized coordinates.The proof applies the bounded-range inequality to squared-weight terms.
  • Normal approximation: Claim B.2 applies Berry–Esseen to the independent unbiased coordinates after splitting the weighted sum into independent parts.The approximation is used after conditioning on the randomization pattern.

C Proof of Invariance Principle (Th. 3.10)

The proof establishes an invariance principle for linear functions over independent ensembles whose corresponding variables are bounded and match moments through degree 3. A smooth approximation to the positive-part function, Taylor expansion, and moment matching bound the difference between evaluations on the two ensembles.

  • The ensembles A and B are independently structured, bounded by 1, and have matching moments up to degree 3 coordinatewise.
  • The linear function l combines coefficient vectors l{i} with the corresponding ensemble blocks, and the spread function c(α) captures its regularity.
  • The proof replaces blocks from B with blocks from A one at a time, comparing the resulting intermediate random inputs Xi and Xi−1.
  • Taylor expansion through the matching third moments leaves higher-order terms, which are bounded using K-boundedness and coefficient norms.
  • The resulting bound controls the inner expectation and therefore the target expression, with the displayed estimate involving K and ∥l{i}∥1^2.
  • A smooth function Φα approximates pos while differing only within an α-neighborhood of the threshold θ.

D Hardness of Smooth k-Label Cover

This section constructs and analyzes smooth k-Label Cover instances from bipartite Label Cover. Completeness is preserved, while soundness and projection smoothness support the NP-hardness reduction.

  • The starting bipartite Label Cover is W-side regular and uses projection functions between labels on the two vertex parts.
  • The resulting Label Cover parameters and distinguishing gap are NP-hard for the stated integer parameters.
  • The reduction keeps V as the vertex set, samples k-tuples of neighbors of each w, and assigns the corresponding projections to each generated hyperedge.
  • If the original instance is fully satisfiable, restricting its labeling to V makes every generated hyperedge consistent.
  • Soundness: A weakly satisfying labeling of the smooth instance can be extended to W by assigning each w its most frequently recommended label.
  • Soundness: The extension would satisfy a sufficiently large edge fraction, contradicting the assumed soundness bound when the smooth instance has too many weakly satisfied hyperedges.
  • Smoothness: Smoothness follows because selecting a projection in the constructed instance is equivalent to randomly selecting a neighbor in the original regular bipartite graph.
Loading 1012.0729v1…