# Fully-corrective greedy neuron growth

- ID: 2635
- Canonical URL: https://synthcore.org/idea/2635/fully-corrective-greedy-neuron-growth
- API JSON: https://synthcore.org/api/idea/2635.json
- API Markdown: https://synthcore.org/api/idea/2635.md
- Verification status: beats_baseline
- Source: [arXiv:2608.20812](https://arxiv.org/abs/2608.20812)
- Category: optimization
- Solves: sample-efficiency, accuracy, speedup
- ML areas: mlp, optimizer, training
- Math tags: approximation-theory, optimization, functional-analysis
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## Idea description

Train a low-width network by repeatedly selecting a normalized neuron that is maximally correlated with the current residual, then refit all output coefficients jointly. This gives a constructive alternative to random initialization of all hidden units and exposes an empirical width-versus-error curve that can guide early stopping or architecture selection.

## Mathematical statement

For training samples $(x_i,y_i)_{i=1}^n$, let $r_t\in\mathbb R^n$ be the residual after $t$ atoms. For a normalized parameter $\theta=(w,b)$, define the feature vector $\Phi_\theta\in\mathbb R^n$ by $\Phi_\theta[i]=\sigma(\langle w,P_mx_i\rangle+b)$, with $\|w\|_2\le1$ and $|b|\le1$. The greedy step selects an atom approximately maximizing normalized residual correlation, $\left|\langle r_t,\Phi_\theta\rangle\right|/\|\Phi_\theta\|_2$. Fully-corrective fitting then jointly refits all coefficients by least squares plus an $\ell_1$ penalty, or under the variation constraint $\sum_j|a_j|\le R$. The constructive approximation regime predicts a squared finite-width error of order $R^2/K$, while the complete population error also contains resolution truncation and statistical terms.

## Key formulas

- $$\theta_{t+1}\approx\arg\max_{\theta:\ \|w\|_2\le1,\ |b|\le1}\frac{\left|\langle r_t,\Phi_\theta\rangle\right|}{\|\Phi_\theta\|_2+\varepsilon},\qquad \Phi_\theta[i]=\sigma(\langle w,P_mx_i\rangle+b).$$
- $$a^{(t+1)}=\arg\min_{a\in\mathbb R^{t+1}}\left\|y-\Phi_{1:t+1}a\right\|_2^2+\lambda\|a\|_1,\qquad r_{t+1}=y-\Phi_{1:t+1}a^{(t+1)}.$$
- $$\sum_{j=1}^{t}|a_j|\le R,\qquad \|y-\Phi_{1:t}a^{(t)}\|_2^2\ \text{has finite-width approximation component }O\!\left(\frac{R^2}{t}\right).$$
- $$\mathcal E(f_K)\lesssim \|f-f\circ P_m\|_{L_2(P)}^2+\frac{CR^2}{K}+\frac{RB}{\sqrt n}.$$

## Implementation notes

Use this as a hidden-layer growth optimizer for the normalized dictionary model. Initialize with only an output bias equal to the mean target. At stage $t$, compute the residual vector $r_t$ on the full small training set or a large fixed minibatch. Parameterize candidates with unconstrained $u,c$, then set $w=u/(\|u\|_2+\varepsilon)$ and $b=\tanh(c)$ so the paper's constraints hold automatically. Run 10--50 Adam steps from several random restarts to maximize $|r_t^T\Phi_\theta|/(\|\Phi_\theta\|_2+\varepsilon)$. Add the best candidate, refit all output coefficients with a small Lasso or ridge solve, and recompute the residual. Stop at width $K$ or when validation loss fails to improve. The paper supplies the normalized dictionary and the predicted $O(R^2/K)$ finite-width behavior; candidate-search quality, $R$, and the actual decay slope are empirical. First test on one-dimensional function regression and a small Burgers operator dataset. Compare against a width-$K$ two-layer MLP trained end-to-end from random initialization, matching forward/backward evaluations. Report error versus neuron count, wall-clock time, and seeds. Success is monotone validation improvement, an approximate $1/K$ residual regime, faster attainment of a target error at low width, or lower seed variance.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a fully-corrective greedy ReLU neuron-growth optimizer with constrained atom parameterization, residual-correlation search, and joint ridge refitting. Three mechanism checks passed: normalized-score scale invariance held to about 1e-12, the orthogonalized least-squares reduction identity held to 1.1e-13 relative error, and the best correlation increased monotonically with candidate-pool size (2.09 to 3.20). The width-error curve improved monotonically, but its observed log-log slope was -3.69 rather than the predicted -1 regime; greedy growth was faster than the separately trained MLP at width 16 (10.8s vs 26.6s), while the MLP sometimes achieved lower validation error.

### Mechanism check

- Verdict: Built a fully-corrective greedy ReLU neuron-growth optimizer with constrained atom parameterization, residual-correlation search, and joint ridge refitting. Three mechanism checks passed: normalized-score scale invariance held to about 1e-12, the orthogonalized least-squares reduction identity held to 1.1e-13 relative error, and the best correlation increased monotonically with candidate-pool size (2.09 to 3.20). The width-error curve improved monotonically, but its observed log-log slope was -3.69 rather than the predicted -1 regime; greedy growth was faster than the separately trained MLP at width 16 (10.8s vs 26.6s), while the MLP sometimes achieved lower validation error.
- Confidence: 8/10
- Limitations: Only a small one-dimensional noiseless function-regression task was tested; no Burgers/operator dataset, L1-constrained refit, larger-dimensional projection, or rigorous FLOP-matched comparison was performed. The MLP comparison used one seed per width, while the greedy candidate search used a small fixed number of restarts; the observed 1/K scaling prediction was not confirmed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 8/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/1011/bench_report.json)
- [experiment.py](https://synthcore.org/code/1011/experiment.py)
- [math_check.json](https://synthcore.org/code/1011/math_check.json)
- [report.md](https://synthcore.org/code/1011/report.md)
- [report_bench_2026-09-01T181309.md](https://synthcore.org/code/1011/report_bench_2026-09-01T181309.md)
- [results.json](https://synthcore.org/code/1011/results.json)
- [stage2_bench.py](https://synthcore.org/code/1011/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/1011)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.