arXiv:2112.07628v3 cs.LG

다층 과매개변수화 신경망의 준이차 시간 학습

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

Zhao Song, Lichen Zhang, Ruizhe Zhang

제출 2021-12-14

한국어 초록

본 연구는 손실 함수로부터 유도되는 경험적 위험을 최소화하기 위해 다층 과매개변수화 신경망의 마지막 층을 학습하는 문제를 다룬다. 과매개변수화의 전형적인 설정에서는 네트워크 너비 $m$이 데이터 차원 $d$와 학습 표본 수 $n$보다 훨씬 크며($m=\mathrm{poly}(n,d)$), 이로 인해 첫 번째 층 이후의 각 층마다 매우 큰 가중치 행렬 $W\in\mathbb{R}^{m\times m}$이 생긴다. 층 입력이 밀집(dense)한 경우 순진하게는 순전파와 역전파 계산 모두에서 가중치 행렬을 읽고 신경망 함수를 평가하는 데 $O(m^2)$ 시간을 들여야 한다. 반복당 학습 비용을 줄이기 위해, 초기화 단계에서 $O(m^2nL)$ 시간을 사용하고 $m$에 대해 반복당 진정한 준이차 분할 상환 비용, 즉 반복당 $m^{2-\Omega(1)}$을 달성하는 프레임워크를 제안한다. 이러한 속도 향상은 희소 활성화에서 비롯되는데, 이는 각 층의 임계값이 해당 층 입력의 노름에 비례하는 이동된 ReLU이다. 이 임계값을 사용하면 모든 층이 양의 동차성을 가지므로, 수렴 증명에는 깊이 $L$, $n$, 그리고 가장 작은 커널 고유값의 역수에 대해 다항식 수준의 너비만 필요하다. 학습되는 층의 입력은 고정되어 있고 희소하다. 이 설정에서는 자료구조가 없는 더 단순한 알고리즘도 같은 반복당 비용에 도달하며, 마지막 층과 그 입력의 곱을 유지하면 비용이 $mn^{\omega-1+o(1)}$으로 낮아진다. 여기서 $\omega$는 행렬 곱셈 지수이다. 본 결과는 대규모 언어 모델(LLM)을 배포하기 위한 핵심 절차인 미세 조정을 가속하기 위해, 고정된 사전 학습 모델 위에 소량의 상태를 유지하는 방식에 대한 이상화된 모델로 볼 수 있다. 본 보장은 고정된 층이 무작위라고 가정하며, 사전 학습된 모델의 경우에는 이러한 곱을 유지하는 반복당 비용만 그대로 적용된다.

원문 초록

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 $m$ is much larger than the data dimension $d$ and the number of training samples $n$ ($m=\mathrm{poly}(n,d)$), which induces a prohibitively large weight matrix $W\in\mathbb{R}^{m\times m}$ per layer above the first. Naively, when the layer inputs are dense, one has to pay $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(m^2nL)$ time in the initialization phase and achieves a truly subquadratic amortized cost per iteration in terms of $m$, i.e., $m^{2-\Omega(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 $L$, in $n$ 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^{\omega-1+o(1)}$, where $\omega$ 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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2112.07628v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.