Tabel gradien dan penaksir SAGA

Pilih iterat awal \(x_0\) dan inisialisasikan satu titik tabel \(\phi_i^0=x_0\) untuk setiap \(i=1,\dots,N\). Simpan, pada iterasi \(k\geq0\), \[\begin{equation} g_i^k=\nabla f_i(\phi_i^k), \qquad \bar g_k=\frac{1}{N}\sum_{i=1}^{N}g_i^k. \end{equation}\] Dengan \(x\in\mathbb{R}^n\), tabel lengkap mempunyai \(N\) kolom gradien di \(\mathbb{R}^n\). Ambil indeks acak \(J_k\sim\operatorname{Unif}\{1,\dots,N\}\) dan bentuk \[\begin{equation} \label{becker03:eq:saga-estimator} v_k =\nabla f_{J_k}(x_k)-g_{J_k}^k+\bar g_k. \end{equation}\] Pembaruan SAGA tanpa suku proksimal adalah \[\begin{equation} \label{becker03:eq:saga-update} x_{k+1}=x_k-t_kv_k. \end{equation}\] Sesudah \(v_k\) dihitung dari tabel lama, hanya kolom terpilih yang disegarkan: \[\begin{equation} \label{becker03:eq:table-update} g_i^{k+1}= \begin{cases} \nabla f_i(x_k),&i=J_k,\\ g_i^k,&i\ne J_k, \end{cases} \qquad \phi_i^{k+1}= \begin{cases} x_k,&i=J_k,\\ \phi_i^k,&i\ne J_k. \end{cases} \end{equation}\] Ini menuliskan secara eksplisit inisialisasi dan urutan pembaruan yang hanya tersirat pada donor. Suku \(-g_{J_k}^k+\bar g_k\) merupakan peubah kontrol (control variate). Donor juga menyebut SAG dan SVRG; keduanya adalah metode reduksi varians lain, tetapi algoritmanya tidak diimpor dari bagian di luar rentang beku.

Mengapa koreksi tabel mengurangi varians

Penghubung mandiri.

Ambil \(\mathcal F_k\) sebagai informasi sebelum \(J_k\) ditarik, sehingga \(x_k\) dan seluruh tabel tetap ketika ekspektasi bersyarat dihitung.

Lebih tepat lagi, tuliskan \(a_i^k=\nabla f_i(x_k)-g_i^k\) dan \(\bar a_k=N^{-1}\sum_i a_i^k\). Maka \[\begin{equation} \label{becker03:eq:variance-identity} \mathbb{E}\!\left[ \left\lVert v_k-\nabla f(x_k)\right\rVert_2^2\mid\mathcal F_k \right] =\frac1N\sum_{i=1}^{N}\left\lVert a_i^k-\bar a_k\right\rVert_2^2 \leq\frac1N\sum_{i=1}^{N}\left\lVert a_i^k\right\rVert_2^2. \end{equation}\] Identitas ini memperlihatkan mekanismenya: ketika gradien tersimpan mendekati gradien komponen pada iterat sekarang, ruas kanan menyusut meskipun langkah \(t_k\) tidak dipaksa menuju nol. Berbeda dari SAG, koreksi SAGA pada penaksir SAGA membuat arah langkah takbias. SVRG mencapai gagasan serupa dengan gradien penuh pada titik acuan berkala, sehingga tidak menyimpan seluruh tabel gradien tetapi memakai evaluasi gradien tambahan.

Laju konvergensi dan iterat rata-rata

Pernyataan donor “untuk \(t\) yang sesuai, metode ini konvergen secara linear” memerlukan hipotesis. Bentuk berikut adalah spesialisasi nonkomposit dari hasil SAGA oleh Defazio, Bach, dan Lacoste-Julien (2014).

Konstanta dan laju pada teorema tersebut mengikuti hasil adaptivitas terhadap kekonveksan kuat dalam Defazio, Bach, dan Lacoste-Julien, SAGA (2014). Teorema donor tanpa hipotesis tidak dipertahankan sebagai klaim universal: tanpa kemulusan dan struktur konveks yang sesuai, laju linear tidak mengikuti hanya dari bentuk pembaruan.

Jika \(f\) hanya konveks, definisikan iterat rata-rata secara tidak ambigu sebagai \[\begin{equation} \label{becker03:eq:average-iterate} \bar x_k=\frac1k\sum_{r=1}^{k}x_r. \end{equation}\] Di bawah asumsi konveks dan \(L\)-mulus di atas, dengan \(t=1/(3L)\), hasil yang sama memberi batas \[\begin{equation} \label{becker03:eq:average-rate} \mathbb{E}[f(\bar x_k)]-f(x^*) \leq\frac{4N}{k} \left[ \frac{2L}{N}\left\lVert x_0-x^*\right\rVert_2^2+f(x_0)-f(x^*) \right]. \end{equation}\] Jadi perataan bukan jaminan tanpa syarat untuk laju yang lebih baik; dalam rezim konveks yang dinyatakan, ia menyediakan jaminan sublinear \(\mathcal O(1/k)\) untuk nilai fungsi.

Latihan dengan petunjuk dan solusi

Latihan berikut merupakan materi baru untuk edisi ini; tidak ada latihan, petunjuk, atau solusi pada rentang donor.

Petunjuk. Gunakan \(v_k-\nabla f(x_k)=a_{J_k}^k-\bar a_k\) dan kembangkan kuadratnya.

Solusi lengkap. Keseragaman indeks memberi \(\mathbb{E}[a_{J_k}^k\mid\mathcal F_k]=\bar a_k\), sehingga selisih tersebut bermean nol. Selanjutnya, \[\begin{multline*} \mathbb{E}\left\lVert a_{J_k}^k-\bar a_k\right\rVert_2^2 =\frac1N\sum_i \left(\left\lVert a_i^k\right\rVert_2^2-2\left\langle a_i^k,\bar a_k\right\rangle +\left\lVert \bar a_k\right\rVert_2^2\right)\\ =\frac1N\sum_i\left\lVert a_i^k\right\rVert_2^2-\left\lVert \bar a_k\right\rVert_2^2, \end{multline*}\] yang sama dengan ruas tengah identitas varians dan tidak melebihi ruas kanannya. Variansnya nol tepat ketika semua \(a_i^k\) sama; khususnya, nol jika \(g_i^k=\nabla f_i(x_k)\) untuk semua \(i\).

Petunjuk. \(g_1^k=-1\), \(g_2^k=2\), dan \(\bar g_k=1/2\).

Solusi lengkap. Pada \(x_k=2\), gradien komponen adalah \(1\) dan \(3\). Oleh karena itu \(v_k=1-(-1)+1/2=5/2\) jika \(J_k=1\), sedangkan \(v_k=3-2+1/2=3/2\) jika \(J_k=2\). Maka \(\mathbb{E}[v_k]=2=\nabla f(2)\) dan \(\operatorname{Var}(v_k)=\tfrac12[(1/2)^2+(-1/2)^2]=1/4\). Penaksir SGD biasa bernilai \(1\) atau \(3\), sehingga mean-nya juga \(2\) tetapi variansnya \(1\). Dengan \(t_k=0{,}1\), SAGA menghasilkan \(x_{k+1}=1{,}75\) atau \(x_{k+1}=1{,}85\).