CAGE-NAS: Certified Functional Descent for Efficient Model Growth

1 Introduction

• Progressive growth must determine when a representation is no longer adequate for optimization and should be modified.The paper frames training and growth as needing a common condition tied to the current representation's ability to follow the optimization direction.Source: §1 · p. 1
• CAGE-NAS treats representational adequacy in function space, where the neural representation induces adaptive families of functional-gradient approximations.The representation is adequate while at least one family produces a realizable direction sufficiently close to the functional gradient to preserve functional-gradient-descent conditions.Source: §1 · p. 1
• The resulting constructive scheme connects training and growth through a common condition of representational sufficiency.Source: §1 · p. 1

2 Previous Work

• GradMax initializes added neurons using gradient information, NORTH specifies when, where, and how to grow, and Firefly uses local search over architectural modifications.Source: §2 · p. 1
• FRAGrow adapts growth timing to fitting risk, while TINY uses an expressivity-bottleneck notion to address functional capacity to follow the optimization direction.Source: §2 · p. 2
• In TINY's DAG extension, intermediate training is shown to push parameters toward overfitting, while subsequent growth can help escape potential local minima.This highlights the interaction between training and growth dynamics.Source: §2 · p. 2
• Functional Gradient Descent with Adaptive Representations [2] establishes convergence conditions when the functional gradient is replaced by adaptive finite-dimensional approximations.The framework provides foundations for governing training and structural growth with a functional-approximation criterion.Source: §2 · p. 2

3 CAGE-NAS

• An induced approximation of the functional gradient must satisfy a relative-error criterion to support descent, with updates designed to converge to a stationary point that is also a global minimizer.In the finite-data setting, the Banach and Hilbert norms are equivalent on the empirical function space.Source: §3 · p. 2
• With the stated PL condition and μ = 2, every sequence of committed certified steps satisfies a trajectory-level contraction.Source: §3 · p. 2
• Growth becomes necessary when no functional-gradient representation induced by the current architecture can certify a step at the current functional state.This failure signals an expressivity bottleneck; growth expands the available directions.Source: §3 · p. 3
• Structural expansion preserves the current network function and loss, then recomputes certification on the grown architecture before optimization resumes.The resulting architectures form a constructive sequence.Source: §3 · p. 3

3.1 The damped tangent space approximation as a CAGE-NAS Representation

• The tangent-space instance projects the functional gradient onto directions generated by infinitesimal parameter variations, with regularization set by a damping factor.The Jacobian of the finite-data representation characterizes those directions.Source: §3.1 · p. 3
• The damping parameter trades approximation fidelity against required parameter displacement; a qualifying tangent approximation certifies descent, while failure can motivate other realizable variations or growth.As damping vanishes, the direction approaches the orthogonal projection onto the tangent space, and the residual corresponds to TINY's expressivity bottleneck.Source: §3.1 · p. 3

4 Empirical Evaluation of CAGE-NAS

• The controlled nonlinear-regression evaluation used a fixed parameter budget, four model seeds, and a complete training set for certification.Training and validation each contained 1,024 examples, and test contained 8,192.Source: §4 · p. 3
• Above the 99.8th performance percentile by test RMSE for every seed, CAGE-NAS avoided enumerating the screened alternatives during growth.The percentile comparison is against screened models satisfying the strict 600-parameter budget; the study screened 76,646 architectures and tuned 12,240 architecture–hyperparameter pairs.Source: Figure 1 · p. 4, §4 · p. 4
• Mean test RMSE was 0.0613 ± 0.0060 for CAGE-NAS, versus 0.0700 ± 0.0053 after same-seed retraining from scratch; growth obtained lower RMSE in three of four seeds.The fixed-architecture grid used validation-selected hyperparameters.Source: §4 · p. 4

5 Efficiency boundary and limitations

• Evidence covers a controlled synthetic benchmark across four seeds; classification and real-world tasks are still needed to assess broader applicability.The evaluated space is also restricted to fixed-depth, three-hidden-layer MLPs and monotonic neuron additions.Source: §5 · p. 4
• Tangent-family certificates can reflect interpolation rather than representational sufficiency when pA ≥ s and the empirical Jacobian has full row rank.When pA < s, overparameterization alone cannot make the empirical Jacobian span the finite-data function space.Source: §5 · p. 4
• Efficiency claims concern architecture discovery, while practical scaling remains unprofiled across wall-clock time, FLOPs, peak memory, and energy.An explicit Jacobian requires Θ(spA) storage and O(spA min{s, pA}) dense factorization; certification may also evaluate several expansions, damping values, and solves.Source: §5 · p. 4

6 Conclusion

• In a controlled setting with exact Jacobian computation and full-data certification, CAGE-NAS architectures lie in the extreme lower-RMSE tail of admissible alternatives within their parameter budgets, without enumerating them during search.The conclusion presents this as initial evidence for using functional-gradient representation adequacy to coordinate training and growth; other representation families and larger-scale problems remain future work.Source: §6 · p. 4

A Where to grow

• For inner growth, the algorithm compares candidate neuron locations by relative-error certificates on cloned networks initialized from the same output and data, isolating the structural location's effect.After committing a candidate, scores are recomputed because the Jacobian, its spectrum, and subsequent addition options have changed.Source: A Where to grow · p. 6
• For outer growth, it adds a neuron to the layer with the largest expressivity bottleneck using a function-preserving construction, providing another degree of freedom for later certificate searches.This outer-step location rule differs from certificate-based selection used during inner growth.Source: A Where to grow · p. 6

B.1 Gradient, smoothness, and PL identity of the code loss

• The summed squared-error code loss has Hessian 2I_s, smoothness and strong-convexity constants Ls = µ = 2, unique minimizer F⋆ = Y, and an equality PL bound.Dividing the loss by n rescales both constants by 1/n.Source: §B.1 · p. 7
• For the empirical problem, the Hilbert and Banach geometries coincide with Euclidean Hn, making the gradient-compatibility constants α = β = 1.The appendix derives this from the Hilbert gradient identity and the isometric Riesz representation.Source: §B.1 · p. 7

B.2 Sufficient descent and the implemented rate interval

• A functional-gradient approximation g with relative error ε = ∥g − r∥B/∥g∥B < 1/2 satisfies the sufficient-descent condition for an Ls-smooth functional.The stated result requires the descent coefficient q to be positive.Source: §B.2 · p. 8
• Specializing the sufficient-descent result to α = β = 1 and code-loss smoothness K = Ls = 2 yields the implemented positive-q learning-rate interval.The interval follows by solving q(η, ε) > 0; its upper bound for Ls = 2 is (1 − 2ε)/(1 + 2ε).Source: §B.2 · p. 8

B.3 Global linear contraction for the implemented training loss

• Committed training steps with positive q_t are analyzed through the global linear-contraction result, with stationary and global bounds logged as trajectory diagnostics in the main configuration.The paper-pure certify_apply_in_ interval path commits a step from its relative-error certificate rather than requiring a second held-out-loss gate.Source: §B.3 · p. 8

C The damped tangent family

• Damping regularizes the tangent-space projection to discourage large parameter updates that could enlarge the neglected nonlinear Taylor remainder and undermine its function-space interpretation.Decreasing damping can improve approximation by transmitting more singular modes, but can amplify parameter coefficients and the nonlinear remainder.Source: C The damped tangent family · pp. 9, 11
• The tangent approximation is admissible only when its relative-error criterion is met; in the undamped orthogonal-projection limit, ε < 1/2 corresponds to capturing more than 80% of functional-gradient energy.With damping, the direction is a filtered projection, so the 80% interpretation is a limiting case and the implemented relative error is evaluated directly.Source: C The damped tangent family · pp. 9–10
• The admissible learning-rate interval excludes both nonpositive-descent steps and excessively small steps that could stagnate loss; the proposed midpoint maximizes the quadratic lower bound on guaranteed descent.As approximation quality deteriorates, the permitted rate decreases; at ε = 1/2 no strictly positive rate remains, triggering representation refinement.Source: C The damped tangent family · p. 10

D Nonlinear parametric displacement family

• When tangent linearization is insufficient, the method searches within the same network for a finite curved parametric displacement that can contain higher-order components.The clone is trained toward a target that makes its nonlinear displacement follow the functional-gradient trajectory, rather than directly seeking the prediction.Source: D Nonlinear parametric displacement… · p. 11
• Certification of a nonlinear displacement tests its direction after optimal positive scaling, not the displacement's magnitude, which depends on clone-training choices and curvature.The candidate is committed only when it meets the relative-error criterion.Source: D Nonlinear parametric displacement… · p. 12

Certification setting

• The controlled study uses dense tangent computations, whose computational cost is a stated limitation, and certifies steps on all 1024 training samples without a held-out-loss acceptance gate.Validation and test losses are reported as diagnostics; they do not determine acceptance of a functional step.Source: §E.1 · p. 12

Training and architectural growth

• Training loss falls as capacity grows, and the seed-0 run shows no persistent training-accuracy degradation after expansion.The experiment starts from three hidden layers with two neurons each and repeats across four seeds; initialization affects the trajectory.Source: §E.1 · pp. 12–13, Figure 2 · p. 13

Held-out behavior

• After a brief transient, test loss trends downward and test accuracy stabilizes near its upper plateau as the architecture grows.The held-out curves do not diverge from the training trajectory in the representative seed-0 run.Source: §E.1 · p. 13, Figure 3 · p. 14

Performance among budget-constrained alternatives

• Across every evaluated seed, CAGE-NAS ranks in the top 0.2% by test RMSE among screened architectures with p(A) ≤600, without enumerating them during growth.The percentile ranges from 99.88th to 100.00th; this does not establish recovery of the globally best architecture.Source: §E.1 · p. 14, Figure 4 · p. 15, Table 3 · p. 15

Scope and limitations

• The growth criterion does not directly optimize parameter count, and test performance is unavailable during training, so more generalizing architectures may not be selected.The authors suggest an additional mechanism for favoring generalization, complementing damping.Source: §E.1 · p. 15

Comparison with fixed retraining

• Fixed retraining averages 0.0700 ± 0.0053 test RMSE, versus 0.0613 ± 0.0060 for growth; growth wins three of four paired seeds.The paired difference, fixed retraining minus growth, is +0.0087 ± 0.0107, and the four-seed sample does not establish a uniform advantage.Source: Table 4 · p. 16, §E.1 · p. 16

• Only the first three input coordinates contribute to the single-output target.Source: §E.2 · p. 16
• The target combines smooth nonlinear terms, a pairwise interaction, and a weak linear component; the fourth input dimension is irrelevant.Source: §E.2 · p. 16
• Training and validation each use 1,024 examples in 16 batches of 64, while testing uses 8,192 examples.Source: §E.2 · p. 16
• The synthetic loader resets its seed each iteration, so the same examples recur at every epoch.Source: §E.2 · p. 16

• The four final architectures are retrained from random initialization with structural growth disabled.Source: §E.3 · p. 17
• The grid tests 60 AdamW configurations per architecture and seed, varying learning rate, weight decay, and cosine annealing, across four model seeds and 400 epochs.This produces 960 trials.Source: §E.3 · p. 17
• Hyperparameters and the best epoch are selected by minimum validation MSE, with each growth run compared to same-seed retraining after validation-based selection.Source: §E.3 · p. 17

E.4 Search over fixed architectures within the parameter budget

• The three-hidden-layer architecture’s trainable-parameter count is given by p(A) = 5h1 + h1h2 + h2 + h2h3 + 2h3 + 1.Source: §E.4 · p. 17
• The search retains the 50 best architectures per seed after Stage 1 screening, then evaluates them across 60 AdamW learning-rate, weight-decay, and scheduler configurations.Source: §E.4 · p. 17
• Candidates with p(A) ≤600 are ranked by minimum validation MSE, and test RMSE is read only after selection; the protocol does not rule out better architectures beyond its search.Source: §E.4 · p. 17

F CAGE-NAS train-and-grow algorithms

• Epoch-level training builds a fixed certification set, attempts up to 15 certified outer steps, retains function-preserving growth, and stops at the first rejected attempt.Source: F CAGE-NAS train-and-grow algorithms · p. 18
• A certified outer step first tries nonlinear growth; if the tangent family is admissible, it tries a certified tangent realization and otherwise rejects the parameter step.Source: F CAGE-NAS train-and-grow algorithms · p. 18