PaperlayerView exact revision on arXiv

Source-linked AI summary

From average case complexity to improper learning complexity

Amit Daniely, Nati Linial, Shai Shalev-Shwartz

arXiv:1311.2272v2cs.LGcs.CC

TL;DR

Learning theory lacks hardness results that match the best known algorithms, especially for improper learning, where standard NP-hardness reductions can fail. This paper introduces a methodology based on average-case hardness and derives hardness results for several hypothesis classes.

  • Problem

    Hardness results for basic learning problems lag behind algorithms, particularly for improper learning, because standard NP-hardness reductions may not apply.

  • Method

    The paper introduces a methodology for proving improper-learning hardness and combines it with the SRCSP assumption about refuting random constraint satisfaction problems.

  • Results

    The results establish hardness for learning DNF's, agnostically learning halfspaces with a constant approximation ratio, learning intersections of ω(1) halfspaces, and learning finite automata.

  • Takeaways & Limitations

    The paper extends hardness results for improper learning to multiple hypothesis classes using average-case complexity assumptions.

  • Takeaways & Limitations

    The SRCSP assumption is strong, and the stated halfspace-hardness argument does not allow its parameter K to grow with the dimension n.

Abstract

from arXiv · show

The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are efficiently learnable. There is presently a dearth of results showing hardness of learning problems. Moreover, the existing lower bounds fall short of the best known algorithms. The biggest challenge in proving complexity results is to establish hardness of {\em improper learning} (a.k.a. representation independent learning).The difficulty in proving lower bounds for improper learning is that the standard reductions from $\mathbf{NP}$-hard problems do not seem to apply in this context. There is essentially only one known approach to proving lower bounds on improper learning. It was initiated in (Kearns and Valiant 89) and relies on cryptographic assumptions. We introduce a new technique for proving hardness of improper learning, based on reductions from problems that are hard on average. We put forward a (fairly strong) generalization of Feige's assumption (Feige 02) about the complexity of refuting random constraint satisfaction problems. Combining this assumption with our new technique yields far reaching implications. In particular, 1. Learning $\mathrm{DNF}$'s is hard. 2. Agnostically learning halfspaces with a constant approximation ratio is hard. 3. Learning an intersection of $ω(1)$ halfspaces is hard.

1 Introduction

The paper addresses a persistent gap between learning algorithms and hardness results, especially for improper learning, by introducing an average-case reduction method based on random CSP hardness. Under a generalized Feige assumption, it derives hardness results for several fundamental learning classes.

  • 1 Introduction: Improper learning remains difficult to lower-bound because learners may output hypotheses outside the target class, defeating standard NP-hardness reductions.Existing lower bounds mainly use cryptographic assumptions, while the best known algorithms substantially outperform known hardness results.
  • 1 Introduction: The new methodology makes improper learning hard when distinguishing realizable samples from randomly generated unrealizable samples is hard.
  • 1 Introduction: Under a generalized Feige assumption about refuting random CSPs, the paper shows that learning DNF’s, finite automata, parity, and intersections of ω(1) halfspaces is hard.
  • 1 Introduction: Agnostic learning of halfspaces with a constant approximation ratio is hard, even over the boolean cube.
  • 1.1 Comparison to the cryptographic technique: Unlike cryptographic hardness proofs, the approach targets a concrete learning algorithm with a problem and distribution designed to defeat it, while CSP proximity constrains average-case reductions.
  • 1.2 On the role of average case complexity: Average-case hardness of CSPs extends earlier cryptographic and hardness-of-approximation consequences to fundamental PAC learning problems.

2 Preliminaries

The preliminaries define the learning models, CSP hardness notions, and proof-system framework used to state and analyze the paper’s reductions. They distinguish proper from improper learning and formalize average-case refutation of random CSP instances.

  • 2.1 Learning Theory: An efficient learner receives accuracy, confidence, and dimension parameters plus samples from an unknown distribution, and outputs an efficiently evaluable hypothesis.PAC learning requires low error on realizable distributions; agnostic learning compares error with the best hypothesis in the class, while approximate agnostic learning allows a multiplicative ratio.
  • 2.1 Learning Theory: A learner is proper if it always outputs a hypothesis in the target class and improper otherwise.
  • 2.2 Constraints Satisfaction Problems: A P-constraint applies a Boolean predicate to signed values of K distinct variables, and CSP(P) seeks an assignment maximizing the satisfied-constraint fraction VAL(J).
  • 2.2 Constraints Satisfaction Problems: Approximation resistance means that improving over the random-assignment baseline is NP-hard, with stronger variants requiring hardness even on satisfiable instances or for every predicate implied by P.
  • 2.2 Constraints Satisfaction Problems: The average-case problem CSPα,rand_m(n)(P) distinguishes instances with value at least α from random instances with m(n) constraints.For sufficiently many random constraints, random instances typically have value near VAL(P), making this an average-case analogue of approximation-gap CSP.
  • 2.3 Resolution refutation and Davis Putnam algorithms: Resolution refutations derive the empty clause from CSP constraints, and RES(J) records the shortest refutation length.Davis–Putnam-style algorithms recursively assign variables and implicitly produce resolution refutations, so proof-size lower bounds constrain their running time.

3 The methodology

The methodology converts average-case hardness of distinguishing random samples from realizable or almost-realizable samples into lower bounds for improper and agnostic learning. Its key insight is that an efficient learner can output only a limited set of hypotheses, which random samples are unlikely to fit.

  • 3 The methodology: Improper learning evades the standard NP-hardness reduction because a hypothesis outside H may fit an unrealizable sample despite no hypothesis in H doing so.This explains why hardness of proper learning does not automatically extend to improper learning.
  • 3 The methodology: A randomly generated unrealizable sample is likely to have large empirical error for every hypothesis an efficient learner might output.The learner’s outputs are determined by the observed examples and its random bits, so efficiency limits the number of possible outputs.
  • 3 The methodology: Theorem 3.2 rules out efficient learning when a scattered ensemble is hard to distinguish from realizable samples.For every c > 0, the condition requires an (n^c, β)-scattered ensemble under the stated indistinguishability assumption.
  • 3 The methodology: The proof tests a learner on samples by accepting when its returned hypothesis has empirical error at most β, separating realizable inputs from scattered random inputs.On random inputs, the possible outputs are bounded by |G| ≤ 2^(q(n)−n), while scattering makes the acceptance probability at most 2^−n.
  • 3 The methodology: Theorem 3.4 extends the argument to agnostic learning, ruling out approximation ratio α when scattered random samples are hard to distinguish from β-almost-realizable samples.The required scattering parameter is αβ + 1/n, and the theorem allows α ≥ 1.

4 The strong random CSP assumption

The paper proposes SRCSP, a strong random constraint-satisfaction assumption generalizing Feige’s assumption to broader predicates and super-linearly many constraints. It also identifies a SAT-restricted variant as a possible route toward weaker assumptions.

  • 4 The strong random CSP assumption: SRCSP generalizes Feige’s assumption and the Barak–Kindler–Steurer assumption to predicates beyond SAT3 and instances with super-linearly many constraints.The assumption is introduced to support lower bounds for improper learning through the methodology of Section 3.
  • 4 The strong random CSP assumption: The paper relates 0-variability to refutation complexity: random instances become trivially unsatisfiable at Ω(n^r) constraints but can require exponential resolution complexity at O(n^(c·r)) constraints.Here r = VAR0(P), and the exponential lower bound is stated for an absolute constant c > 0.
  • 4 The strong random CSP assumption: The first SRCSP component assumes that satisfiable CSP(P) instances are hard to distinguish from random instances with n^d constraints for predicates that are heredity approximation resistant.The required predicates also have sufficiently large 0-variability, captured by a function f(d).
  • 4 The strong random CSP assumption: The second component assumes hardness of distinguishing instances with value at least VAL(P) − ε from random instances with n^d constraints.It extends the random CSP hypothesis to much denser random instances and uses 0-variability to quantify the constraint regime.
  • 4.1 Toward weaker assumptions: The proposed SAT-restricted assumption asks whether satisfiable CSP(SAT_K) instances can be distinguished from random instances with n^d constraints only with hard computation.The authors view this restriction as promising because their learning reductions use only certain predicates, and prior work connects the SAT case to the broader assumption.

5 Summary of results

The paper derives hardness of improper learning from average-case-hard random CSPs, establishing results for DNFs, agnostic halfspace learning, and intersections of superconstant numbers of halfspaces. It also extends the framework to automata and parity and develops the reductions and complexity consequences supporting these results.

  • 5.1 Learning DNF’s: For every q(n) tending to infinity, learning DNF formulas with at most q(n) clauses is SRCSP-hard, extending hardness beyond constant-clause classes.Since DNFq(n) is contained in DNF_nq(n), the paper obtains SRCSP-hardness for DNFs of size at most n log(n).
  • 5.2 Agnostically learning halfspaces: For every constant α ≥ 1, it is SRCSP-hard to approximately agnostically learn HALFSPACES with an approximation ratio of α.
  • 5.3 Learning intersection of halfspaces: For every q(n) tending to infinity, learning intersections of at most q(n) halfspaces is SRCSP-hard.The class can be realized by simple neural networks, so the lower bound also implies hardness for corresponding improper neural-network learning problems.
  • 5.4 Additional results: The paper additionally proves SRCSP-hardness for learning polynomial-size finite automata and for agnostically learning parity with any constant approximation ratio.It also proves resolution-refutation lower bounds for random CSPs and rules out standard NP-hardness reductions to those random CSP problems unless the polynomial hierarchy collapses.
  • 5.5 On the proofs: The reductions translate hard random CSP instances into scattered-versus-realizable learning samples and then efficiently realize the resulting artificial classes with DNFs and related hypothesis classes.The DNF construction uses predicates whose CSP hardness persists under allowing both predicate and negated-predicate constraints; the same strategy yields the halfspace and parity results.

6 Future work

The paper identifies weaker assumptions, evidence for SRCSP, and additional learning applications as major directions for future work.

  • 6.1 Weaker assumptions?: Weaker assumptions than SRCSP are desirable, while a direct NP-hardness route to SRCSP-hard problems is argued to fail unless the polynomial hierarchy collapses.This motivates studying average-case complexity through assumptions rather than straightforward worst-case reductions.
  • 6.2 The SRCSP-assumption: Additional support for SRCSP could come from deriving it from weaker assumptions, analyzing more algorithms, and proving proof-complexity lower bounds beyond resolution.Existing evidence includes the inability of Davis–Putnam algorithms to refute SRCSP and limitations of basic SDP algorithms for related assumptions.
  • 6.3 More applications: The method and SRCSP leave open whether decision trees, large-margin halfspaces, parity, and constant-size halfspace intersections are SRCSP-hard.For halfspaces, the paper reports constant-ratio hardness but leaves a substantial gap between that result and the best known approximation ratio.
  • 6.3 More applications: The authors also seek applications of SRCSP beyond learning and approximation, including possible connections to cryptography and other areas of complexity theory.They describe such extensions as directions for future work rather than established consequences.

7 Proofs of the lower bounds

The lower-bound proofs reduce SRCSP-hard constraint problems to learning tasks by constructing scattered sample ensembles, with the DNF proof using the predicate H_k.

  • 7 Proofs of the lower bounds: The general proof strategy seeks a scattered ensemble D for which distinguishing realizable samples from D-random samples is SRCSP-hard.This criterion is then combined with the paper’s general reduction theorem.
  • 7.1 Learning DNFs: For learning DNFs, the proof uses the SRCSP assumption with Huang’s predicate H_k and its approximation-resistance properties.The construction also uses H_k’s 0-variability and a vector y_k that shifts positive instances outside H_k.
  • Lemma 7.2 ([27]): Since d is arbitrary, the theorem follows from Theorem 3.2.
  • Lemma 7.2 ([27]): The reduction transforms a CSP instance by changing variable signs in alternating constraints, then maps constraints into labeled examples.If the CSP is satisfiable, the resulting sample is realized by a DNF; random instances yield random samples under the constructed ensemble.

Claim 1

The halfspace construction encodes CSP constraints as paired examples and uses majority predicates to obtain SRCSP-hardness for constant-factor agnostic learning.

  • 7.2 Agnostically learning halfspaces: The auxiliary hypothesis class over {−1, 1, 0}^n is efficiently realized by ordinary halfspaces through coordinate duplication.The embedding preserves the relevant classifier values under the mapping Φ.
  • 7.2 Agnostically learning halfspaces: For odd K, the majority predicate has VAL(MAJ_K) = 1 − 1/(K+1) and VAR_0(MAJ_K) = (K+1)/2.These properties support the construction’s relationship between CSP value and agnostic error.
  • 7.2 Agnostically learning halfspaces: The resulting reduction proves that no efficient algorithm can approximately agnostically learn the induced halfspace class with any fixed constant approximation ratio unless SRCSP is false.The proof fixes α ≥ 1 and chooses β = 1/(10α) before applying the reduction.
  • 7.2 Agnostically learning halfspaces: The reduction maps each majority constraint to two oppositely labeled examples, producing random samples from random CSPs and almost-realizable samples from high-value CSP assignments.This connects CSP value gaps directly to agnostic learning gaps.

Claim 3

The paper’s broader conclusions establish constant-ratio hardness for agnostic halfspace learning while leaving the optimal approximation ratio unresolved and extending the discussion to margin-based learning.

  • Claim 3: Constant-factor agnostic learning of halfspaces is SRCSP-hard, based on distinguishing random samples from β-almost realizable samples.The proof concludes by combining the majority-predicate properties with the reduction from CSP instances.
  • Claim 3: The optimal approximation ratio remains open: the paper conjectures a substantially larger hardness scale, while the best known algorithms achieve n log(n).The conjectured larger scale is presented as an intuition rather than a proved result.
  • Claim 3: The broader approximation-ratio conclusions remain bounded by the fixed-K restriction in the SRCSP hypothesis and by the paper’s explicitly open status for a rigorous treatment.The proposed growth of K with n is not allowed by the stated SRCSP hypothesis.
  • Claim 3: The same proof shows hardness for approximately learning large-margin halfspaces with any constant approximation ratio.The discussion conjectures a ratio near 1/γ, whereas the best known algorithms achieve 1/√γ.

7.3 Learning automata

The paper transfers hardness from DNF learning to automata by efficiently realizing logarithmic-clause DNFs with polynomial-size acyclic automata.

  • 7.3 Learning automata: SRCSP-hardness extends to learning AUTOn^ε for every ε > 0.The proof reduces to learning DNFlog2(n) and realizes each such DNF with an automaton using n^2 + 1 states.
  • 7.3 Learning automata: The hardness theorem remains valid when the automata are restricted to be acyclic.This restriction uses the same proof.
  • 7.3 Learning automata: A DNF with log2(n) clauses is represented by an acyclic automaton with n^2 + 1 states.The automaton tracks, after each input variable, which clauses remain satisfied and accepts exactly when at least one clause survives.
  • 7.3 Learning automata: The construction maintains one state for each variable and subset of clause indices, plus a start state.After reading all variables, the tracked set contains the clauses satisfied by the input, so acceptance matches the DNF evaluation.

7.4 Toward intersection of 4 halfspaces

This section develops a route toward hardness for learning intersections of four halfspaces, conditional on a conjecture about a predicate P_k.

  • 7.4 Toward intersection of 4 halfspaces: The proof reduces the goal to finding a pairwise-uniform distribution supported on P−1(1), and constructs DQ as a pairwise-uniform distribution supported on Q−1(1).
  • 7.4 Toward intersection of 4 halfspaces: For a suitable threshold predicate T_k,l, the section reduces satisfiable-versus-low-value CSP instances from 3-SAT.A satisfiable 3-SAT instance maps to a satisfiable T_k,l instance, while low-value instances remain bounded away from full satisfiability.
  • 7.4 Toward intersection of 4 halfspaces: Conjecture 7.8 asserts that P_k is heredity approximation resistant on satisfiable instances.Under the unique games conjecture, the paper states that P_k is heredity approximation resistant and that distinguishing satisfiable instances from instances of value at most α is NP-hard for some constant α < 1.
  • 7.4 Toward intersection of 4 halfspaces: Assuming conjecture 7.8, learning INTER4 is SRCSP-hard.The reduction first establishes hardness for intersections of two halfspaces over a related domain, then transfers it to the boolean cube.
  • 7.4 Toward intersection of 4 halfspaces: The reduction maps each CSP constraint to one positive and one negative example with structured nonzero coordinates.If the CSP instance is satisfiable, the resulting sample is realized by four halfspaces determined by a satisfying assignment.

7.5 Agnostically learning parity

The paper gives an average-case hardness result for agnostic learning of parity, using parity CSP instances to create learning samples.

  • 7.5 Agnostically learning parity: For every constant α ≥ 1, approximately agnostically learning PARITY with approximation ratio α is SRCSP-hard.The result applies to the parity hypothesis class consisting of all functions χ_S over subsets S of the input coordinates.
  • 7.5 Agnostically learning parity: The reduction encodes each parity CSP constraint as a labeled example whose active coordinates are exactly the variables in that constraint.The label records the constraint’s parity offset, so satisfying assignments correspond to hypotheses that classify the examples correctly.
  • 7.5 Agnostically learning parity: The hardness reduction distinguishes β-almost realizable samples from random scattered samples.For sufficiently large predicate arity, the underlying parity CSP problem is hard on average, and the resulting learning samples inherit that distinction.
  • 7.5 Agnostically learning parity: A CSP assignment satisfying a 1 − β fraction of constraints yields a β-almost realizable learning sample.The hypothesis χ_S is correct on an example precisely when the corresponding parity constraint is satisfied.

8 Resolution lower bounds

The resolution-lower-bound argument combines a width-to-length theorem with structural properties of random CSP instances, proved through a two-part lemma.

  • 8 Resolution lower bounds: Resolution refutations of unsatisfiable CSP instances are exponentially long when their minimum refutation width is large.The section invokes Ben-Sasson and Wigderson’s theorem linking refutation length to width.
  • 8 Resolution lower bounds: Lemma 8.2 lower-bounds the width when every small constraint subset contains many variables appearing nowhere else in that subset.The proof uses this structural condition to show that small collections cannot imply the empty clause and that derived clauses must retain private variables.
  • Claim 4: Claim 4 bounds the number of original constraints needed to imply a derived clause and propagates this bound through resolution.The measure μ assigns each clause the minimum number of source constraints implying it, with μ increasing additively under resolution.
  • Claim 4: For suitable parameters, random constraint sets satisfy the structural condition of Lemma 8.2 with probability 1 − o_n(1).The proof controls repeated-variable events across randomly selected constraint sets and bounds failure probabilities by inverse powers of n.
  • Claim 4: The probabilistic argument excludes large collections with too many variable collisions by summing bounds over all candidate collections.A union bound combined with Stirling’s approximation yields the final high-probability estimate.

9 On basing the SRCSP assumption on NP-Hardness

The section shows that reductions from distinguishing random CSP instances from high-value instances imply statistical zero-knowledge proofs, and that NP-hardness or CoNP-hardness of this problem would collapse the polynomial hierarchy.

  • On yes inputs, the reduction produces a satisfiable or high-value CSP instance, whereas on no inputs it produces a random CSP instance with the same variable and constraint scale.The construction uses f(n) variables and C·f(n) constraints in the deterministic-machine formulation.
  • A reduction from any language L to distinguishing random CSP(P) instances from instances of value at least α implies that L has a statistical zero-knowledge proof.The result applies when the CSP has at least Cn constraints for a sufficiently large constant C.
  • A reduction from an NP-hard or CoNP-hard problem to this CSP distinction problem would collapse the polynomial hierarchy.The proof uses SZKP closure under complement and SZKP ⊂ CoAM to derive NP ⊂ CoAM.
  • The proof reduces L to an entropy-distinguishing problem for circuits, which is in SZKP when the output entropy is at most t−1 versus at least t.The circuit receives a uniform random input and outputs a CSP instance.
  • For sufficiently large C, random CSP instances have value at most α with probability at least 1/2, enabling an entropy gap between the two cases.The counting argument bounds the high-value instances by at most half of all instances, while random instances have entropy q(n)=m(f(n)) log2(2^K) up to the stated one-bit gap.
Loading 1311.2272v2…