Hardness of Learning 3-term DNF Formulae
Representation independent learning separates the original hypothesis class from the class used to produce the output.
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.
Identify the original class: The original class is the class of 3-term DNF formulae used to describe the target learning problem.
Identify the output requirement: The learner is not required to express its answer using the same 3-term DNF representation.
Identify the enlarged choice: The learner may choose a hypothesis from a larger class that is easier for the algorithm to use.
Apply 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
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 |
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.
- Identify the object whose computation is claimed to be difficult.
- Ask whether the claim concerns one implementation or the learnability of the entire class.
- Check whether an additional argument connects the implementation difficulty to a stronger claim about learnability.
- Do 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?
State the demonstrated fact: The demonstrated fact concerns the computational difficulty of one implementation: ERM over H.
State the limited conclusion: It is justified to say that this ERM implementation is computationally hard.
Test the stronger conclusion: The claim that H is not learnable concerns all possible successful learning algorithms, not merely the ERM implementation.
Look 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 |
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 |
Common Reasoning Errors
Treating the original hypothesis class as the mandatory output class in every learning setup.
Representation-independent learning allows the algorithm to return a hypothesis that is not necessarily written in the original representation.
Fix:
Separate the class used to describe the target from the class from which the learner may choose its output.Claiming that efficient learning contradicts an earlier hardness result without comparing the requirements.
The two results can concern different output requirements. One may require the original representation while the other permits a larger output class.
Fix:
Ask whether the learner is required to stay inside the original representation before comparing the conclusions.Concluding that H is unlearnable because ERM over H is computationally hard.
Hardness of one implementation does not rule out another learning algorithm.
Fix:
Identify the additional argument needed to move from implementation difficulty to a claim about the learnability of the class.Using cryptography as if it automatically proves learning hardness.
A hardness proof needs a specific connection showing that an efficient learner would violate a cryptographic assumption.
Fix:
State 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.
Compare 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.
Compare the requirements: The first task requires a specific form of output, while the second focuses on obtaining a hypothesis that predicts well.
Compare 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
- Representation-independent learning separates the original hypothesis class from the class used to produce the learner's output.
- Allowing a larger output class can make efficient learning possible without contradicting a hardness result for the original representation.
- Computational hardness must identify the specific computation or learning requirement that is difficult.
- Hardness of implementing ERM over H does not by itself imply that H is unlearnable by every other algorithm.
- Cryptographic assumptions can support learning hardness arguments because an efficient learner might make hidden information discoverable.
Key Takeaways
- 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.