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

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

    Sep 28, 2026Etienne Boursier, Nicolas FlammarionRepresentation LearningFine-Tuning