Hardness of Learning 3-term DNF Formulae
The target can still be associated with 3-term DNF formulae even when the learner is not required to output a 3-term DNF formula.
The Representation Change
A hardness result is meaningful only when we identify exactly what learning task and what computation it concerns. For 3-term DNF formulae, the crucial distinction is between learning while staying inside the original representation and learning a target connected to that representation while allowing the algorithm to return a hypothesis from a different, possibly larger class.
The target can still be associated with 3-term DNF formulae even when the learner is not required to output a 3-term DNF formula.
Representation-Independent Learning
Representation-independent learning separates the original hypothesis class from the class used to produce the output. The learner is not required to return a hypothesis written in the original representation. The central requirement becomes that the returned hypothesis predicts well, rather than that it belongs exactly to the starting class.
In this setting, there are two different roles. The original class describes the representation used to state the learning problem. The output class describes the hypotheses the algorithm is permitted to return. If the output class is larger and easier to learn, the algorithm may be able to produce a useful predictor without reconstructing the target in its original form.
Separating the Two Classes
Suppose a learning problem is described using 3-term DNF formulae, but the representation-independent learner may return a hypothesis that is not a 3-term DNF formula.
- 1Identify the original class
The original class is the class of 3-term DNF formulae used to describe the target learning problem.
- 2Identify the output requirement
The learner is not required to express its answer using the same 3-term DNF representation.
- 3Identify the enlarged choice
The learner may choose a hypothesis from a larger class that is easier for the algorithm to use.
- 4Apply the actual success criterion
The relevant question is whether the returned hypothesis predicts well, not whether it belongs exactly to the original class.
The learning task has changed: it is no longer learning under the requirement that the output remain a 3-term DNF formula.
Why the Hardness Results Differ
What do you think happens?
If an earlier result says that learning within the 3-term DNF representation is hard, does that alone rule out efficient representation-independent learning?
Reveal answer
No, because the output class and the learning requirement may have changed.
The earlier and later claims concern different requirements. A representation-specific result requires the answer to remain in the original representation, while representation-independent learning allows a hypothesis that is not necessarily a 3-term DNF formula.
| Feature | Earlier representation-specific setup | Representation-independent setup |
|---|---|---|
| Target connection | The problem is described using 3-term DNF formulae | The problem remains connected to 3-term DNF formulae |
| Required output | The answer must use the original representation | The answer need not be a 3-term DNF formula |
| Main restriction | The learner must stay within the original class | The learner may use a larger output class |
| Reason the conclusions differ | The learning requirement is stricter | The learning requirement has changed |
The same target class can appear in two learning claims with different output requirements.
There is therefore no contradiction in saying both that learning within a particular 3-term DNF representation is hard and that efficient representation-independent learning is possible. The statements address different tasks. The second task relaxes the requirement that the answer be expressed in the original representation.
What Computational Hardness Means
A computationally hard learning problem is one in which carrying out the required computation is difficult. A hardness claim must specify which computation or learning requirement is difficult; it does not automatically mean that every possible learning method fails.
- 1Identify the object whose computation is claimed to be difficult.
- 2Ask whether the claim concerns one implementation or the learnability of the entire class.
- 3Check whether an additional argument connects the implementation difficulty to a stronger claim about learnability.
- 4Do not infer the stronger conclusion when that connecting argument has not been provided.
ERM Versus Learnability
Empirical risk minimization over H, written as ERM H, refers here to an implementation that seeks an empirical risk minimizer in the class H. The source makes a crucial logical distinction: computational hardness of implementing ERM H does not imply that H is not learnable. One particular procedure may be difficult even though another learning algorithm can learn the class.
Avoiding an Invalid Inference
A researcher shows that implementing ERM over H is computationally hard. What conclusion is justified, and what conclusion is not justified by that fact alone?
- 1State the demonstrated fact
The demonstrated fact concerns the computational difficulty of one implementation: ERM over H.
- 2State the limited conclusion
It is justified to say that this ERM implementation is computationally hard.
- 3Test the stronger conclusion
The claim that H is not learnable concerns all possible successful learning algorithms, not merely the ERM implementation.
- 4Look for the missing argument
A stronger non-learnability conclusion would require an additional argument connecting the hard ERM computation to the impossibility of efficient learning by any other algorithm.
Hardness of implementing ERM over H does not, by itself, prove that H is unlearnable.
| Question | ERM implementation | Learnability of H |
|---|---|---|
| What is being evaluated? | One specified computational procedure | Whether an efficient learning algorithm exists |
| Does the claim concern alternatives? | Not necessarily | Yes, it concerns the possibility of another algorithm |
| What follows from hardness? | That this implementation is difficult | A stronger conclusion requires an additional argument |
Implementation difficulty and class learnability are related questions, but they are not identical claims.
Cryptographic Hardness Arguments
Cryptographic assumptions can be used to support a proof that a learning problem is computationally hard. The source describes the proof pattern rather than a named construction or a complete formal reduction: if an efficient learner could uncover the relevant hidden information, that learner could be used to violate a cryptographic assumption.
| Learning | Cryptography |
|---|---|
| Attempts to uncover an underlying rule | Attempts to prevent discovery of a secret |
| Uses observed examples as information | Assumes information may be available while hidden information remains protected |
| An efficient learner could reveal structure | A successful attack would undermine the protection assumption |
The contrast between uncovering and hiding explains why cryptography can support a learning hardness argument.
Common Reasoning Errors
Common mistake Treating the original hypothesis class as the mandatory output class in every learning setup.
What it looks likeThe target is described by 3-term DNF formulae, so the learner must return a 3-term DNF formula.
Why it failsRepresentation-independent learning allows the algorithm to return a hypothesis that is not necessarily written in the original representation.
Do this insteadSeparate the class used to describe the target from the class from which the learner may choose its output.
Common mistake Claiming that efficient learning contradicts an earlier hardness result without comparing the requirements.
What it looks likeLearning connected to 3-term DNF formulae is efficient, so the earlier hardness result must be false.
Why it failsThe two results can concern different output requirements. One may require the original representation while the other permits a larger output class.
Do this insteadAsk whether the learner is required to stay inside the original representation before comparing the conclusions.
Common mistake Concluding that H is unlearnable because ERM over H is computationally hard.
What it looks likeThe exact empirical risk minimizer is difficult to compute, therefore no efficient learner can learn H.
Why it failsHardness of one implementation does not rule out another learning algorithm.
Do this insteadIdentify the additional argument needed to move from implementation difficulty to a claim about the learnability of the class.
Common mistake Using cryptography as if it automatically proves learning hardness.
What it looks likeCryptography hides secrets, so every related learning problem is hard.
Why it failsA hardness proof needs a specific connection showing that an efficient learner would violate a cryptographic assumption.
Do this insteadState the reduction direction: the hypothetical learner would uncover hidden information and thereby produce a cryptographic break.
Practice: Classify the Claim
Classify each statement as a claim about an implementation, a claim about a learning requirement, or a claim about the learnability of a class. Then explain whether the statement alone supports a conclusion that the class is unlearnable: ERM over H is computationally hard; the learner may output a hypothesis outside the 3-term DNF representation; an efficient learner would uncover information protected by a cryptographic assumption.
Hints
- An implementation claim concerns one specified computational procedure.
- A learning-requirement claim concerns what representations the learner is allowed to output.
- A cryptographic claim becomes relevant when an efficient learner can be transformed into a violation of an assumption.
A Precise Final Diagnosis
Explain why the following two statements can both be true: learning under the original 3-term DNF representation is hard, and representation-independent learning related to 3-term DNF formulae is efficient.
- 1Compare the representations
The first statement keeps the learner inside the original representation. The second allows the learner to return a hypothesis from a larger class.
- 2Compare the requirements
The first task requires a specific form of output, while the second focuses on obtaining a hypothesis that predicts well.
- 3Compare the conclusions
A hardness result for the stricter task does not automatically apply to the relaxed task.
The statements are compatible because they describe different learning requirements.
Summary
- 1Representation-independent learning separates the original hypothesis class from the class used to produce the learner's output.
- 2Allowing a larger output class can make efficient learning possible without contradicting a hardness result for the original representation.
- 3Computational hardness must identify the specific computation or learning requirement that is difficult.
- 4Hardness of implementing ERM over H does not by itself imply that H is unlearnable by every other algorithm.
- 5Cryptographic assumptions can support learning hardness arguments because an efficient learner might make hidden information discoverable.
At a glance
- Representation-independent learning changes the allowed output representation while keeping the learning problem connected to the original target class.
- Efficient learning of a target connected to 3-term DNF formulae is not contradictory to hardness under a stricter representation-specific requirement.
- A computationally hard ERM implementation does not automatically show that the entire hypothesis class is unlearnable.
- A valid hardness claim must identify its computational bottleneck and distinguish one method from all possible learning algorithms.
- Cryptography provides a useful contrast because learning attempts to uncover rules, whereas cryptography attempts to keep secret information hidden.