跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2112.07628 · v3

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

首次提交 2021-12-15 02:13
版本更新 2026-11-16 11:26
雷达观测 2026-11-17 17:12
arXiv ↗PDF ↗

摘要

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.

作者备注:ITCS 2024. This version corrects the analysis: the threshold of each layer now scales with the norm of the layer input, which removes a factor exponential in the depth from the width, and the claims are narrowed to training the last layer at an amortized cost per iteration. It also adds simpler and faster algorithms for this setting

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-16 11:26 · 最新观测版本

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

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.

查看此版本解读 →查看此版本原文 ↗