기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

요약

확률적 최적화는 기계 학습의 핵심 구성 요소이며, 그 핵심에는 60여년 전에 처음 제안된 이후 널리 사용되어 온 방법인 확률적 경사하강법 알고리즘(SGD)이 있습니다. 지난 8년 동안 우리는 확률론적 최적화 방법을 위한 분산 감소 기술이라는 흥미진진한 새로운 개발을 목격했습니다. 이러한 분산 감소 방법(VR 방법)은 훈련 데이터의 여러 반복을 허용하는 시나리오에서 잘 수행되며 이론과 실제 모두에서 SGD보다 빠른 수렴을 보여줍니다. 이러한 속도 증가는 VR 방법에 대한 관심이 높아지고 이 분야에서 빠르게 축적되는 연구 성과를 강조합니다. 이 기사에서는 비전문가 독자에게 정보를 제공하기 위해 제한된 데이터 세트 최적화를 위한 VR 방법의 주요 원칙과 주요 발전 사항을 검토합니다. 우리는 주로 볼록 최적화 환경에 중점을 두고 비볼록 함수 최소화 확장에 관심이 있는 독자를 위한 참고 자료를 제공합니다.

핵심 단어 | 머신러닝 최적화;

1. 소개

머신러닝 연구 분야에서 기본적이고 중요한 문제는 거대한 데이터 세트에 모델을 어떻게 적응시키는가입니다. 예를 들어 선형 최소 제곱 모델의 일반적인 경우를 고려해 볼 수 있습니다.

$${엑스}^{\ast }\in \mathrm{아르g}\underset{엑스\in {아르\; 자형}^{디}}{분}\frac{1}{N}\sum _{나=1}^N({ㅏ}_{나}^{티}엑스-{비}_{나}{)}^2$$

이 모델에서 우리는 $디$ 벡터로 표현되는 매개변수$엑스\in {아르\; 자형}^{디}$ 주어진.그동안 우리는 가지고 있습니다.$N$ 특징 벡터를 포함한 데이터 포인트${ㅏ}_{나}\in {아르\; 자형}^{디}$ 그리고 목표값${비}_{나}\in 아르\; 자형$ .모델의 적응 프로세스는 모델의 예측 결과가 나오도록 이러한 매개변수를 조정하는 것입니다.${ㅏ}_{나}^{티}엑스$ 평균적으로 목표값에 최대한 가깝게${비}_{나}$。

더 광범위하게는 손실 함수를 사용할 수 있습니다. ${에프}_{나}(엑스)$ 모델 예측과$나$ 데이터 포인트가 얼마나 가까운지:

$${엑스}^{\ast }\in \mathrm{아르g}\underset{엑스\in {아르\; 자형}^{디}}{분}에프(엑스):=\frac{1}{N}\sum _{나=1}^N{에프}_{나}(엑스)$$

손실 함수 ${에프}_{나}(엑스)$ 더 크면 모델의 예측이 데이터에서 크게 벗어난다는 것을 나타냅니다.${에프}_{나}(엑스)$ 0과 같으면 모델이 데이터 포인트에 완벽하게 맞습니다.기능$에프(엑스)$ 전체 데이터 세트에 대한 모델의 평균 손실을 반영합니다.

위의 형식 (2)와 같은 문제는 선형 최소 제곱 문제뿐만 아니라 기계 학습에서 연구된 다른 많은 모델에도 적용됩니다. 예를 들어 로지스틱 회귀 모델에서는 다음을 해결합니다.

$${엑스}^{\ast }\in \mathrm{아르g}\underset{엑스\in {아르\; 자형}^{디}}{분}\frac{1}{N}\sum _{나=1}^N\mathrm{봐라g}(1+{이자형}^{-{비}_{나}{ㅏ}_{나}^{티}엑스})+\frac{\lambda }{2}\Vert 엑스{\Vert }_2^2$$

여기에서 우리가 다루고 있는 것은 bi ∈ { − 1 , + 1 } b_i {-1, +1}비나​∈{−1,+1} 이진 분류 문제의 경우 예측은 다음을 기반으로 합니다.${ㅏ}_{나}^{티}엑스$ 기호.정규화 용어도 공식에 도입되었습니다.$\frac{\lambda }{2}\Vert 엑스{\Vert }_2^2$ 데이터의 과적합을 방지하기 위해$\Vert 엑스{\Vert }_2^2$ 표현하다$엑스$ 유클리드 노름의 제곱입니다.

대부분의 지도 학습 모델에서 훈련 프로세스는 L1 정규화된 최소 제곱, SVM(지원 벡터 머신), 주성분 분석, 조건부 무작위 필드 및 심층 신경망 등을 포함하여 형식 (2)로 표현될 수 있습니다.

현대 문제 사례의 주요 과제는 데이터 포인트의 수입니다. $N$ 아마도 매우 클 것입니다. 우리는 종종 테라바이트 범위를 훨씬 뛰어 넘는 데이터 세트를 다루고 인터넷, 위성, 원격 센서, 금융 시장 및 과학 실험과 같은 다양한 소스에서 얻을 수 있습니다. 이러한 대규모 데이터 세트를 처리하기 위해 일반적인 접근 방식은 각 반복에서 무작위로 선택된 소수의 데이터 포인트만 사용하는 SGD(확률적 경사하강법) 알고리즘을 사용하는 것입니다. 또한, 최근에는 기존의 확률적 경사법보다 수렴 속도가 빠른 분산 감소(VR) 확률적 경사법에 대한 관심이 급증하고 있습니다.

그림 1. 버섯 데이터세트[7]를 기반으로 한 로지스틱 회귀 문제에서 경사하강법(GD), 가속 경사하강법(AGD, [50]의 가속 GD), 확률적 경사하강법(SGD) 및 ADAM[30] 방법이 사용되었습니다. 분산 감소(VR) 방법 SAG 및 SVRG(n = 8124, d = 112)와 비교됩니다.

1.1 경사 및 확률적 경사하강법

경사하강법(GD)은 위의 문제(2)를 해결하기 위해 사용되는 고전적인 알고리즘이며, 반복 업데이트 공식은 다음과 같습니다.
$${엑스}_{케이+1}={엑스}_{케이}-\gamma \frac{1}{N}\sum _{나=1}^N\nabla {에프}_{나}({엑스}_{케이})$$

여기,$\gamma$ 0보다 큰 고정 단계 값입니다.GD 알고리즘을 반복할 때마다 각 데이터 포인트는 다음과 같아야 합니다.$나$ 기울기 계산$\nabla {에프}_{나}({엑스}_{케이})$이는 GD가 모든 것을 요구한다는 것을 의미합니다. $N$ 데이터 포인트의 완전한 순회를 수행합니다.데이터 세트의 크기가$N$ 크기가 매우 커지면 GD 알고리즘을 반복할 때마다 비용이 매우 높아 적용이 제한됩니다.

대안으로 Robbins와 Monro가 처음 제안한 SGD(Stochastic Gradient Descent) 방법을 고려할 수 있으며, 그 반복 업데이트 공식은 다음과 같습니다.
$${엑스}_{케이+1}={엑스}_{케이}-\gamma \nabla {에프}_{{나}_{케이}}({엑스}_{케이})$$

SGD 알고리즘은 각 반복에서 무작위로 선택된 하나의 데이터 포인트의 기울기만 사용하여 작동합니다. $\nabla {에프}_{{나}_{케이}}({엑스}_{케이})$ 각 반복의 비용을 줄이기 위해. 그림 1에서 SGD는 최적화 프로세스의 초기 단계에서 GD(가속 GD 방법 포함)보다 더 중요한 진전을 달성하는 것을 볼 수 있습니다.그래프는 모든 계산으로 정의되는 에포크 측면에서 최적화 진행 상황을 보여줍니다.$N$ 훈련 샘플의 기울기 수입니다. GD 알고리즘은 각 라운드에서 한 번의 반복을 수행하는 반면 SGD 알고리즘은 각 라운드에서 한 번의 반복을 수행합니다.$N$ 반복.우리는 SGD와 GD를 비교하기 위한 기초로 라운드를 사용합니다.$N$ 매우 큰 경우 두 방법의 주요 비용은 기울기에 집중됩니다.$\nabla {에프}_{나}({엑스}_{케이})$ 계산.

1.2. 분산 문제

무작위 인덱싱을 고려해 봅시다 ${나}_{케이}$ 컬렉션에서 { 1 , … , n } {1, 점, n}{1,…,N} 균일 무작위 선택의 경우 이는 모든$나$,선택하다 ${나}_{케이}=나$ 확률$피[{나}_{케이}=나]$ 동일한$\frac{1}{N}$ . 이 경우,$\nabla {에프}_{{나}_{케이}}({엑스}_{케이})$ ~처럼$\nabla 에프({엑스}_{케이})$ 기대값의 정의에 따르면 다음과 같은 추정자가 편향되지 않습니다.
$$이자형[\nabla {에프}_{{나}_{케이}}({엑스}_{케이})|{엑스}_{케이}]=\frac{1}{N}\sum _{나=1}^N\nabla {에프}_{나}({엑스}_{케이})=\nabla 에프({엑스}_{케이})(6)$$

SGD(Stochastic Gradient Descent) 방법은 각 iteration에서 기능을 보장하지 않지만 $에프$ 값은 감소하지만 평균적으로 하향 방향을 나타내는 음의 전체 기울기 쪽으로 이동합니다.

그러나 편향되지 않은 기울기 추정기를 갖는 것만으로는 SGD 반복의 수렴을 보장하는 데 충분하지 않습니다. 이를 설명하기 위해 그림 2(왼쪽)는 LIBSVM[7]에서 제공하는 4개 범주 데이터 세트에 일정한 단계 크기를 사용하여 로지스틱 회귀 함수를 적용할 때 SGD의 반복 궤적을 보여줍니다.그림의 동심 타원은 함수의 윤곽, 즉 함수 값을 나타냅니다.$에프(엑스)=씨$ 대응점$엑스$ 모으다,$씨$ 실수 집합의 특정 상수입니다.다른 상수 값$씨$ 다양한 타원에 해당합니다.

SGD의 반복 궤적은 최적의 솔루션(그림에서 녹색 별표로 표시)으로 수렴되지 않고 최적의 솔루션 주위에 포인트 클라우드를 형성합니다. 대조적으로, 그림 2에서는 나중에 소개할 동일한 일정한 단계 크기를 사용하는 분산 감소(VR) 방법인 확률적 평균 기울기(SAG)의 반복 궤적을 보여줍니다. 이 예에서 SGD가 수렴하지 못하는 이유는 확률적 기울기 자체가 0으로 수렴하지 않기 때문에 일정 단계 SGD 방법(5)이 절대 멈추지 않기 때문입니다.이는 다음과 같이 자연스럽게 멈추는 경사하강법(GD) 방법과 뚜렷한 대조를 이룹니다.${엑스}_{케이}$ 구혼${엑스}^{\ast }$,구배 $\nabla 에프({엑스}_{케이})$ 0이 되는 경향이 있을 것입니다.

그림 2. 고정 단계 SGD(왼쪽) 및 SAG(오른쪽) 반복 방법을 사용한 2차원 로지스틱 회귀에 대한 수준 집합 도표. 녹색 별표는 x를 나타냅니다.풀다.

1.3. 고전적인 분산 감소 방법

처리로 인해 $\nabla {에프}_{나}({엑스}_{케이})$ 값의 분산으로 인해 발생하는 비수렴 문제에 대한 몇 가지 고전적인 기술이 있습니다.예를 들어 Robbins와 Monro[64]는 일련의 감소 단계를 사용합니다.${\gamma }_{케이}$ 차이 문제를 해결하고 제품이${\gamma }_{케이}\nabla {에프}_{{나}_{케이}}({엑스}_{케이})$ 0으로 수렴할 수 있습니다. 그러나 알고리즘이 너무 일찍 또는 너무 늦게 중지되는 것을 방지하기 위해 이러한 감소 단계 순서를 조정하는 것은 어려운 문제입니다.

분산을 줄이는 또 다른 고전적인 기술은 여러 개의 변수를 사용하는 것입니다. $\nabla {에프}_{나}({엑스}_{케이})$ 전체 기울기를 얻기 위한 평균$\nabla 에프(엑스)$ 좀 더 정확한 추정. 이 접근 방식을 미니배치라고 하며 여러 기울기를 병렬로 평가할 수 있는 경우 특히 유용합니다. 결과적으로 다음 형식이 반복됩니다.
$${엑스}_{케이+1}={엑스}_{케이}-\gamma \frac{1}{|{비}_{케이}|}\sum _{나\in {비}_{케이}}\nabla {에프}_{나}({엑스}_{케이})(7)$$
~에${비}_{케이}$ 무작위 인덱스 세트입니다.$|{비}_{케이}|$ 표현하다${비}_{케이}$ 의 크기.만약에${비}_{케이}$ 대체를 통해 균일하게 샘플링하면 이 경사 추정의 분산은 "배치 크기"와 관련됩니다.$|{비}_{케이}|$ 반비례하므로 배치 크기를 늘려 분산을 줄일 수 있습니다.

그러나 이러한 반복 비용은 배치 크기에 비례하므로 이러한 형태의 분산 감소는 계산 비용이 증가하는 대가를 치르게 됩니다.

분산을 줄이고 SGD의 경험적 성능을 향상시키는 또 다른 일반적인 전략은 이전 단계에서 사용된 방향을 기반으로 하는 추가 용어인 "모멘텀"을 추가하는 것입니다. 특히 모멘텀을 갖는 SGD의 형태는 다음과 같습니다.
$${엑스}_{케이+1}={엑스}_{케이}-\gamma {중}_{케이}(9)$$
여기서 운동량 매개변수는$\beta$ (0, 1) 범위에 위치합니다.초기 추진력이라면${중}_0=0$, (8)에서 확장합니다. ${중}_{케이}$ 업데이트를 위해 우리는${중}_{케이}$ 이전 그라디언트의 가중 평균입니다.
$${중}_{케이}=\sum _{티=0}^{케이}{\beta }^{케이-티}\nabla {에프}_{{나}_{티}}({엑스}_{티})(10)$$
그러므로,${중}_{케이}$ 확률적 기울기의 가중 합입니다.왜냐하면${\sum }_{티=0}^{케이}{\beta }^{케이-티}=\frac{1-{\beta }^{케이+1}}{1-\beta }$, 우리는 변환할 수 있습니다 $\frac{1-\beta }{1-{\beta }^{케이}}{중}_{케이}$ 확률적 기울기의 가중 평균으로 간주됩니다.이것을 완전 그래디언트에 대한 표현식과 비교하면$\nabla 에프({엑스}_{케이})=\frac{1}{N}{\sum }_{나=1}^N\nabla {에프}_{나}({엑스}_{케이})$ 비교하자면,$\frac{1-\beta }{1-{\beta }^{케이}}{중}_{케이}$(게다가 ${중}_{케이}$ )은 완전한 기울기의 추정치로 해석됩니다. 이 가중 합계는 분산을 줄이는 동시에 중요한 문제도 발생시킵니다.가중치 합(10)은 최근 샘플링된 그라디언트에 더 많은 가중치를 부여하므로 전체 그라디언트로 수렴되지 않습니다.$\nabla 에프({엑스}_{케이})$ , 후자는 단순 평균입니다. 섹션 II-A에서 볼 첫 번째 분산 감소 방법은 가중 평균 대신 단순 평균을 사용하여 이 문제를 해결합니다.

1.4. 현대적인 분산 감소 방법

고전적인 방법과 달리 하나 이상의 직접 사용 $\nabla {에프}_{나}({엑스}_{케이})$ ~처럼$\nabla 에프({엑스}_{케이})$ 근사치로서 최신 분산 감소(VR) 방법은 다른 전략을 사용합니다.이러한 방법은$\nabla {에프}_{나}({엑스}_{케이})$ 기울기 추정을 업데이트하려면$g_{케이}$, 그의 목표는 $g_{케이}$ 접근하다$\nabla 에프({엑스}_{케이})$ .구체적으로 우리는 희망합니다$g_{케이}$ 만족시킬 수 있는$g_{케이}\approx \nabla 에프({엑스}_{케이})$ . 이러한 그래디언트 추정을 기반으로 다음 형식의 대략적인 그래디언트 단계를 수행합니다.
$${엑스}_{케이+1}={엑스}_{케이}-\gamma g_{케이}(11)$$
여기$\gamma >0$ 단계 크기 매개변수입니다.

일정한 단계 크기가 사용되도록 하려면 $\gamma$ 반복(11)이 수렴할 수 있으면 기울기 추정이 다음과 같은지 확인해야 합니다.$g_{케이}$ 분산은 0이 되는 경향이 있습니다. 수학적으로 이는 다음과 같이 표현될 수 있습니다.
$$이자형\left[\Vert g_{케이}-\nabla 에프({엑스}_{케이}){\Vert }^2\right]\to 0\text{~처럼}케이\to \infty (12)$$
여기에 기대$이자형$ 알고리즘을 기반으로 하여$케이$ 반복을 위해 모든 확률 변수가 계산됩니다. 속성(12)은 최적의 솔루션에 도달하면 VR 방법을 중지할 수 있도록 보장합니다. 우리는 이 속성을 VR 접근 방식의 특징적인 특징으로 간주하므로 이를 VR 속성이라고 부릅니다. 실제로 분산이 0이 되는 경향이 있기 때문에 "감소된" 분산이라는 표현이 오해의 소지가 있을 수 있다는 점은 주목할 가치가 있습니다. 속성(12)은 VR 방법이 이론(적절한 가정 하에서)과 실제(그림 1 참조)에서 더 빠른 수렴을 달성할 수 있게 하는 핵심 요소입니다.

1.5. 분산 감소 방법의 첫 번째 예: SGD²

간단한 개선 방법은 SGD 재귀 공식(5)이 단계 크기를 줄이지 않고 수렴하도록 할 수 있습니다. 즉, 각 기울기를 빼는 것입니다. $\nabla {에프}_{나}({엑스}^{\ast })$, 이 방법은 다음과 같이 정의됩니다.
$${엑스}_{케이+1}={엑스}_{케이}-\gamma (\nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({엑스}^{\ast }))(13)$$
이 방법을 SGD²라고 합니다[22].우리는 일반적으로 모든 것을 확실히 알 수는 없지만$\nabla {에프}_{나}({엑스}^{\ast })$ , 그러나 예를 들어 SGD²는 분산 감소 방법의 기본 특성을 잘 설명할 수 있습니다.또한, 많은 분산 감소 방법은 SGD² 방법의 대략적인 형태로 볼 수 있습니다. 이러한 방법은 알려진 방법에 의존하지 않습니다.$\nabla {에프}_{나}({엑스}^{\ast })$대신에 다음과 같은 근사값을 얻을 수 있는 방법을 사용하십시오. $\nabla {에프}_{나}({엑스}^{\ast })$ 추정 값.

SGD²가 전체 기울기의 편향되지 않은 추정치를 사용한다는 점은 주목할 가치가 있습니다.왜냐하면$\nabla 에프({엑스}^{\ast })=0$,에프:
$$이자형[\nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({엑스}^{\ast })]=\nabla 에프({엑스}_{케이})-\nabla 에프({엑스}^{\ast })=\nabla 에프({엑스}_{케이})$$
또한 SGD²가 최적의 솔루션에 도달하면 자연스럽게 중지됩니다.$나$,가지다:
$$(\nabla {에프}_{나}(엑스)-\nabla {에프}_{나}({엑스}^{\ast })){|}_{엑스={엑스}^{\ast }}=0$$

추가로 관찰한 결과, ${엑스}_{케이}$ 가까운${엑스}^{\ast }$(연속 $\nabla {에프}_{나}$), SGD²는 다음과 같은 이유로 분산 감소 속성(12)을 충족합니다.
$$\begin{gathered} 이자형\left[\Vert g_{케이}-\nabla 에프({엑스}_{케이}){\Vert }^2\right]= \\ 이자형\left[\Vert \nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({엑스}^{\ast })-\nabla 에프({엑스}_{케이}){\Vert }^2\right]\le 이자형\left[\Vert \nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({엑스}^{\ast }){\Vert }^2\right] \end{gathered}$$
여기서는 Lemma 2를 사용합니다.$엑스=\nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({엑스}^{\ast })$, 그리고 이점을 활용했습니다. $이자형[\nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({엑스}^{\ast })]=\nabla 에프({엑스}_{케이})$ 자연. 이 속성은 SGD²가 부록 B에 자세히 설명된 기존 SGD 방법보다 수렴 속도가 더 빠르다는 것을 나타냅니다.

1.6. 분산 감소 방법의 신속한 수렴

이 섹션에서는 분산 감소(VR) 방법을 분석하는 데 사용되는 두 가지 표준 가정을 소개하고 이러한 가정에서 얻을 수 있는 가속 효과를 기존 SGD 방법과 비교하여 논의합니다. 먼저, 그래디언트에 Lipschitz 연속성이 있다고 가정합니다. 이는 그래디언트의 변화율이 유한하다는 것을 의미합니다.

가정 1(립시츠 연속성)

우리는 다음과 같은 기능을 한다고 가정합니다. $에프$는 미분가능하고 $엘$- 모두에게 부드럽습니다. $엑스$ 그리고$와이$ 그리고 누군가$0<엘<\infty$,다음 조건:
$$\Vert \nabla 에프(엑스)-\nabla 에프(와이)\Vert \le 엘\Vert 엑스-와이\Vert (14)$$
이는 모든$에프나:{아르\; 자형}^{디}\to 아르\; 자형$ 미분가능하다,${엘}_{나}$- 매끄럽게, 우리가 정의합니다 ${엘}_{\text{최대}}$ ~을 위한 최대 ⁡ { L 1 , . . . , L n } 최대 {L_1, . . . , L_n}최대{엘1​,...,엘N​}。

이는 일반적으로 약한 가정으로 간주되지만 다음 장에서는 매끄럽지 않은 문제에 적합한 VR 방법에 대해 논의할 것입니다. 두 번 미분 가능한 일변량 함수의 경우,$엘$-부드러움은 다음과 같이 직관적으로 이해될 수 있습니다. 이는 2차 도함수가 다음과 같다고 가정하는 것과 동일합니다. $엘$ 상한선, 즉$|{에프}^{\prime \prime }(엑스)|\le 엘$ 모든$엑스\in {아르\; 자형}^{디}$ .다중 변수의 두 번 미분 가능한 함수의 경우 헤세 행렬을 가정하는 것과 동일합니다.${\nabla }^2에프(엑스)$ 특이값$엘$ 상한.

가정 2(강한 볼록성)

우리가 고려하는 두 번째 가설은 함수 (f)가 ​​다음과 같다는 것입니다. $\mu$-강하게 볼록하다는 것은 특정한 경우를 의미합니다. $\mu >0$,기능 $엑스\mapsto 에프(엑스)-\frac{\mu }{2}\Vert 엑스{\Vert }^2$ 볼록합니다.게다가, 각각에 대해$나=1,...,N$，$에프나:{아르\; 자형}^{디}\to 아르\; 자형$ 볼록합니다.

이것은 강력한 가정입니다.최소제곱 문제에서 각 (fi$는 볼록하지만 전체 함수(f)는 설계 행렬에만 있습니다.$ㅏ:=[{ㅏ}_1,...,{ㅏ}_N]$ 완벽한 행 순위를 갖는 경우에만 강하게 볼록합니다. L2 정규화된 로지스틱 회귀 문제는 정규화 항의 존재로 인해 이 가정을 충족합니다.$\mu \ge \lambda$。

이러한 가정을 충족하는 중요한 문제 클래스는 다음 형식의 최적화 문제입니다.
$${엑스}^{\ast }\in \mathrm{아르g}\underset{엑스\in {아르\; 자형}^{디}}{분}에프(엑스)=\frac{1}{N}\sum _{나=1}^N{\ell }_{나}({ㅏ}_{나}^{티}엑스)+\frac{\lambda }{2}\Vert 엑스{\Vert }^2(15)$$
여기서 각 "손실" 기능은${\ell }_{나}:아르\; 자형\to 아르\; 자형$ 는 두 번 미분가능하며, 2차 도함수는${\ell }_{나}^{\prime \prime }$ 0과 일부 상한으로 제한됩니다.$중$ 사이. 여기에는 최소 제곱, 로지스틱 회귀, 프로빗 회귀, Huber 로버스트 회귀 등과 같은 기계 학습의 L2 정규화를 사용한 다양한 손실 함수가 포함됩니다.이 경우 모든 사람에게$나$,우리는 ${엘}_{나}\le 중\Vert {ㅏ}_{나}{\Vert }^2+\lambda$ 그리고$\mu \ge \lambda$。

이러한 가정 하에서 경사하강법(GD) 방법의 수렴률은 조건수에 의해 결정됩니다. $\kappa :=엘/\mu$ 결정하다. 조건수는 항상 1보다 크거나 같고, 1보다 상당히 크면 함수의 윤곽이 매우 타원형이 되어 GD 방법의 반복이 진동하게 됩니다.반대로, 언제$\kappa$ 1에 가까울수록 GD 방법이 더 빠르게 수렴됩니다.

가정 1과 2에서 VR 방법은 선형 속도로 수렴합니다.무작위 방법({f(x_k)})의 함수 값은 다음과 같이 주어진다고 말합니다.$0<\rho \le 1$ 상수가 존재하는 경우 선형 수렴 속도(예상 하에)$씨>0$ 제조사:
$$이자형[에프({엑스}_{케이})]-에프({엑스}^{\ast })\le (1-\rho {)}^{케이}씨=영형(\mathrm{경험치}(-케이\rho ))\forall 케이(16)$$
이는 각 반복에서 편향되지 않은 기울기 추정에만 의존하고 다음 가정 하에서 하위선형 속도만 얻는 기존 SGD 방법과 대조됩니다.
$$이자형[에프({엑스}_{케이})]-에프({엑스}^{\ast })\le 영형(1/케이)$$
이 부등식을 만족하는 최소값$케이$ 이를 알고리즘의 반복 복잡도라고 합니다. 다음은 GD, SGD 및 VR 방법의 기본 변형에 대한 반복 복잡성과 한 번의 반복 비용입니다.

알고리즘의 총 실행 시간은 반복 복잡성과 반복 실행 시간의 곱으로 결정됩니다.여기서 사용됨${\kappa }_{\text{최대}}:={\mathrm{최대}}_{나}{엘}_{나}/\mu$ .알아채다${\kappa }_{\text{최대}}\ge \kappa$; 따라서 GD의 반복 복잡도는 VR 방법의 반복 복잡도보다 작습니다.

그러나 GD의 반복당 비용은 VR 방식과 동일하므로 $N$ 전체 러닝타임 측면에서는 VR 방식이 우월하다.

기존 SGD 방법의 장점은 실행 시간과 수렴 속도가 다음 요소에 의존하지 않는다는 것입니다. $N$, 하지만 허용오차가 있습니다. $ϵ$ 의 의존성은 훨씬 더 나쁩니다. 이는 허용 오차가 작을 때 SGD의 성능 저하를 설명합니다.

부록 B에서는 SGD² 방법이 VR 방법과 동일한 반복 복잡성을 가짐을 보여주는 간단한 증명을 제공합니다.

2. 기본 분산 감소 방법

분산 감소(VR) 방법의 개발은 여러 단계를 거쳤으며, 초기 방법 배치에서는 수렴률이 크게 향상되었습니다. 이 일련의 방법의 시작은 SAG 알고리즘입니다. 이어 SDCA(Stochastic Dual Coordinate Ascent) 알고리즘, MISO 알고리즘, SVRG/S2GD(Stochastic Variance Reduction Gradient) 알고리즘, SAGA('향상된' SAG라는 뜻) 알고리즘이 차례로 나왔다.

이 장에서는 이러한 선구적인 VR 방법에 대해 자세히 설명합니다. 4장에서는 특정 애플리케이션 시나리오에서 이러한 기본 방법에 비해 우수한 특성을 보여주는 몇 가지 새로운 방법을 살펴보겠습니다.

2.1. 확률적 평균 기울기 방법(SAG)

첫 번째 VR(분산 감소) 방법에 대한 탐구는 전체 그래디언트 구조를 모방하는 것부터 시작됩니다.완전한 그라데이션이기 때문에$\nabla 에프(엑스)$ 전부다$\nabla {에프}_{나}(엑스)$ 기울기의 단순 평균과 전체 기울기 추정치$g_{케이}$ 또한 이러한 기울기 추정치의 평균이어야 합니다. 이 아이디어는 우리의 첫 번째 VR 방법인 SAG(확률적 평균 기울기) 방법을 탄생시켰습니다.

SAG 방법[37], [65]은 초기 IAG(Incremental Aggregated Gradient) 방법[4]의 무작위 버전입니다. SAG의 핵심 아이디어는 각 데이터 포인트에 대해$나$ 견적을 유지하다$V_{좋아요}\approx \nabla {에프}_{나}({엑스}_{케이})$ .그런 다음 이것을 사용하십시오$V_{좋아요}$ 값의 평균은 전체 기울기의 추정치로 사용됩니다. 즉,
$${\bar{g}}_{케이}=\frac{1}{N}\sum _{제이=1}^N{V}_{농담이야}\approx \frac{1}{N}\sum _{제이=1}^N\nabla {에프}_{제이}({엑스}_{케이})=\nabla 에프({엑스}_{케이})(18)$$

SAG의 각 반복에서 세트의 { 1 , … , n } {1, 점, n}{1,…,N} 다음에서 인덱스를 추출합니다.${나}_{케이}$, 다음 규칙에 따라 업데이트됩니다. $V_{농담이야}$：
$$V_{농담이야}^{케이+1}=\{\begin{array}{ll}\nabla {에프}_{{나}_{케이}}({엑스}_{케이}),& \text{만약에}제이={나}_{케이}\\ V_{농담이야}^{케이},& \text{만약에}제이\ne {나}_{케이}\end{array}(19)$$
그 중에는 각각$V_{0나}$ 0으로 초기화될 수 있습니다.$\nabla {에프}_{나}({엑스}_0)$ 대략적인 값.솔루션으로${엑스}^{\ast }$ 근사치, 각각$V_{좋아요}$ 점차적으로 수렴할 것이다.$\nabla {에프}_{나}({엑스}^{\ast })$, 이로써 VR 특성(12)을 만족시킨다.

SAG를 효율적으로 구현하기 위해서는 계산에 주의가 필요합니다. ${\bar{g}}_{케이}$ 매번 처음부터 합계를 시작하는 것을 피하기 위해$N$ 벡터이기 때문에$N$ 크기가 크면 비용이 높습니다.다행스럽게도 각 반복에는 하나만 있으므로$V_{좋아요}$ 조건은 변경되므로 매번 전체 합계를 다시 계산할 필요가 없습니다.특히 반복하는 동안 다음과 같이 가정합니다.$케이$ 다음에서 추출된 인덱스${나}_{케이}$, 다음이 있습니다:
$${\bar{g}}_{케이}=\frac{1}{N}\sum _{\begin{array}{c}제이=1\\ 제이\ne {나}_{케이}\end{array}}^N{V}_{농담이야}+\frac{1}{N}{V}_{{나}_{케이}}^{케이}={\bar{g}}_{케이-1}-\frac{1}{N}{V}_{{나}_{케이}}^{케이-1}+\frac{1}{N}{V}_{{나}_{케이}}^{케이}(20)$$

이후부터 $V_{{나}_{케이}}$ 제외한 모든 것$V_{농담이야}$ 값은 모두 동일하게 유지되며 각각을 저장합니다.$제이$ 다음에 해당하는 벡터$V_{제이}$ . 알고리즘 1은 SAG 방법의 구체적인 구현을 보여줍니다.

SAG는 선형 수렴을 달성하는 최초의 확률론적 방법이며 반복 복잡도는 다음과 같습니다. $영형(({\kappa }_{\text{최대}}+N)\mathrm{봐라g}(1/ϵ))$, 단계 크기 사용 $\gamma =영형(1/{엘}_{\text{최대}})$ . 이 선형 수렴은 그림 1에서 관찰할 수 있습니다.인해 주목할 가치가 있습니다.${엘}_{\text{최대}}$- 누구에게나 부드러운 기능 ${엘}^{\prime }\ge {엘}_{\text{최대}}$ 도${엘}^{\prime }$- 부드러운 SAG 방법은 실제로 조정하기 어려운 단계 크기가 감소하는 시퀀스에서만 하위 선형 속도를 달성하는 기존 SGD 방법과 달리 충분히 작은 단계 크기에 대해 선형 수렴 속도를 달성합니다.

당시 SAG의 선형 수렴은 각 반복에서 단 하나의 확률적 기울기(단일 데이터 포인트 처리)만 계산했기 때문에 상당한 발전이었습니다. 그러나 Schmidt et al.[65]이 제공한 수렴 증명은 매우 복잡하며 컴퓨터 검증 단계에 의존합니다. SAG를 분석하기 어려운 주요 이유는 다음과 같습니다.$g_{케이}$ 는 기울기의 편향된 추정치입니다.

다음으로, 공변량의 개념을 활용하여 유사한 성능을 가지지만 분석하기 더 쉬운 SAG 방법의 편향되지 않은 변형을 생성하는 SAG의 변형인 SAGA 방법을 소개합니다.

---

알고리즘 1: SAG 방법

1. 매개변수: 단계 크기 $\gamma >0$
2. 초기화:${엑스}_0$，$V_{나}=0\in {아르\; 자형}^{디}$ ~을 위한$나=1,\dots ,N$
3. 오른쪽 $케이=1,\dots ,티-1$ 구현하다:
   가. 무작위 선택 ik ∈ { 1 , … , n } i_k in { 1, ldots, n }나케이​∈{1,…,N}
   b. 계산하다${\bar{g}}_{케이}={\bar{g}}_{케이-1}-\frac{1}{N}{V}_{{나}_{케이}}^{케이-1}$
   다. 업데이트$V_{{나}_{케이}}^{케이}=\nabla {에프}_{{나}_{케이}}({엑스}_{케이})$
   d. 기울기 추정 업데이트${\bar{g}}_{케이}={\bar{g}}_{케이}+\frac{1}{N}{V}_{{나}_{케이}}^{케이}$
   마. 업데이트${엑스}_{케이+1}={엑스}_{케이}-\gamma {\bar{g}}_{케이}$
4. 산출:${엑스}_{티}$

2.2.SAGA 방식

감소된 기본 편향되지 않은 기울기 추정 $\nabla {에프}_{{나}_{케이}}({엑스}_{케이})$ 분산 접근법은 소위 공변량 또는 제어 변수를 사용하는 것입니다.~을 위한$나=1,\dots ,N$,설정 $V_{나}\in {아르\; 자형}^{디}$ 벡터입니다.이 벡터를 사용하여 전체 그래디언트를 변환할 수 있습니다.$\nabla 에프(엑스)$ 다음과 같이 다시 작성되었습니다.
$$\nabla 에프(엑스)=\frac{1}{N}\sum _{나=1}^N(\nabla {에프}_{나}(엑스)-V_{나}+V_{나})=\frac{1}{N}\sum _{나=1}^N\nabla {에프}_{나}(엑스)-V_{나}+\frac{1}{N}\sum _{제이=1}^N{V}_{제이}$$
$$:=\frac{1}{N}\sum _{나=1}^N\nabla {에프}_{나}(엑스,V)(21)$$
정의하는$\nabla {에프}_{나}(엑스,V):=\nabla {에프}_{나}(엑스)-V_{나}+\frac{1}{N}{\sum }_{제이=1}^N{V}_{제이}$ .이제 무작위로 샘플링할 수 있습니다.$\nabla {에프}_{나}(엑스,V)$ 완전한 그라디언트를 구성하려면$\nabla 에프(엑스)$ 편견 없는 추정 i ∈ { 1 , … , n } i in { 1, ldots, n }나∈{1,…,N}, SGD 방법을 적용하고 기울기 추정을 사용할 수 있습니다.
$$g_{케이}=\nabla {에프}_{{나}_{케이}}({엑스}_{케이},V)=\nabla {에프}_{{나}_{케이}}({엑스}_{케이})-V_{{나}_{케이}}+\frac{1}{N}\sum _{제이=1}^N{V}_{제이}(22)$$

관찰을 위해 $V_{나}$ 선택 쌍 차이$g_{케이}$ 영향력을 행사할 수 있습니다.$g_{케이}=\nabla {에프}_{{나}_{케이}}({엑스}_{케이},V)$ 대체하여 사용하세요${이자형}_{나}\sim \frac{1}{N}[V_{나}]=\frac{1}{N}{\sum }_{제이=1}^N{V}_{제이}$ 기대치를 계산하려면 다음을 얻습니다.
$$이자형\left[\Vert \nabla {에프}_{나}({엑스}_{케이})-V_{나}+{이자형}_{나}\sim \frac{1}{N}[V_{나}-\nabla {에프}_{나}({엑스}_{케이})]{\Vert }^2\right]\le 이자형\left[\Vert \nabla {에프}_{나}({엑스}_{케이})-V_{나}{\Vert }^2\right](23)$$
Lemma 2가 여기서 사용됩니다.$엑스=\nabla {에프}_{나}({엑스}_{케이})-V_{나}$ .이 경계(23)는 다음을 보여줍니다.$V_{나}$ 와 함께$케이$ 증가폭은 가까움$\nabla {에프}_{나}({엑스}_{케이})$ , VR 속성(12)을 얻을 수 있습니다.그게 우리가 전화하는 이유야$V_{나}$ 공변량이며 분산을 줄이기 위해 공변량을 선택할 수 있습니다.

예를 들어, 이 접근법은 SGD² 방법(13)으로도 구현됩니다. $V_{나}=\nabla {에프}_{나}({엑스}^{\ast })$ .그러나 이는 실제로는 잘 모르기 때문에 일반적으로 사용되지 않습니다.$\nabla {에프}_{나}({엑스}^{\ast })$ .좀 더 실용적인 옵션은$V_{나}$ 우리가 알고 있듯이${\overline{엑스}}_{나}\in {아르\; 자형}^{디}$ 근처의 경사$\nabla {에프}_{나}({\overline{엑스}}_{나})$ . 각 기능별 SAGA${에프}_{나}$ 참조점을 사용하다${\overline{엑스}}_{나}\in {아르\; 자형}^{디}$, 공변량 사용 $V_{나}=\nabla {에프}_{나}({\overline{엑스}}_{나})$, 각각은 ${\overline{엑스}}_{나}$ 우리의 마지막 평가가 될 거야${에프}_{나}$ 가리키다. 이러한 공변량을 사용하여 (22)에 따라 다음과 같은 기울기 추정을 구성할 수 있습니다.
$$g_{케이}=\nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({\overline{엑스}}_{{나}_{케이}})+\frac{1}{N}\sum _{제이=1}^N\nabla {에프}_{제이}({\overline{엑스}}_{제이})(24)$$

SAGA를 구현하기 위해 그라디언트를 저장할 수 있습니다. $\nabla {에프}_{나}({\overline{엑스}}_{나})$ 대신에$N$ 기준점${\overline{엑스}}_{나}$ .즉, 가정해보자$V_{제이}=\nabla {에프}_{제이}({\overline{엑스}}_{제이})$ ~을 위한 j ∈ { 1 , … , n } j는 { 1, ldots, n }에 있습니다.제이∈{1,…,N}, 각 반복에서 SAG와 같은 확률적 그래디언트를 업데이트합니다. $V_{제이}$。

알고리즘 2 사가

1. 매개변수: 단계 크기 $\gamma >0$
2. 초기화:${엑스}_0$，$V_{나}=0\in {아르\; 자형}^{디}$ ~을 위한$나=1,\dots ,N$
3. 지휘하다 $케이=1,\dots ,티-1$ 반복:
   가. 무작위 선택 ik ∈ { 1 , … , n } i_k in { 1, ldots, n }나케이​∈{1,…,N}
   b. 이전 값을 저장합니다.$V_{\text{오래된}}=V_{{나}_{케이}}$
   다. 업데이트$V_{{나}_{케이}}=\nabla {에프}_{{나}_{케이}}({엑스}_{케이})$
   D. 업데이트${엑스}_{케이+1}={엑스}_{케이}-\gamma (V_{{나}_{케이}}-V_{\text{오래된}}+{\bar{g}}_{케이})$
   e. 기울기 추정 업데이트${\bar{g}}_{케이}={\bar{g}}_{케이-1}+\frac{1}{N}(V_{{나}_{케이}}-V_{\text{오래된}})$
4. 산출:${엑스}_{티}$

SAGA 방법은 SAG와 동일한 반복 복잡성을 갖습니다. $영형(({\kappa }_{\text{최대}}+N)\mathrm{봐라g}(1/ϵ))$, 단계 크기 사용 $\gamma =영형(1/{엘}_{\text{최대}})$ , 그러나 증명은 훨씬 간단합니다.그러나 SAG와 마찬가지로 SAGA 방법에도 저장 공간이 필요합니다.$N$ 보조 벡터$V_{나}\in {아르\; 자형}^{디}$ ~을 위한$나=1,\dots ,N$, 이는 필요함을 의미한다. $영형(N디)$ 저장 공간의.언제$디$ 그리고$N$ 둘 다 큰 경우에는 실현 불가능할 수 있습니다. 다음 섹션에서는 정규화된 선형 모델과 같은 일반적인 모델에 대한 메모리 요구 사항을 줄이는 방법을 자세히 설명합니다.

할 수 있을 때 $N$ 두 개의 보조 벡터가 메모리에 저장되면 SAG와 SAGA는 비슷하게 동작하는 경향이 있습니다. 이 메모리 요구 사항이 너무 높으면 다음 섹션에서 검토할 SVRG 방법이 좋은 대안입니다. SVRG 방법은 동일한 수렴 속도를 달성하고 실제로는 거의 속도가 빠르지만$영형(디)$ 일반적인 문제에 대한 메모리.

2.3.SVRG 방법

SAGA 방법이 등장하기 전 일부 초기 연구에서는 SAG 방법에 필요한 높은 메모리 문제를 해결하기 위해 처음으로 공변량을 도입했습니다.이러한 연구는 고정된 기준점을 기반으로 합니다.$\overline{엑스}\in {아르\; 자형}^{디}$ 공변량, 해당 지점의 전체 기울기를 계산했습니다.$\nabla 에프(\overline{엑스})$ .참조점을 저장하여$\overline{엑스}$ 그리고 상응하는 완전한 그라디언트$\nabla 에프(\overline{엑스})$, 각각을 저장하지 않고도 이 작업을 수행할 수 있습니다. $\nabla {에프}_{제이}(\overline{엑스})$ 경우에는 사용${\overline{엑스}}_{제이}=\overline{엑스}$ 모든$제이$ 업데이트를 구현합니다(24).특히, 이러한 벡터를 저장하는 대신 각 반복에서 저장된 참조점을 활용합니다.$\overline{엑스}$ 계산하다$\nabla {에프}_{{나}_{케이}}(\overline{엑스})$ . 이 방법은 원래 다른 저자에 의해 다른 이름으로 제안되었으나 나중에 [28] 및 [84]의 명명법에 따라 SVRG 방법으로 통합되었습니다.

우리는 알고리즘 3에서 SVRG 방법을 공식화합니다.

(23)을 사용하여 기울기 추정을 유도할 수 있습니다. $g_{케이}$ 의 분산은 다음과 같이 제한됩니다.
$$이자형\left[\Vert g_{케이}-\nabla 에프({엑스}_{케이}){\Vert }^2\right]\le 이자형\left[\Vert \nabla {에프}_{나}({엑스}_{케이})-\nabla {에프}_{나}(\overline{엑스}){\Vert }^2\right]\le {엘}_{\text{최대}}^2\Vert {엑스}_{케이}-\overline{엑스}{\Vert }^2$$
여기서 두 번째 부등식은 각각을 사용합니다.${에프}_{나}$ ~의${엘}_{나}$-부드러움.

참고할만한 점은 $\overline{엑스}$ 현재 지점에 가까울수록${엑스}_{케이}$, 기울기 추정의 분산이 작아집니다.

SVRG 방법이 효과적이려면 참조점을 자주 업데이트해야 합니다. $\overline{엑스}$ (따라서 전체 기울기 계산이 필요함)은 분산 감소의 이점을 고려하여 평가됩니다.이러한 이유로 우리는 각자$티$ 매 반복마다 참조점을 업데이트하여 참조점에 가깝게 만듭니다.${엑스}_{케이}$ (알고리즘 II-C의 11행 참조)즉, SVRG 방법에는 외부 루프라는 두 개의 루프가 포함되어 있습니다.$에스$, 참조 기울기가 계산되는 곳 $\nabla 에프({\overline{엑스}}_{에스-1})$(라인 4), 참조점이 고정되고 확률적 경사 단계를 기반으로 내부 반복이 업데이트되는 내부 루프(22) ${엑스}_{케이}$(라인 10).

SAG 및 SAGA와 달리 SVRG에는 다음 사항만 필요합니다. $영형(디)$ 기억의. SVRG의 단점은 다음과 같습니다. 1) 추가 매개변수가 있습니다.$티$즉, 내부 루프의 길이를 조정해야 합니다. 2) 각 반복마다 두 개의 기울기를 계산해야 하며 참조점이 변경될 때마다 전체 기울기를 계산해야 합니다.

Johnson과 Zhang [28]은 SVRG가 반복적 복잡성을 가지고 있음을 보여주었습니다. $영형(({\kappa }_{\text{최대}}+N)\mathrm{봐라g}(1/ϵ))$ , SAG 및 SAGA와 유사합니다.이는 가설 내의 루프 수입니다.$티$ 컬렉션에서 { 1 , … , m } {1, 점, m}{1,…,중} 균일한 샘플링 조건에서 얻은 것입니다.${엘}_{\text{최대}}$，$\mu$, 단계 크기 $\gamma$ 그리고$티$ 이들 사이에는 특정 종속성이 충족되어야 합니다.실제로는$\gamma =영형(1/{엘}_{\text{최대}})$ 내부 루프 길이$티=N$, SVRG는 잘 수행되는 경향이 있으며 이는 그림 1에서 사용한 설정과 정확히 같습니다.

이제 원래 SVRG 방법에는 다양한 변형이 있습니다.예를 들어, 일부 변형에서는 다음을 사용합니다.$티$ 대체 분포 [32], 일부 변형에서는 다음 형식을 허용합니다.$영형(1/{엘}_{\text{최대}})$ 단계 크기 [27], [33], [35].사용하는 변형도 있습니다.$\nabla 에프(\overline{엑스})$ 이러한 전체 그래디언트 평가 비용을 줄이고 미니 배치 크기를 늘려 VR 속성을 보존하기 위한 미니 배치 근사법입니다.[54]에 따라 내부 루프에서 업데이트가 반복되는 일부 변형도 있습니다.$g_{케이}$：
[ g_k = 나블라 f_{i_k}(x_k) - 나블라 f_{i_k}(x_{k-1}) + g_{k-1} 사분면 (25) ]
이는 보다 지역적인 근사치를 제공합니다. 이 지속적인 업데이트 변형(25)을 사용하면 섹션 IV에서 간략하게 논의한 것처럼 볼록하지 않은 함수를 최소화하는 데 고유한 이점이 있습니다.마지막으로 SVRG는 다음을 활용할 수 있습니다.$\nabla 에프({\overline{엑스}}_{에스})$ 알고리즘 종료 시기를 결정하는 데 도움이 되는 값입니다.

알고리즘 3 SVRG 방법

1. 매개변수: 단계 크기 $\gamma >0$
2. 참조점 초기화 ${\overline{엑스}}_0={엑스}_0\in {아르\; 자형}^{디}$
3. 외부 순환을 수행 $에스=1,2,\dots$：
   a. 계산 및 저장$\nabla 에프({\overline{엑스}}_{에스-1})$
   b. 가정하다${엑스}_0={\overline{엑스}}_{에스-1}$
   c. 내부 루프의 반복 횟수를 선택합니다.$티$
   d. 내부 순환을 수행합니다.$케이=0,1,\dots ,티-1$：
   나. 무작위 선택 ik ∈ { 1 , … , n } i_k in { 1, ldots, n }나케이​∈{1,…,N}
   ii. 계산$g_{케이}=\nabla {에프}_{{나}_{케이}}({엑스}_{케이})-\nabla {에프}_{{나}_{케이}}({\overline{엑스}}_{에스-1})+\nabla 에프({\overline{엑스}}_{에스-1})$
   iii. 업데이트${엑스}_{케이+1}={엑스}_{케이}-\gamma g_{케이}$
   e. 참조점 업데이트${\overline{엑스}}_{에스}={엑스}_{티}$

2.4. SDCA 및 그 변형

SAG 및 SVRG 방법의 한 가지 단점은 단계 크기가 일부 문제에서는 알 수 없는 알 수 없는 값에 의존한다는 것입니다. ${엘}_{\text{최대}}$ . SVRG 이전에 SDCA 방법[70]은 최초의 VR 방법 중 하나로 좌표 하강 방법에 대한 연구를 유한합 문제로 확장했습니다. SDCA와 그 변형의 기본 아이디어는 기울기 좌표가 자연스러운 분산 감소 기울기 추정치를 제공한다는 것입니다.구체적으로 가정해보자 j ∈ { 1 , … , d } j { 1, ldots, d }제이∈{1,…,디}, 그리고 정의 ${\nabla }_{제이}에프(엑스):=\left(\frac{\partial 에프(엑스)}{\partial {엑스}_{제이}}\right){이자형}_{제이}$ (f(x))의 번째입니다$제이$ 좌표 방향의 도함수, 여기서${이자형}_{제이}\in {아르\; 자형}^{디}$ 처음이야$제이$ 단위 벡터.좌표 도함수의 주요 속성은 다음과 같습니다.${\nabla }_{제이}에프({엑스}^{\ast })=0$, 왜냐하면 우리는 알고 있기 때문입니다 $\nabla 에프({엑스}^{\ast })=0$ .각 데이터 포인트를 사용한 이것의 파생물$\nabla {에프}_{제이}$ 다르지만 후자는${엑스}^{\ast }$ 0이 아닐 수도 있습니다. 그러므로 우리는:
$$\Vert \nabla 에프(엑스)-{\nabla }_{제이}에프(엑스){\Vert }^2\to 0\text{언제}엑스\to {엑스}^{\ast }(26)$$
이는 좌표 도함수가 분산 감소 특성(12)을 만족함을 의미합니다.추가적으로 우리는 다음을 사용할 수 있습니다.${\nabla }_{제이}에프(엑스)$ 짓다$\nabla 에프(엑스)$ 편견 없는 추정.예를 들어$제이$ 컬렉션에서 나온 거에요 { 1 , … , d } {1, 점, d}{1,…,디} 에서 균일하게 무작위로 선택된 인덱스입니다.그러므로 어떤 경우에도 i ∈ { 1 , … , d } i in { 1, ldots, d }나∈{1,…,디},우리는 $피[제이=나]=\frac{1}{디}$ . 그러므로,$디\times {\nabla }_{제이}에프(엑스)$ 예$\nabla 에프(엑스)$ 편향되지 않은 추정치는 다음과 같습니다.
$$이자형\left[디{\nabla }_{제이}에프(엑스)\right]=디\sum _{나=1}^{디}피[제이=나]\frac{\partial 에프(엑스)}{\partial {엑스}_{나}}{이자형}_{나}=\sum _{나=1}^{디}\frac{\partial 에프(엑스)}{\partial {엑스}_{나}}{이자형}_{나}=\nabla 에프(엑스)$$

그러므로,${\nabla }_{제이}에프(엑스)$ 공변량을 사용할 필요 없이 전체 기울기를 추정하는 VR에 대해 기대할 수 있는 이상적인 속성을 모두 갖추고 있습니다. 이 좌표 기울기 사용의 한 가지 단점은 합계 문제(2)에 대해 계산 비용이 많이 든다는 것입니다.계산 때문이에요.${\nabla }_{제이}에프(엑스)$ 전체 데이터 세트를 탐색해야 하기 때문에${\nabla }_{제이}에프(엑스)=\frac{1}{N}{\sum }_{나=1}^N{\nabla }_{제이}{에프}_{나}(엑스)$ . 따라서 좌표 도함수를 사용하는 것은 합 문제의 구조와 호환되지 않는 것 같습니다. 그러나 원래 문제(2)를 소위 이중 공식으로 다시 작성할 수 있는 경우가 많습니다. 여기서 좌표 도함수는 고유 구조를 활용할 수 있습니다.

예를 들어, L2 정규화 선형 모델(15)의 이중 공식은 다음과 같습니다.
$$V^{\ast }\in \mathrm{아르g}\underset{V\in {아르\; 자형}^N}{\mathrm{최대}}\frac{1}{N}\sum _{나=1}^N-{\ell }_{나}^{\ast }(-V_{나})-\frac{\lambda }{2}{\Vert \frac{1}{\lambda }\sum _{나=1}^N{V}_{나}{ㅏ}_{나}\Vert }^2(27)$$
~에${\ell }_{나}^{\ast }(V)$ 예${\ell }_{나}$ 볼록 접합체.매핑을 사용할 수 있습니다$엑스=\frac{1}{\lambda }{\sum }_{나=1}^N{V}_{나}{ㅏ}_{나}$ 원래 문제를 복원하려면 (15)$엑스$ 변하기 쉬운.해결할 것이다$V^{\ast }$ 위 매핑의 우변에 대입하면 (15)의 해를 얻을 수 있습니다.${엑스}^{\ast }$。

이 이중 문제는 $N$ 실제 변수$V_{나}\in 아르\; 자형$ , 각 훈련 샘플에 대해 하나씩 해당합니다.게다가, 각각의 이중 손실 함수${\ell }_{나}^{\ast }$ 오직$V_{나}$ 함수. 즉, 손실 함수의 첫 번째 항은 배위 분리가 가능합니다. 이러한 좌표 분리성은 두 번째 항의 간단한 형태와 결합되어 좌표 상승 방법을 효율적으로 구현할 수 있게 해줍니다.실제로 Shalev-Shwartz와 Zhang은 이 문제에 대한 좌표 상승이 SAG, SAGA 및 SVRG와 유사한 반복 복잡성을 가지고 있음을 보여주었습니다.$영형(({\kappa }_{\text{최대}}+N)\mathrm{봐라g}(1/ϵ))$。

반복 비용과 알고리즘 구조도 매우 유사합니다. 추적을 통한 합산 ${\sum }_{나=1}^N{V}_{나}{ㅏ}_{나}$ (27)의 두 번째 항을 처리하기 위해 각 이중 좌표 상승 반복은 하나의 훈련 샘플만 고려하면 되며 각 반복의 비용은 다음과 같습니다.$N$ 할 것이 없다.또한 1D 라인 검색을 사용하여 다음과 같이 최대화할 단계 크기를 효율적으로 계산할 수 있습니다.$V_{나}$ 함수의 이중 목적.즉, 없어도${엘}_{\text{최대}}$ 또는 관련 수량에 대한 지식을 통해 VR 방법에 대한 최악의 경우 빠른 실행 시간을 달성하는 것도 가능합니다.

3. 분산 감소의 실질적인 문제

기본적인 분산 감소(VR) 방법을 구현하고 합리적인 성능을 달성하기 위해서는 몇 가지 구현 문제를 해결해야 합니다. 이 섹션에서는 위에서 다루지 않은 몇 가지 문제에 대해 논의합니다.

3.1.SAG/SAGA/SVRG 설정 단계 크기

최적화 알고리즘 분야, 특히 SAG(Stochastic Average Gradient), SAGA(Stochastic Average Gradient Algorithm), SVRG(Stochastic Gradient)와 같은 변동 감소 방법에서는 단계 크기 설정이 중요한 문제입니다.SDCA(확률적 이중 좌표 상승) 방법의 경우 이중 목적을 사용하여 스텝 크기를 결정할 수 있지만 SAG, SAGA 및 SVRG의 원래 가변 방법에 대한 이론적 근거는 스텝 크기가 다음과 같아야 한다는 것입니다.$\gamma =영형\left(\frac{1}{{엘}_{\text{최대}}}\right)$ 형태.그러나 실제 적용에서는 우리가 모르는 경우가 많습니다.${엘}_{\text{최대}}$ 정확한 값을 사용하고 다른 단계 크기를 사용하면 더 나은 성능을 얻을 수 있습니다.

Full Gradient Descent(full-GD) 방법에서 단계 크기를 설정하는 고전적인 전략은 Armijo 라인 검색입니다.주어진 현재 포인트${엑스}_{케이}$ 및 검색 방향$g_{케이}$, 아미조 라인 검색에서 ${\gamma }_{케이}$ 다음과 같이 정의된 라인에서 수행됩니다. {감마 : x_k + 감마 g_k}의 γ k ∈ { γ : xk + γ gk } 감마_kγ케이​∈{γ:엑스케이​+γg케이​}, 그리고 그 기능은 충분히 감소되어야 합니다. 즉:
$$에프({엑스}_{케이}+{\gamma }_{케이}{g}_{케이})<에프({엑스}_{케이})-씨{\gamma }_{케이}\Vert \nabla 에프({엑스}_{케이}){\Vert }^2$$
그러나 이 접근 방식에는 여러 후보 단계가 필요합니다.${\gamma }_{케이}$ 계산$에프({엑스}_{케이}+{\gamma }_{케이}{g}_{케이})$, 평가하는 $에프(엑스)$ 전체 데이터 세트를 탐색하는 데에는 비용이 엄청납니다.

이 문제를 해결하기 위해 Random Variation 방법을 사용하여 다음 조건을 만족하는 것을 찾을 수 있습니다. ${\gamma }_{케이}$：
$${에프}_{좋아요}({엑스}_{케이}+{\gamma }_{케이}{g}_{케이})<{에프}_{좋아요}({엑스}_{케이})-씨{\gamma }_{케이}\Vert \nabla {에프}_{좋아요}({엑스}_{케이}){\Vert }^2$$
이 접근 방식은 일반적으로 실제로 잘 작동합니다. 특히 다음과 같은 경우에 더욱 그렇습니다.$\Vert \nabla {에프}_{좋아요}({엑스}_{케이})\Vert$ 현재 이 접근 방식을 뒷받침하는 이론은 없지만 0에 가깝지는 않습니다.

또한 Mairal은 실제로 스텝 크기를 설정하기 위한 "Bottou 기술"을 제안했습니다. 이 방법은 이 샘플을 단일 통과하여 최적의 단계 크기를 찾기 위해 데이터 세트의 작은 부분(예: 5%)을 가져와 이진 검색을 수행합니다. Armijo 라인 검색과 유사하게 이 방법은 실제로는 잘 수행되는 경우가 많지만 이론적 기반이 부족합니다.

위 내용은 수학 공식과 변수를 표현하기 위해 Markdown 형식을 사용하여 원본 텍스트를 다시 설명한 것입니다.

그러나 SDCA 방법에는 몇 가지 단점도 있습니다.첫째, 볼록 공액을 계산해야 합니다.${\ell }_{나}^{\ast }$ 단순한 그라데이션이 아닌 볼록 공액에 대한 자동 미분 등가물이 없으므로 구현 노력이 증가할 수 있습니다. 최근 연구에서는 접합이 필요하지 않고 대신 그라디언트를 직접 사용하는 "이중 프리" SDCA 방법을 제안했습니다. 그러나 이러한 방법에서는 단계 크기를 설정하기 위해 이중 목표를 추적하는 것이 더 이상 불가능합니다.둘째, SDCA만 필요하지만$영형(N+디)$ (15) 문제를 해결하기 위한 메모리이지만 이 문제 범주의 경우 SAG/SAGA만 필요합니다.$영형(N+디)$ 메모리(섹션 3 참조).SAG/SAGA의 보다 일반적인 문제에 적합한 SDCA의 변형$영형(N디)$ 기억 때문에$V_{나}$ 가지게 되다$디$ 요소의 벡터입니다. SDCA의 마지막 미묘한 단점은 암시적으로 강한 볼록성 상수를 가정한다는 것입니다.$\mu$ 동일한$\lambda$ .~을 위한$\mu$ 그 이상$\lambda$ 문제가 발생하면 원래 VR 방법은 일반적으로 SDCA보다 성능이 훨씬 뛰어납니다.

3.2. 종료 조건의 결정

알고리즘 최적화 분야에서 우리는 알고리즘이 특정 정확도를 달성하는 데 필요한 최악의 반복 횟수를 예측하기 위해 반복 복잡성의 이론적 결과에 의존하는 경우가 많습니다. 그러나 이러한 이론적 한계는 예측할 수 없는 일부 상수에 의존하는 경우가 많으며 실제 응용 프로그램에서는 알고리즘이 더 적은 반복으로 예상되는 정확도를 달성할 수 있는 경우가 많습니다. 따라서 알고리즘을 종료해야 하는 시점을 결정하기 위해 몇 가지 테스트 기준을 설정해야 합니다.

전통적인 Full-GD(Full-GD) 방법에서는 일반적으로 Gradient의 Norm을 사용합니다. $\Vert \nabla 에프({엑스}_{케이})\Vert$ 또는 반복을 중지할 시기를 결정하기 위해 이와 관련된 다른 수량입니다.SVRG 방법의 경우 동일한 기준을 채택할 수 있지만$\Vert \nabla 에프({\overline{엑스}}_{에스})\Vert$ 판단의 근거로 삼습니다.SAG/SAGA 방법의 경우 완전한 기울기를 명시적으로 계산하지는 않지만 $ g_{bar{k}} $의 양은 점차 근사화됩니다.$\nabla 에프({엑스}_{케이})$따라서 다음을 사용하십시오. $\Vert g_{\overline{케이}}\Vert$ 중지 조건으로 사용하는 것은 합리적인 경험적 방법입니다.

SDCA 방법에서는 몇 가지 추가 기록 작업을 통해 점근 비용을 추가하지 않고도 이중 목표의 기울기를 추적할 수 있습니다.추가적으로, 보다 체계적인 접근 방식은 이중 격차를 추적하는 것입니다.$영형(N)$ 비용이 많이 들지만 이중 간격 증명을 통해 종료 조건을 제공할 수 있습니다. 또한 MISO 방법은 강하게 볼록한 대상의 최적 조건을 기반으로 2차 하한을 기반으로 하는 원칙적인 방법을 채택합니다[41].

다음은 Markdown 형식으로 표현된 수학식과 변수입니다.

• 그라데이션 표준:$\Vert \nabla 에프({엑스}_{케이})\Vert$
• SVRG 방법의 기울기 표준:$\Vert \nabla 에프({\overline{엑스}}_{에스})\Vert$
• SAG/SAGA 방법의 근사 기울기 양: $ g_{bar{k}} $
• 반복당 비용 증가:$영형(N)$
• MISO 방식
• 2차 하한

위 내용은 수학 공식과 변수를 표현하기 위해 Markdown 형식을 사용하여 원본 텍스트를 다시 설명한 것입니다.

3.3. 메모리 요구 사항을 줄입니다.

SVRG(Stochastic Variational Reduction of Gradient) 알고리즘은 이전 변동 감소 방법의 메모리 요구 사항을 제거하지만 실제 응용에서는 SAG(Stochastic Average Gradient Descent) 및 SAGA(Stochastic Average Gradient Descent with Gradient Accumulation) 알고리즘이 많은 문제에 사용됩니다. . SVRG 알고리즘보다 반복 횟수가 적은 경향이 있습니다.이것이 생각을 촉발시켰습니다: SAG/SAGA를 허용하는 몇 가지 문제가 있습니까?$영형(N디)$ 메모리 요구 사항은 아래와 같이 구현됩니다. 이 섹션에서는 메모리 요구 사항을 크게 줄일 수 있는 선형 모델 클래스를 살펴봅니다.

각 함수가 다음과 같은 선형 모델을 고려하십시오. ${에프}_{나}(엑스)$ 그것은 다음과 같이 표현될 수 있다:${\xi }_{나}({\mathbf{ㅏ}}_{나}^{\top }엑스)$ .오른쪽$엑스$ 미분은 그라데이션 형식을 제공합니다.
$$\nabla {에프}_{나}(엑스)={\xi }^{\prime }({\mathbf{ㅏ}}_{나}^{\top }엑스){\mathbf{ㅏ}}_{나}$$
여기,${\xi }^{\prime }$ 표현하다$\xi$ 의 파생물.고유벡터에 직접 접근할 수 있다고 가정${\mathbf{ㅏ}}_{나}$, SAG/SAGA 방법을 구현하려면 스칼라만 저장하면 됩니다. $\xi ({\mathbf{ㅏ}}_{나}^{\top }엑스)$ .이런 식으로 메모리 요구 사항은 다음과 같습니다.$영형(N디)$ 로 감소$영형(N)$ . SVRG 알고리즘은 또한 이 그라데이션 구조를 활용할 수 있습니다.$N$ 스칼라를 사용하면 이 문제 클래스에 대해 SVRG "내부" 반복당 필요한 기울기 평가 수를 1로 줄일 수 있습니다.

메모리 요구 사항을 줄일 수 있는 확률적 그래픽 모델과 같은 다른 유형의 문제도 있습니다[66]. 특정 데이터 구조와 알고리즘 최적화를 통해 런타임 시 알고리즘에 필요한 메모리 리소스를 더욱 줄일 수 있습니다.

다음은 Markdown 형식으로 표현된 수학식과 변수입니다.

• 선형 모델 기능:${에프}_{나}(엑스)={\xi }_{나}({\mathbf{ㅏ}}_{나}^{\top }엑스)$
• 그라데이션 표현:$\nabla {에프}_{나}(엑스)={\xi }^{\prime }({\mathbf{ㅏ}}_{나}^{\top }엑스){\mathbf{ㅏ}}_{나}$
• 특징 벡터:${\mathbf{ㅏ}}_{나}$
• 메모리 요구 사항은 다음과 같습니다. $영형(N디)$ 다음으로 감소$영형(N)$。

3.4 희소 기울기 처리

일부 문제에서는 그래디언트 $\nabla {에프}_{나}(엑스)$ 희소 특성이 있는 선형 모델과 같이 많은 수의 0 값을 포함할 수 있습니다.이 경우 전통적인 확률적 경사 하강법(SGD) 알고리즘은 일반적으로 문제 차원보다 훨씬 작은 경사의 0이 아닌 요소 수에 선형적인 계산 복잡성을 사용하여 효율적으로 구현할 수 있습니다.$디$ . 그러나 표준 변형 감소(VR) 방법에서는 이러한 장점이 활용되지 않습니다. 다행히도 이를 개선할 수 있는 두 가지 알려진 방법이 있습니다.

첫 번째 개선 사항은 Schmidt et al.이 제안했는데, 이는 업데이트 프로세스의 단순성을 활용하고 각 반복의 비용이 0이 아닌 개수에 비례하도록 "즉석" 계산의 변형을 구현합니다. 강요.SAG를 예로 들면(그러나 이 접근 방식은 모든 변형에 대해 작동함) 각 반복 후에 전체 벡터를 저장하지 않음으로써 수행됩니다.$V_{좋아요}$, 그러나 0이 아닌 요소에 해당하는 요소만 계산합니다. $V_{나{케이}_{제이}}$, 해당 요소가 0이 아닌 마지막 시간 이후 각 변수를 업데이트하여 $V_{나{케이}_{제이}}$。

두 번째 개선 방법은 공식을 업데이트하는 SAGA를 위해 Leblond et al.에 의해 제안되었습니다. ${엑스}_{케이+1}={엑스}_{케이}-\gamma (\nabla {에프}_{좋아요}({엑스}_{케이})-\nabla {에프}_{좋아요}({\overline{엑스}}_{좋아요})+{\bar{g}}_{케이})$ 추가적인 무작위성이 도입되었습니다. 여기,$\nabla {에프}_{좋아요}({엑스}_{케이})$ 그리고$\nabla {에프}_{좋아요}({\overline{엑스}}_{좋아요})$ 희박하고,${\bar{g}}_{케이}$ 조밀하다.이 방법에서는 조밀한 항$({\bar{g}}_{케이}{)}_{제이}$ 의 각 구성 요소는 다음으로 대체됩니다.${와}_{제이}({\bar{g}}_{케이}{)}_{제이}$,안에 $와\in {아르\; 자형}^{디}$ 지원 세트가 포함된 임의의 희소 벡터입니다.$\nabla {에프}_{좋아요}({엑스}_{케이})$ 이며 모든 요소가 1인 상수 벡터일 것으로 예상됩니다. 이러한 방식으로 업데이트 프로세스는 편향되지 않은 상태로 유지되며(비록 지금은 희소하지만) 증가된 분산은 알고리즘의 수렴 속도에 영향을 미치지 않습니다. 자세한 내용은 Leblond et al.에서 제공됩니다.

다음은 Markdown 형식으로 표현된 수학식과 변수입니다.

• 구배:$\nabla {에프}_{나}(엑스)$
• SGD 업데이트:${엑스}_{케이+1}={엑스}_{케이}-\gamma (\nabla {에프}_{좋아요}({엑스}_{케이})-\nabla {에프}_{좋아요}({\overline{엑스}}_{좋아요})+{\bar{g}}_{케이})$
• 희박한 그라데이션:$\nabla {에프}_{좋아요}({엑스}_{케이})$ 그리고$\nabla {에프}_{좋아요}({\overline{엑스}}_{좋아요})$
• 조밀한 그라데이션:${\bar{g}}_{케이}$
• 무작위 희소 벡터:$와$
• 상수 벡터(모든 요소가 1인 벡터)가 필요합니다.