Representation Complexity Along Learning Trajectories: Trading Width for Precision and Time

1 Introduction

• Feature learning can require traversing representations more complex than the final predictor, motivating a distinction between representing a known target and discovering an unknown one.Information-plane studies report nonmonotonic representation trajectories, with complexity increasing before decreasing near the final solution.Source: §1 · p. 2

1.1 Modelling Approach

• The paper models learning through an oracle that provides noisy, coordinatewise gradient information rather than direct access to the target distribution.Its learner is zero-respecting: an all-zero feedback matrix leaves the first-layer representation unchanged.Source: §1.1 · p. 2

1.2 Summary of Results

• Effective width transfers statistical-query lower bounds to the gradient features available during learning, yielding a task-agnostic threshold for target-dependent information.Below the threshold, distinct targets can produce the same all-zero gradient transcript, preventing target-dependent progress.Source: §1.2 · p. 3
• For k-sparse parity, a known target has an O(k)-width representation, while discovering its support requires polynomially greater effective width.Parity's sign-reflection invariance yields a sharper unsigned width measure and a critical scale characterized up to logarithmic factors.Source: §1.2 · p. 3

1.3 Statistical Interpretations of Effective Width

• Under fresh-sample accumulation and unsigned-width assumptions, sparse parity yields a width–sample frontier: narrow representations need greater precision before the target becomes visible.The section also relates effective width and sample size to fixed-feature generalisation and interpolation; when R is much smaller than N, exact interpolation requires readout-norm inflation, while additional norm control may be needed once R approaches or exceeds N.Source: §1.3 · p. 4

1.4 Related Work

• The work connects its approach to statistical-query limits, variation-space complexity, and functional measures of representation dynamics.Its stated focus is functional diversity rather than raw neuron count as a resource for learning parities.Source: §1.4 · p. 5

2.1 A Forward-Backward Width Transfer

• The forward–backward width transfer bounds the dimension of gradient-query features using the effective width of forward activities, under bounded-weight, activation-regularity, and input-moment conditions.The generic transfer has a D² inflation from treating signed tangent directions as distinct.Source: §2.1 · p. 6
• Parity sign-reflection symmetry permits an unsigned representation measure and reduces the parity-relevant transfer inflation to D rather than D².The symmetry leaves the magnitude of target-dependent query responses unchanged.Source: §2.1 · p. 7

2.2 Critical Initial Effective Width

• Theorem 5 combines the transfer with statistical-query dimension to lower-bound initial effective width for successful zero-respecting learning.Insufficient query width leaves at least two targets compatible with an all-zero transcript, which freezes the first-layer representation.Source: §2.2 · p. 7

2.3 Sparse Parity Bounds

• A one-round sparse-parity construction uses pooled neurons whose coefficient gap makes target coordinates detectable when a pool contains the other support coordinates.Covering pools provide witness responses for every target coordinate, enabling support recovery by thresholding.Source: §2.3 · p. 8
• The parity lower and constructive upper bounds characterize critical unsigned effective width up to logarithmic factors.For fixed k, the construction interpolates from O(k) neurons at precision τ² = O_k(D^−(k−1)) to O_k(D^(k−1)) width at constant precision.Source: §2.3 · p. 8

2.4 Effective Width and Fixed-Feature Fitting

• Once a sparse-parity support is known, its O(k)-width representation gives a fixed-feature complexity bound independent of ambient dimension under controlled readout norm and approximation error.For target-independent features with R/N → 0, exact interpolation instead requires readout-norm inflation; R ≍ N marks the crossover.Source: §2.4 · p. 9

2.5 Predicted Phase Diagram

• The predicted width–sample frontier assumes fresh-sample accumulation, with τ² ≍ N⁻¹, and unsigned width as the relevant discovery measure.For a fixed query, averaging over N fresh samples motivates the tolerance scaling; the trajectory-level approximation is exact only when the representation stays fixed during accumulation.Source: §2.5 · pp. 9–10, §2.5.1 · p. 10

2.5.1 Effective width–sample phase diagram

• Below the task frontier, gradient feedback does not reveal the target; below R ≍ N, exact interpolation requires readout-norm inflation.Beyond the fixed-feature crossover, the dominant feature space may support interpolation, so additional readout regularization or implicit norm control may be needed.Source: §2.5.1 · p. 10

3 Experiments

• The trajectory-level hypothesis predicts a cumulative width-time lower envelope of e^Ω_k(D^(k−1)) when comparable fresh statistical information accumulates across steps.The proposed cumulative expenditure sums effective-width upper bounds along the trajectory.Source: §3 · p. 10

3.1 Estimating Effective Width

• The width estimate uses Walsh expansions of neuron activities to construct a low-dimensional approximation weighted by representation-cost bounds; it upper-bounds effective width but may be loose.The restriction to Walsh-based approximations and potentially nonminimal representation costs can inflate the estimate.Source: §3.1 · pp. 10–11

3.2 Cumulative Effective Width and Ambient Dimension

• The empirical comparison evaluates multiple targets, initializations, and feedback realizations per hyperparameter setting, using minimum test accuracy across runs as an analogue of the uniform criterion.The tested ambient dimensions are D=5, 7, 9, and 11 for k=3.Source: §3.2 · p. 11
• For k=3 sparse parity across D=5, 7, 9, and 11, cumulative effective-width expenditure tracks accuracy more clearly than instantaneous width, and normalising bCε by D^2 produces an approximate collapse.Instantaneous trajectories vary with initialization scale, and some successful runs show little transient increase.Source: §3.2 · p. 11, Figure 2 · p. 12

3.3 Effective Width, Optimisation Time, and Generalisation

• The width-time analysis concerns stopping times at specified accuracy thresholds and assumes approximately uniform information accumulation across training steps.It applies the lower-envelope prediction to both training and test stopping times.Source: §3.3 · p. 11
• Trajectories cannot combine low average effective width with few steps to reach either training or test accuracy thresholds; the test-time lower envelope becomes approximately U-shaped.Beyond a characteristic width, increasing width continues to accelerate fitting without a corresponding reduction in test stopping time.Source: §3.3 · pp. 11–12

4 Discussion

• Sparse parity is compact once its support is known, but noisy gradient feedback requires polynomially greater effective width to identify that support.The relevant resource is effective width, not raw neuron count.Source: §4 · pp. 12–13
• Training time stays near the predicted inverse lower envelope, while the test-time frontier turns U-shaped beyond a characteristic effective width.Stronger weight decay keeps runs closest to the test-time frontier.Source: Figure 3 · p. 13

4.1 Limitations and Future Directions

• The factor-D gap between general signed-weight transfer and its unsigned counterpart remains unresolved; closing it may require modeling how training combines and decodes gradient responses.For parity, sign invariance reduces the transfer inflation from D^2 to D, but whether the remaining factor is realizable or an artifact is open.Source: §4.1 · p. 13
• The framework covers broad activations and concept classes but is limited to shallow networks; its sparse-parity upper bounds rely on permutation symmetry and Fourier–Walsh structure.Deep extensions would need to track how representations and target-dependent information transform and are shared across layers.Source: §4.1 · p. 13
• The oracle uses fresh-sample accumulation to interpret tolerance, leaving open whether sample-wise gradient methods can exploit individual examples for more favorable PAC-type scaling.At low width, constant-rate SGD may use weak correlations less efficiently than explicit averaging; annealing, iterate averaging, or larger batches may help approach the frontier.Source: §4.1 · p. 14
• Effective width is resolution-dependent, and estimating it on an unknown input distribution remains open.For sparse parity, the finite input space and Fourier–Walsh basis provide a constructive, potentially loose upper bound.Source: §4.1 · p. 14
• Effective width measures function directions linearly accessible to prediction and gradient feedback at resolution δ, unlike noise-regularised mutual information.A measure tailored to stochastic feedback could capture distinguishability under sampling noise rather than worst-case tolerance.Source: §4.1 · p. 14

4.2 Conclusion

• Greater functional diversity can weaken statistical control while reducing the precision or time needed for target discovery, motivating a width–precision–time frontier.A compact predictor may still require a substantially richer representation to discover.Source: §4.2 · pp. 14–15

Proof

• The proof splits neurons into large and small sets, bounding the small-neuron regime by rescaling weights and applying the mean value theorem.The small-neuron condition is that every incoming weight has maximum coordinate magnitude at most α.Source: Proof · pp. 24, 27
• Auxiliary lemmas switch ambient spaces while preserving the commutation relation between the forward and query synthesis maps.The resulting approximating subspace is obtained by mapping the forward space through the relevant operator.Source: Proof · pp. 24, 26
• Combining coordinate-query families incurs a D-fold dimension increase over the largest individual coordinate-query width.The proof constructs a joint approximating space from the coordinate-specific spaces.Source: Proof · p. 24
• For large neurons, the transfer bounds tangent-feature width using an approximating space whose dimension is at most D times the forward-space dimension.The stated error scales with the large-coordinate threshold α and the forward approximation error ε.Source: Proof · pp. 25–26
• For large unsigned neurons, the proof uses a directional derivative and summed multiplier to build a transfer space with dimension no greater than the forward approximating space.This construction assumes nonnegative incoming weights and the additional condition stated in the lemma.Source: Proof · pp. 26–27
• The proof combines approximations for the two query regimes by taking the span of their spaces, whose dimension is at most the sum of their dimensions.Each query belongs to one of the two families, so its error is controlled by that family's approximation.Source: Proof · p. 27

B.4 Main transfer result

• The query-family width d_{D2n+D}(Q, L2) is at most Ctr D^1/4 d_n(Z, Bz)^1/2.The constant Ctr is independent of dimension.Source: §B.4 · p. 28
• Under nonnegative weights and a dictionary bounded in l1, Corollary 22 gives a dimension-free transfer constant.The corollary invokes assumption 4.Source: §B.4 · p. 28

Appendix C. SQ Bounds on Width

• SQ dim(F, γ) is the largest d for which F contains d unit-norm hypotheses with pairwise inner products at most γ in magnitude.This is the criterion used to define an SQ-witness family.Source: Appendix C · p. 29
• The section adapts a standard CSQ lower-bound argument to show that learning below squared loss 1−γ requires many oracle calls.The lemma states the query requirement in terms of SQ dimension.Source: Appendix C · p. 29
• The required query count is M ≥ τ^2(d−1)/(1+(d−1)γ); a single query detects at most (1+(d−1)γ)/τ^2 hypotheses, and eliminating d−1 hypotheses is required.Source: Appendix C · p. 30

C.1 Intrinsic Complexity bounds from CSQ bounds

• The width obstruction uses the intrinsic complexity of queries to assess whether an algorithm requests information efficiently, even if its query process is inefficient.The section approximates query families in finite-dimensional spaces before applying SQ-dimension bounds.Source: §C.1 · p. 30
• If the initial query family has insufficient width, at least two distinct targets have responses no larger than τ for every query in the family.The width-transfer result connects the initial activity set to the intrinsic dimension of the tangent-query family.Source: §C.1 · p. 32
• For a zero-respecting learner, an all-zero response can freeze the first-layer representation, making the complete transcript identical under those targets.The learner therefore cannot identify both targets correctly.Source: §C.1 · p. 32
• Under the symmetry assumption, signed queries can be replaced by absolute-weight queries because target compatibility with zero responses is unchanged.This permits use of the tighter parity-relevant transfer.Source: §C.1 · p. 33

D.1 Forward Approximation

• Threshold functions represent k-parity by interpolating its values over the k+1 possible sums of the target coordinates.The construction chooses weights supported on the target set and biases that produce the interpolation points.Source: §D.1 · p. 34
• Every function on the k+1 possible coordinate sums, including k-parity, can be represented by k+1 derivative features.The section also constructs finite-weight tanh functions with a well-conditioned basis.Source: §D.1 · pp. 34–35

D.1.1 Covering

• A covering family of size-s pools is chosen so every (k−1)-subset of coordinates is contained in at least one pool.The construction uses a classical (D, s, k−1)-covering design.Source: §D.1.1 · p. 37
• Sharper covering-design bounds do not remove the logarithmic factor from the asymptotic width estimate.The section retains an elementary probabilistic proof for completeness.Source: §D.1.1 · p. 37

• The coordinatewise gradient transcript identifies every k-sparse parity in one non-adaptive oracle round.The learner accepts coordinate d when some pool response lies within τ of λk−1,s; the stated separation prevents false acceptances.Source: Then there exists a network of width · pp. 38–39
• For each target coordinate, the covering property supplies a pool containing the support with that coordinate removed.Source: Then there exists a network of width · p. 39
• All pool-coordinate responses are requested simultaneously, so the support-recovery procedure uses one oracle round.Source: Then there exists a network of width · p. 39

D.2 Explicit Endpoints

• A width-k construction identifies every k-sparse parity in one non-adaptive round when τ < 1/(2Ck).A separate single-neuron result identifies every k-sparse parity when 2τ < |∆D,k|; for fixed k, the stated condition holds for sufficiently large D.Source: §D.2 · pp. 39–40

E.1 Variation Balls

• The variation-ball section states empirical Rademacher-complexity bounds for variation balls, finite-dimensional classes, and bounded inputs.Source: §E.1 · pp. 41–42

E.2 Generalisation Bound

• The generalisation result bounds population-versus-empirical loss uniformly over readouts using effective-width approximations and Rademacher complexity.The approximation uses a subspace of dimension at most R and approximants to the selected features.Source: §E.2 · pp. 43, 45

E.3 Norm-control

• For most k-sparse parity targets, low-dimensional approximation of the initial activity family forces every sample-interpolating readout to satisfy a norm lower bound.The result assumes the initial activity family and its approximating space are conditionally independent of the target given the sample inputs.Source: §E.3 · p. 49
• Under permutation invariance, the fixed-target interpolation-obstruction conclusion holds for every fixed k-sparse parity, with probability 1−o(1) over task-independent initialization and the sample.This is under Theorem 45’s assumptions, with R < N and ηD,N,ζ < 1.Source: §E.3 · p. 51

Along the parity frontier

• On the low-width side of the crossover and within the empirical-isotropy regime, exact interpolation requires readout norm Ω(ND) with probability 1−o(1).The stated regime has R/N→0 and ηD,N,ζ→0, up to logarithmic factors, throughout the specified window.Source: Along the parity frontier · p. 51