Scale Invariant Complexity Measures for Neural Networks

36 concepts18 papers1 proposal

One of the central mysteries in deep learning is generalization: why do massive, over-parameterized networks perform exceptionally well on unseen data instead of merely memorizing the training set? To answer this, theorists try to measure a model's "capacity" or complexity. Traditionally, we might count the number of parameters or calculate standard weight norms (like the $L_2$ norm used in weight decay).

However, standard weight norms suffer from a fundamental flaw when applied to modern deep networks: they measure the arbitrary parameterization of a network rather than the intrinsic function it computes.

The Flaw in Standard Weight Norms

To understand why standard norms fail, consider a simple two-layer neural network with Rectified Linear Unit (ReLU) activations:

$$f(x) = W_2 \max(0, W_1 x)$$

Because the ReLU activation function is positive-homogeneous ($\max(0, \alpha z) = \alpha \max(0, z)$ for any $\alpha > 0$), we can scale the weights of the first layer by $\alpha$ and divide the second layer by $\alpha$ without changing the output of the network at all:

$$f(x) = \frac{1}{\alpha} W_2 \max(0, \alpha W_1 x) = W_2 \max(0, W_1 x)$$

Functionally, the network is completely identical. Yet, its standard $L_2$ weight norm—the sum of the squared weights $\|W_1\|_F^2 + \|W_2\|_F^2$—can change drastically depending on our choice of $\alpha$. As demonstrated by Neyshabur et al. in Exploring Generalization in Deep Learning, this sensitivity to parameter rescaling makes raw weight norms highly misleading indicators of a network's true capacity. An ideal complexity measure should be scale-invariant, ensuring that transformations of model weights that do not alter the underlying predictions also do not alter the complexity score (Abbas et al. in Effective dimension of machine learning models).

The Path-Norm Solution

How do we design a metric that ignores this superficial scaling? Instead of evaluating layers in isolation, we can view the neural network as a collection of directed paths running from the inputs to the outputs.

For any given path from an input node to an output node, the total weight of that path is the product of the weights of the edges connecting them. If we apply a node-wise rescaling transformation—multiplying an incoming edge by $\alpha$ and dividing the outgoing edge by $\alpha$—the product of the weights along any path passing through that node remains exactly the same because the $\alpha$ and $1/\alpha$ terms cancel out.

Standard Norms (Layer-by-Layer):
[Layer 1: Weights * α] ---> [Layer 2: Weights / α]  ==> Norm changes!

Path-Based Norms (End-to-End):
Input ------(Weight 1 * α)------> Node ------(Weight 2 / α)------> Output
Total Path Product = (Weight 1 * α) * (Weight 2 / α) = Weight 1 * Weight 2  ==> Invariant!

By summing these weight products across all possible paths in the network, we obtain the path-norm. First formalized by Neyshabur et al. in Norm-Based Capacity Control in Neural Networks and Geometry of Optimization and Implicit Regularization in Deep Learning, the path-norm provides a representation-independent measure of functional capacity.

To make this framework practical for modern architectures, Gonon et al. extended the path-norm toolkit to handle skip connections, biases, and max-pooling in A path-norm toolkit for modern networks: consequences, promises and challenges. However, simply summing all paths can sometimes overestimate capacity because many paths share the same underlying edges and are linearly dependent. To resolve this, Zheng et al. introduced the Basis-Path Norm in Capacity Control of ReLU Neural Networks by Basis-Path Norm, which isolates a minimal set of linearly independent paths to measure complexity more tightly.

Geometrically and Functionally Invariant Metrics

Path-norms achieve scale invariance by exploiting the specific algebraic structure of coordinate-wise scaling. Other researchers have approached the problem from a broader geometric perspective, looking at the intrinsic geometry of the function space or the loss landscape.

Information Geometry

Instead of tracking paths, we can evaluate how sensitive a model's outputs are to changes in its parameters. Liang et al. proposed the Fisher-Rao norm in Fisher-Rao Metric, Geometry, and Complexity of Neural Networks. Rooted in information geometry, this metric utilizes the Fisher Information Matrix to construct a capacity measure that is inherently invariant under any continuous parameter transformation that preserves the output function.

Similarly, Lau et al. introduced the Local Learning Coefficient (LLC) in The Local Learning Coefficient: A Singularity-Aware Complexity Measure. Derived from Singular Learning Theory, the LLC measures the local geometry of the loss landscape around singularities, providing a reparameterization-invariant metric of effective complexity. Sun et al. also leveraged the local rank of the Fisher Information Matrix in A geometric modeling of Occam’s razor in deep learning to capture functional diversity while remaining completely invariant to network symmetries like neuron permutations.

Function-Space Geometry

An alternative way to guarantee invariance is to ignore the weights entirely and measure the geometric complexity of the decision boundaries in the input space. For instance, Li et al. proposed the region count metric in Understanding Nonlinear Implicit Bias via Region Counts in Input Space, which counts the number of connected components in the input space that share the same predicted label.

In a similar spirit, Moser et al. developed an intrinsic shape complexity measure in Tessellation-Filtering ReLU Neural Networks based on how much a decision boundary deviates from convexity. Because these metrics look directly at the input-output mapping, they remain constant regardless of the specific network architecture, depth, or width used to represent the function. For vector-valued functions, Park et al. developed a basis-independent approach in Towards Empirical Process Theory for Vector-Valued Functions: Metric Entropy of Smooth Function Classes to ensure complexity metrics remain invariant under rotations or coordinate transformations of the output space.

Optimization with Invariant Regularizers

Understanding scale-invariant complexity does more than just yield better generalization bounds; it also changes how we train neural networks. Standard optimization algorithms like Stochastic Gradient Descent (SGD) with weight decay implicitly minimize standard $L_2$ norms, meaning they are sensitive to the arbitrary scaling of layers.

To align optimization with the true geometry of the network, Neyshabur et al. developed Path-SGD in Path-Normalized Optimization of Recurrent Neural Networks with ReLU Activations. Path-SGD updates weights based on gradients normalized by the path-norm, ensuring that parameter updates are invariant to node-wise rescaling. To enforce these structural constraints directly, Ravi et al. utilized conditional gradient methods in Explicitly Imposing Constraints in Deep Networks via Conditional Gradients Gives Improved Generalization and Faster Convergence to bound the path norm during training, accelerating convergence.

Standard SGD: Updates weights uniformly across layers, ignoring rescaling imbalances.
Path-SGD:     Updates weights according to the aggregate path strength, maintaining scale invariance.

Interestingly, some of our most common empirical training techniques implicitly optimize these path-based metrics. Arora et al. demonstrated in Dropout: Explicit Forms and Capacity Control that the dropout mechanism itself induces an explicit form of path-norm regularization, explaining its capacity control properties without requiring external weight constraints.

When explicitly added as a regularizer, path-norms can dramatically simplify the optimization landscape. Ergen et al. showed in Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks that path regularization can transform the notoriously non-convex training of parallel ReLU networks into an exact convex optimization problem. This mathematical tractability allows researchers like Liu et al. to derive sharper generalization bounds for infinitely wide networks in Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks, showing that when capacity is controlled via path-norms, networks can successfully evade the curse of dimensionality.

Key Foundational Work

Norm-Based Capacity Control in Neural Networks (2015) — contributed 2 concept elements to this direction.
Path-Normalized Optimization of Recurrent Neural Networks with ReLU Activations (2016) — contributed 1 concept elements to this direction.
Path-SGD: Path-Normalized Optimization in Deep Neural Networks (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_rescaling_invariant_complexity_measure_bf288d77,
  title = {rescaling-invariant complexity measure},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/rescaling-invariant-complexity-measure/rdr_bf288d7756ac4628ad33dd517f798cba},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_rescaling_invariant_complexity_measure_bf288d77_v1,
  title = {rescaling-invariant complexity measure},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/rescaling-invariant-complexity-measure/rdr_bf288d7756ac4628ad33dd517f798cba/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake