Neural Network Architectures and Activation Functions
Approximate ERM can remain computationally infeasible.
The tempting escape route
Suppose training a neural network means finding weights that achieve the smallest possible empirical error. If finding those exact best weights is too expensive, a natural response is to relax the goal: perhaps weights producing an error only slightly above the minimum will be much easier to find. That response is reasonable, but it is not guaranteed to solve the computational problem. Approximate empirical-risk minimization can remain computationally infeasible.
Exact versus approximate ERM
Exact ERM asks for weights that attain the smallest possible empirical error in the chosen hypothesis class. Approximate ERM weakens this requirement: the weights need only produce an error close to that minimum. The important hardness result is that this relaxation may not change the computational conclusion. Even when exact optimization is replaced by the less demanding search for nearly optimal weights, finding such weights can remain computationally infeasible.
A relaxed target that is still hard
Consider a learning task where the exact best set of weights is difficult to find. Does asking only for weights with close-to-minimal empirical error automatically make the task efficiently solvable?
Separate the targets: The exact target is the smallest possible empirical error. The relaxed target is an error close to that minimum.
Apply the hardness warning: The source states that computational hardness can survive this relaxation. Therefore, replacing exact ERM with approximate ERM is not, by itself, a guaranteed escape route.
Interpret the result: A learner may have a statistically acceptable target while still lacking an efficient method for finding weights that meet it.
Near-optimal empirical error can remain computationally infeasible to find.
Near-optimal does not mean efficiently findable
The distinction is between a property of a desired solution and the cost of discovering that solution. A nearly optimal set of weights may exist, yet an efficient learner may still be unable to find it. Thus, statistical approximation changes what counts as an acceptable answer, but it does not necessarily remove the underlying computational obstruction.
When evaluating a proposed shortcut, ask two questions separately: Is the requested error close to the optimum? Can an algorithm find weights achieving that error efficiently? The source warns that the answer to the first question can be yes while the second remains no.
Architecture is not an automatic cure
Once hardness is established for one network structure, it is natural to ask whether another architecture makes ERM efficient. The same question can be asked about replacing the activation functions with other efficiently computable choices, such as sigmoids. However, changing the representation does not automatically remove the barrier. A broader hardness result can show that the difficulty is not tied to one particular architecture or activation choice.
The representation-independent obstruction
A representation-independent hardness result states the learning difficulty without restricting the result to one particular representation. In the source, under the stated cryptographic assumption, learning intersections of halfspaces is hard even in a representation-independent model of learning.
The consequence for specific models follows from containment. If a hypothesis class contains intersections of halfspaces, then the broader hardness result applies to that class as well. Therefore, under the same cryptographic assumption, every hypothesis class containing intersections of halfspaces cannot be learned efficiently. The result does not need to analyze each possible neural-network representation separately; the containment relationship transfers the obstruction.
Checking whether a specific representation escapes
A proposed neural-network hypothesis class is known to contain intersections of halfspaces. What does the representation-independent hardness result imply under the stated cryptographic assumption?
Identify the broad hard class: The source identifies intersections of halfspaces as hard to learn efficiently under the stated assumption.
Check containment: The proposed hypothesis class contains intersections of halfspaces.
Transfer the conclusion: Because the hard class is contained in the proposed class, the representation-independent result implies that the proposed class cannot be learned efficiently under that same assumption.
Changing to this particular representation does not remove the hardness barrier established by the broader result.
Mistakes in interpreting hardness
Assuming that approximate ERM is automatically easy.
The source explicitly states that computational hardness can survive this relaxation.
Fix:
Treat approximation as a weaker target, not as proof of efficient solvability.Assuming that a different architecture must remove the barrier.
The source presents a broader obstruction that is not tied to one particular architecture.
Fix:
Ask whether a representation-independent result or a containment argument still applies.Confusing an activation-function change with a complexity proof.
Efficiently computing the activation does not by itself show that the overall learning problem is efficiently solvable.
Fix:
Separate the computational cost of evaluating an activation from the complexity of finding suitable weights.Ignoring hypothesis-class containment.
Containment is the step that transfers the representation-independent hardness result to the specific class.
Fix:
Check what functions the hypothesis class contains before claiming that its representation escapes the barrier.
Practice the reasoning
A learner argues: “Finding the exact best weights is hard, but finding weights with nearly minimal empirical error should be easy. If that is still hard, we can simply switch to another architecture or use sigmoids.” Identify the unsupported steps in this argument and explain how the representation-independent result changes the analysis.
Hints
- Separate the exact target from the approximate target.
- Ask whether the source guarantees that approximate ERM is efficient.
- Ask whether the proposed hypothesis class contains intersections of halfspaces.
A complete answer should say that approximation does not necessarily remove computational infeasibility, changing an architecture or activation function is not automatically a cure, and containment of intersections of halfspaces transfers the representation-independent hardness result to the specific hypothesis class.
Main takeaways
- Exact ERM is not the only potentially difficult goal; approximate ERM can also remain computationally infeasible.
- A close-to-minimal empirical error describes the quality of a desired solution, not the efficiency of finding that solution.
- Changing a network architecture or activation function may not remove a hardness barrier established beyond one particular representation.
- Under the stated cryptographic assumption, intersections of halfspaces cannot be learned efficiently.
- If a specific hypothesis class contains intersections of halfspaces, the representation-independent hardness result applies to that class.
Key Takeaways
- Approximate empirical-risk minimization can remain computationally infeasible.
- Statistical near-optimality and computational tractability are separate properties.
- A different architecture or activation function is not automatically an escape from hardness.
- Representation-independent hardness results transfer to specific hypothesis classes through containment.
- Under the stated cryptographic assumption, any hypothesis class containing intersections of halfspaces cannot be learned efficiently.