Computational Complexity of Training Neural Networks
Approximate ERM can remain computationally infeasible.
The tempting relaxation
Training is often described as an optimization problem: find weights that minimize the empirical error on the available training data. A natural response to a difficult optimization problem is to relax the requirement. Instead of demanding the exact best weights, we might accept weights whose empirical error is only close to the smallest possible value. The important lesson is that this relaxation does not automatically make training computationally feasible. Approximate empirical-risk minimization can remain computationally infeasible.
Following the optimization goal
Exact success versus approximate success
Consider two possible training requirements for the same hypothesis class. Requirement A asks for weights with the smallest possible empirical error. Requirement B accepts weights whose empirical error is close to that smallest value.
Start with the exact requirement: Requirement A asks the training procedure to identify an exact empirical-risk minimizer. This is the strongest optimization target.
Relax the target: Requirement B permits a small gap between the error of the returned weights and the smallest possible empirical error. This changes the quality requirement, but it does not by itself provide an efficient way to find the weights.
Apply the hardness lesson: The source states that computational hardness can survive this relaxation. Therefore, accepting nearly minimal empirical error is not a guaranteed escape from computational difficulty.
A weaker optimization target can still have an infeasible search problem.
Optimization quality and computational tractability are different questions. Near-minimal empirical error describes how good the returned weights are. Computational tractability describes whether those weights can be found efficiently. Improving the first requirement does not necessarily resolve the second.
Why architecture changes may not help
Once a hardness result is known for one network structure, it is natural to ask whether another architecture could make empirical-risk minimization efficient. A similar question arises when replacing the activation functions with other efficiently computable choices, such as sigmoids. The source presents a broader obstruction: under a stated cryptographic assumption, learning intersections of halfspaces is hard even in a representation-independent model of learning.
This matters because a hardness result need not be tied to one particular network design. If the difficult target concept is present in a broader hypothesis class, then changing the surrounding representation may not remove the underlying barrier. The issue is not merely that one selected architecture has an inconvenient optimization procedure. The broader learning problem itself can remain hard.
Representation-independent consequences
A representation-independent hardness result is a hardness result stated without restricting the learner to one particular representation. In this source, the result says that, under the stated cryptographic assumption, learning intersections of halfspaces is hard in a representation-independent model.
The consequence for specific neural-network representations is direct. Every hypothesis class that contains intersections of halfspaces cannot be learned efficiently under that same assumption. Therefore, if a particular architecture or activation-based representation contains those concepts in its hypothesis class, the representation-independent hardness result applies to that specific class as well.
| Question | What the hardness result tells us |
|---|---|
| Is one architecture difficult to train? | It may be, but a result limited to that architecture does not by itself address every other representation. |
| Could another representation avoid the barrier? | A representation-independent result gives a broader obstruction. |
| What if a specific hypothesis class contains intersections of halfspaces? | Under the stated cryptographic assumption, that class cannot be learned efficiently. |
How the scope of a hardness result affects its consequences
Tracing a training claim
Evaluating a proposed escape route
A researcher argues: exact empirical-risk minimization is difficult for one neural-network architecture, so the researcher will use a different architecture, replace the activation function with a sigmoid, and accept weights with nearly minimal empirical error. What should you conclude from the source?
Check the objective: Accepting nearly minimal empirical error is a relaxation from exact empirical-risk minimization. The source warns that computational hardness can survive this relaxation.
Check the representation: Changing the architecture or using another efficiently computable activation function changes the representation being considered, but it does not automatically eliminate a hardness barrier.
Check the scope of the result: A representation-independent hardness result is broader than a result for one architecture. Under the stated cryptographic assumption, it applies to every hypothesis class containing intersections of halfspaces.
State the correct conclusion: The proposed changes may alter the model and the optimization target, but the source does not justify concluding that training has become efficiently solvable.
The escape route is not guaranteed to work: approximate optimization and representation changes can both leave the computational hardness intact.
Common reasoning mistakes
Assuming that approximate ERM is automatically easy.
The source explicitly states that computational hardness can survive the relaxation from exact to approximate empirical-risk minimization.
Fix:
Treat approximate ERM as a potentially different but still computationally infeasible task.Assuming that a new architecture automatically removes a hardness result.
Hardness results can apply beyond one particular neural-network architecture.
Fix:
Ask whether the broader hardness result applies to the hypothesis class represented by the new architecture.Treating an efficiently computable activation function as proof of efficient learning.
Efficiently computing an activation function does not by itself establish that the overall learning problem can be solved efficiently.
Fix:
Separate the cost of evaluating a representation from the computational difficulty of learning the represented hypothesis class.Ignoring the containment condition in the representation-independent result.
The source gives the consequence for hypothesis classes that contain intersections of halfspaces.
Fix:
State the result with its condition: under the assumption, every hypothesis class containing intersections of halfspaces cannot be learned efficiently.
Practice and takeaways
A training proposal makes three changes: it seeks weights with nearly minimal empirical error instead of exact minimum error, uses a different neural-network architecture, and replaces its activation function with another efficiently computable choice. Explain why these changes do not, by themselves, establish efficient learnability. Your answer should mention approximate ERM, representation changes, and the representation-independent hardness result.
Hints
- Begin by distinguishing the quality of a solution from the difficulty of finding it.
- Then explain why changing an architecture or activation function may not remove a broader learning barrier.
- Finish by stating the implication for a hypothesis class containing intersections of halfspaces.
- The difficulty of neural-network training is not limited to finding the exact empirical-risk minimizer. Even a relaxed goal, such as finding weights with nearly minimal empirical error, can remain computationally infeasible. Changing the architecture or activation function may change the representation without removing the underlying hardness. A representation-independent result is especially strong: under the stated cryptographic assumption, every hypothesis class containing intersections of halfspaces cannot be learned efficiently.
Key Takeaways
- Approximate empirical-risk minimization can remain computationally infeasible.
- A nearly optimal error value does not guarantee that the corresponding weights can be found efficiently.
- Changing a neural-network architecture or activation function does not automatically remove a learning-theoretic hardness barrier.
- Representation-independent hardness applies broadly and therefore transfers to every specific hypothesis class that contains intersections of halfspaces, under the stated cryptographic assumption.