Neural Network Architectures and Activation Functions

Suppose training a neural network means finding weights that achieve the smallest possible empirical error.

Programming

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

What changes when the goal moves from the exact empirical minimum to a close-to-minimal error?

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.

Worked example

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?

1
Separate the targets
The exact target is the smallest possible empirical error. The relaxed target is an error close to that minimum.
2
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.
3
Interpret the result
A learner may have a statistically acceptable target while still lacking an efficient method for finding weights that meet it.

Result

Near-optimal empirical error can remain computationally infeasible to find.

Near-optimal does not mean efficiently findable

How can a nearly optimal training-error target still be impossible to find efficiently?

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.

Key point

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

How can computational hardness persist when the network architecture or activation function changes?

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

How does a representation-independent hardness result apply to particular neural-network architectures and activation functions?

Definition

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.

Worked example

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?

1
Identify the broad hard class
The source identifies intersections of halfspaces as hard to learn efficiently under the stated assumption.
2
Check containment
The proposed hypothesis class contains intersections of halfspaces.
3
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.

Result

Changing to this particular representation does not remove the hardness barrier established by the broader result.

Mistakes in interpreting hardness

Common mistake
Assuming that approximate ERM is automatically easy.
What it looks like
The exact minimum is difficult, so the learner asks only for weights with close-to-minimal empirical error.
Why it fails
The source explicitly states that computational hardness can survive this relaxation.
Do this instead
Treat approximation as a weaker target, not as proof of efficient solvability.
Common mistake
Assuming that a different architecture must remove the barrier.
What it looks like
A hardness result is known for one network structure, so a different structure is declared easy.
Why it fails
The source presents a broader obstruction that is not tied to one particular architecture.
Do this instead
Ask whether a representation-independent result or a containment argument still applies.
Common mistake
Confusing an activation-function change with a complexity proof.
What it looks like
Replacing an activation function with an efficiently computable sigmoid is treated as evidence that learning is efficient.
Why it fails
Efficiently computing the activation does not by itself show that the overall learning problem is efficiently solvable.
Do this instead
Separate the computational cost of evaluating an activation from the complexity of finding suitable weights.
Common mistake
Ignoring hypothesis-class containment.
What it looks like
A specific model representation is analyzed without checking whether its hypothesis class contains intersections of halfspaces.
Why it fails
Containment is the step that transfers the representation-independent hardness result to the specific class.
Do this instead
Check what functions the hypothesis class contains before claiming that its representation escapes the barrier.

Practice the reasoning

MEDIUM

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.

Your attempt (not saved)

Key point

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

1
Exact ERM is not the only potentially difficult goal; approximate ERM can also remain computationally infeasible.
2
A close-to-minimal empirical error describes the quality of a desired solution, not the efficiency of finding that solution.
3
Changing a network architecture or activation function may not remove a hardness barrier established beyond one particular representation.
4
Under the stated cryptographic assumption, intersections of halfspaces cannot be learned efficiently.
5
If a specific hypothesis class contains intersections of halfspaces, the representation-independent hardness result applies to that class.

At a glance

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.

More concepts starting with N