cs.LGDec 14, 2021

Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time

Authors: Zhao Song, Lichen Zhang, Ruizhe Zhang

Organizations: Adobe Research · Massachusetts Institute of Technology · Simons Institute for the Theory of Computing

Abstract

We consider the problem of training the last layer of a multi-layer over-parametrized neural network to minimize the empirical risk induced by a loss function. In the typical setting of over-parametrization, the network width mm is much larger than the data dimension dd and the number of training samples nn (m=poly(n,d)m=\mathrm{poly}(n,d)), which induces a prohibitively large weight matrix W∈Rm×mW\in\mathbb{R}^{m\times m} per layer above the first. Naively, when the layer inputs are dense, one has to pay O(m2)O(m^2) time to read the weight matrix and evaluate the neural network function in both forward and backward computation. To reduce the training cost per iteration, we propose a framework that uses O(m2nL)O(m^2nL) time in the initialization phase and achieves a truly subquadratic amortized cost per iteration in terms of mm, i.e., m2−Ω(1)m^{2-Ω(1)} per iteration. The speedup comes from a sparse activation, a shifted ReLU whose threshold at each layer is proportional to the norm of the layer input. With this threshold every layer is positively homogeneous, so our convergence proof needs a width only polynomial in the depth LL, in nn and in the inverse smallest kernel eigenvalues. The inputs of the trained layer are fixed and sparse. In this setting, simpler algorithms without a data structure reach the same cost per iteration, and maintaining the products of the last layer with its inputs lowers it to mnω−1+o(1)mn^{ω-1+o(1)}, where ωω is the matrix multiplication exponent. Our result can be viewed as an idealized model of maintaining a small amount of state on top of a frozen pre-trained model to speed up fine-tuning, a core procedure to deploy large language models (LLMs). Our guarantees assume that the frozen layers are random, and for a pre-trained model only the cost per iteration of maintaining these products carries over.

Figures & tables

Explore similar work

Jul 10, 2026

Super-Tuning: From Activation-Aware Pruning to Sparse Fine-Tuning

Large language models (LLMs) remain expensive to fine-tune because full-parameter updates require substantial memory, compute, and per-task storage. We study whether saliency signals originally developed for pruning can be reused to choose where a model should adapt. We propose Super, a sparse parameter-efficient fine-tuning (PEFT) method that fixes a small trainable support using a Wanda-style activation-weighted magnitude score [Sun et al., 2023] computed from a calibration pass. We then introduce Supra, a hybrid adapter that combines this sparse update with LoRA while preserving a matched trainable-parameter budget through a simple budget-splitting rule. In single-seed Math17K arithmetic experiments on Llama-3.2-1B and Meta-Llama-3-8B, the best Super/Supra variants achieve the highest average accuracy among the tested schedule-selected adapter configurations. We also include a PaFi-style magnitude-only support as a closest training-free sparse baseline and find that low-score supports under both magnitude and Wanda-style orderings can be effective. These results suggest that simple pruning-inspired orderings can provide useful fixed sparse supports for PEFT, especially when combined with low-rank adapters.
Sep 28, 2026

Two-Timescale Fine-tuning Provably Learns New Features for Two-Layer ReLU Networks

Fine-tuning pre-trained models on specialized tasks with scarce data is central to modern deep learning. Despite its empirical success, theoretical understanding of fine-tuning remains limited. We introduce a Gaussian multi-index setting to study fine-tuning from pre-trained weights, where the teacher network has m+1m+1 features, mm of which are learned during pre-training and one of which must be learned during fine-tuning. For two-layer ReLU networks, we show that two-timescale training, i.e., updating the outer weights infinitely faster than the hidden ones, learns the new task-specific feature while preserving the pre-trained ones in the model representation. Moreover, only O(d)\mathcal{O}(d) fine-tuning samples are required for this recovery, independently of the number of pre-trained features. In contrast, with random initialization, the same number of samples is insufficient to recover the target parameters. Our results therefore demonstrate that pre-training can induce an implicit bias with a clear statistical advantage over random initialization, enabling feature learning from scarce fine-tuning data.
May 8, 2026

OrScale: Orthogonalised Optimization with Layer-Wise Trust-Ratio Scaling

Muon fixes the direction of every matrix-valued update at the polar factor of its momentum, while each layer's step magnitude is addressed only by a static shape correction. We derive a dynamic per-layer scalar by adapting the LARS/LAMB trust-ratio principle to the orthogonalized setting, where the standard denominator candidates---the raw momentum norm or the polar-factor norm---either live in the wrong unit space or carry no update-scale information. The resulting method, OrScale, uses the norm of the parameter-space direction actually applied and anchors each layer's ratio at one via a per-layer calibration, so that the Moonlight recipe (tuned for AdamW, shared with Muon via RMS matching) transfers with no additional sweep; a component ablation confirms each design choice is individually load-bearing. Theoretically, OrScale retains a nuclear-norm O(1/T)O(1/\sqrt{T}) convergence rate for any clipped multiplier and achieves a strict layer-adaptive descent gain κeff>1κ_{\mathrm{eff}}>1 under two conditions estimable from standard training diagnostics---a bound that predicts the gain should grow with architectural heterogeneity. Experiments confirm the prediction: with every hyperparameter inherited verbatim from the Moonlight recipe, OrScale matches or beats Muon+Moonlight across dense 125M--1.1B FineWeb-Edu pre-training, and on a 16B-A3B mixture-of-experts model---where the logged trust ratios separate cleanly by layer class---the gap widens by an order of magnitude to 0.1300.130 nats (3.8%3.8\% relative) at parity wall-clock cost.