Teknologian jakaminen

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

Yhteenveto

Stokastinen optimointi on tärkeä osa koneoppimista, ja sen ytimessä on stokastinen gradienttilaskeutumisalgoritmi (SGD), menetelmä, jota on käytetty laajalti siitä lähtien, kun sitä ehdotettiin ensimmäisen kerran yli 60 vuotta sitten. Viimeisten kahdeksan vuoden aikana olemme nähneet jännittävän uuden kehityksen: stokastisten optimointimenetelmien varianssinvähennystekniikoita. Nämä varianssinvähennysmenetelmät (VR-menetelmät) toimivat hyvin skenaarioissa, jotka sallivat harjoitusdatan useita iteraatioita osoittaen nopeampaa konvergenssia kuin SGD, sekä teoriassa että käytännössä. Tämä nopeuden lisääntyminen korostaa kasvavaa kiinnostusta VR-menetelmiä kohtaan ja tällä alueella nopeasti kertyvää tutkimustulosta. Tässä artikkelissa tarkastellaan VR-menetelmien keskeisiä periaatteita ja suuria edistysaskeleita rajoitetun tietojoukon optimointiin. Tavoitteena on antaa tietoa ei-asiantuntijoille. Keskitymme ensisijaisesti konveksiin optimointiympäristöihin ja tarjoamme viitteen lukijoille, jotka ovat kiinnostuneita ei-kupereiden funktioiden minimoimista koskevista laajennuksista.

Avainsanat |. Koneoppiminen;

1. Esittely

Koneoppimisen tutkimuksen alalla peruskysymys ja tärkeä kysymys on mallien sovittaminen suuriin tietokokonaisuuksiin. Voimme esimerkiksi tarkastella tyypillistä lineaarisen pienimmän neliösumman mallin tapausta:

$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^d}{\min }\frac{1}{n}\sum _{i=1}^n(a_i^{T}x-b_i{)}^2$$

Tässä mallissa meillä on $d$ parametrit, jotka esitetään vektoreilla$x\in {\mathbb{R}}^d$ annettu.Sillä välin meillä on käsillä$n$ tietopisteet, mukaan lukien piirrevektorit$a_i\in {\mathbb{R}}^d$ ja tavoitearvo$b_i\in \mathbb{R}$ .Mallin mukauttamisprosessina on säätää näitä parametreja niin, että mallin ennustettu tulos saadaan$a_i^{T}x$ keskimäärin mahdollisimman lähellä tavoitearvoa$b_i$。

Laajemmin voisimme käyttää häviöfunktiota $f_i(x)$ Mallin ennusteiden mittaamiseksi ja$i$ Kuinka lähellä datapisteet ovat:

$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^d}{\min }f(x):=\frac{1}{n}\sum _{i=1}^n{f}_i(x)$$

häviötoiminto $f_i(x)$ Jos se on suurempi, se osoittaa, että mallin ennusteet poikkeavat suuresti tiedoista, jos$f_i(x)$ Nollaa vastaava malli sopii täydellisesti datapisteisiin.toiminto$f(x)$ Heijastaa mallin keskimääräistä menetystä koko tietojoukossa.

Yllä olevat muodon (2) kaltaiset ongelmat eivät koske vain lineaarisia pienimmän neliösumman ongelmia, vaan myös monia muita koneoppimisessa tutkittuja malleja. Esimerkiksi logistisessa regressiomallissa ratkaisemme:

$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^d}{\min }\frac{1}{n}\sum _{i=1}^n\log (1+e^{-b_i{a}_i^{T}x})+\frac{\lambda }{2}\Vert x{\Vert }_2^2$$

Tässä ollaan tekemisissä bi ∈ { − 1 , + 1 } b_i in {-1, +1}bi​∈{−1,+1} Binääriluokitteluongelman ennuste perustuu$a_i^{T}x$ symboleja.Kaavaan lisätään myös regularisointitermi$\frac{\lambda }{2}\Vert x{\Vert }_2^2$ tietojen liiallisen sovittamisen välttämiseksi$\Vert x{\Vert }_2^2$ ilmaista$x$ Euklidisen normin neliö.

Useimmissa ohjatuissa oppimismalleissa harjoitusprosessi voidaan ilmaista muodossa (2), mukaan lukien L1-säännölliset pienimmän neliösumman, tukivektorikoneen (SVM), pääkomponenttianalyysin, ehdolliset satunnaiskentät ja syvät neuroverkot jne.

Keskeinen haaste nykyaikaisissa ongelmatapauksissa on datapisteiden määrä $n$ Todennäköisesti erittäin suuri. Käsittelemme usein tietojoukkoja, jotka ovat paljon teratavualueen ulkopuolella ja voivat olla peräisin niinkin erilaisista lähteistä kuin Internet, satelliitit, etäanturit, rahoitusmarkkinat ja tieteelliset kokeet. Tällaisten suurten tietojoukkojen käsittelyssä yleinen lähestymistapa on käyttää stokastisen gradientin laskeutumisalgoritmia (SGD), joka käyttää vain pientä määrää satunnaisesti valittuja datapisteitä kussakin iteraatiossa. Lisäksi kiinnostus varianssin vähentämisen (VR) stokastisiin gradienttimenetelmiin on viime aikoina lisääntynyt voimakkaasti, sillä niiden konvergenssinopeus on nopeampi kuin perinteisillä stokastisilla gradienttimenetelmillä.

Kuva 1. Sieniaineistoon [7] perustuvassa logistisessa regressio-ongelmassa käytettiin gradienttilaskua (GD), kiihdytettyä gradienttilaskua (AGD, kiihdytetty GD vuonna [50]), stokastista gradienttilaskua (SGD) ja ADAM [30 ] -menetelmää. verrattuna varianssivähennysmenetelmiin (VR) SAG ja SVRG, joissa n = 8124, d = 112.

1.1 Gradientti- ja stokastinen gradienttilaskeutumismenetelmät

Gradient descent (GD) on klassinen algoritmi, jota käytetään ratkaisemaan yllä oleva ongelma (2), ja sen iteratiivinen päivityskaava on seuraava:
$$x_{k+1}=x_k-\gamma \frac{1}{n}\sum _{i=1}^n\nabla f_i(x_k)$$

tässä,$\gamma$ on kiinteä askelarvo, joka on suurempi kuin nolla.Jokaisen GD-algoritmin iteraation aikana jokaisen datapisteen on oltava$i$ Laske gradientti$\nabla f_i(x_k)$, mikä tarkoittaa, että GD vaatii kaiken $n$ suorittaa datapisteiden täydellisen läpikäynnin.Kun tietojoukon koko$n$ Kun siitä tulee erittäin suuri, GD-algoritmin kunkin iteraation kustannukset tulevat erittäin korkeaksi, mikä rajoittaa sen soveltamista.

Vaihtoehtona voidaan harkita stokastisen gradientin laskeutumisen (SGD) menetelmää, jonka ensimmäisenä ehdottivat Robbins ja Monro, ja sen iteratiivinen päivityskaava on seuraava:
$$x_{k+1}=x_k-\gamma \nabla f_{i_k}(x_k)$$

SGD-algoritmi toimii käyttämällä vain yhden satunnaisesti valitun datapisteen gradienttia kussakin iteraatiossa. $\nabla f_{i_k}(x_k)$ pienentääksesi kunkin iteroinnin kustannuksia. Kuvasta 1 näemme, että SGD saavuttaa merkittävämpää edistystä kuin GD (mukaan lukien nopeutetut GD-menetelmät) optimointiprosessin alkuvaiheessa.Kaavio näyttää optimoinnin edistymisen aikakausina, jotka määritellään kaikkien laskennaksi$n$ Harjoitusnäytteiden gradienttien määrä. GD-algoritmi suorittaa yhden iteraation jokaisella kierroksella, kun taas SGD-algoritmi suorittaa yhden iteraation kullakin kierroksella$n$ iteraatioita.Käytämme kierroksia SGD:n ja GD:n vertailun perustana, koska olettaen$n$ Erittäin suurissa tapauksissa molempien menetelmien pääkustannukset keskittyvät gradienttiin$\nabla f_i(x_k)$ laskeminen.

1.2 Varianssiongelma

Tarkastellaan satunnaista indeksointia $i_k$ kokoelmasta { 1 , … , n } {1, ldots, n}{1,…,n} Tasaisen satunnaisvalinnan tapauksessa tämä tarkoittaa sitä kaikille$i$,valita $i_k=i$ Todennäköisyys$P[i_k=i]$ yhtä suuri$\frac{1}{n}$ . tässä tapauksessa,$\nabla f_{i_k}(x_k)$ kuten$\nabla f(x_k)$ Estimaattori on puolueeton, koska odotuksen määritelmän mukaan meillä on:
$$E[\nabla f_{i_k}(x_k)|x_k]=\frac{1}{n}\sum _{i=1}^n\nabla f_i(x_k)=\nabla f(x_k)(6)$$

Vaikka SGD (Stochastic Gradient Descent) -menetelmä ei takaa funktiota jokaisessa iteraatiossa $f$ Tahdon arvo pienenee, mutta keskimäärin se liikkuu kohti negatiivista täyttä gradienttia, joka edustaa suuntaa alaspäin.

Puolueeton gradienttiestimaattori ei kuitenkaan riitä varmistamaan SGD-iteraatioiden konvergenssia. Tämän kohdan havainnollistamiseksi kuva 2 (vasemmalla) näyttää SGD:n iteratiivisen liikeradan käytettäessä logistista regressiofunktiota käyttämällä vakioaskelkokoa LIBSVM:n tarjoamassa neljän kategorian tietojoukossa [7].Kuvan samankeskiset ellipsit edustavat funktion ääriviivoja eli funktion arvoa$f(x)=c$ vastaava kohta$x$ kerätä,$c$ on tietty vakio reaalilukujen joukossa.erilaisia ​​vakioarvoja$c$ Vastaa erilaisia ​​ellipsejä.

SGD:n iteratiivinen liikerata ei konvergoi optimaaliseen ratkaisuun (merkitty vihreällä tähdellä kuvassa), vaan muodostaa pistepilven optimaalisen ratkaisun ympärille. Sitä vastoin kuvassa 2 näytämme varianssivähennysmenetelmän (VR) iteratiivisen liikeradan, stokastisen keskigradientin (SAG), käyttäen samaa vakioaskelkokoa, jonka esittelemme myöhemmin. Syy, miksi SGD ei konvergoi tässä esimerkissä, on se, että itse stokastinen gradientti ei konvergoi nollaan, ja siksi vakioaskel SGD-menetelmä (5) ei koskaan pysähdy.Tämä on jyrkässä ristiriidassa gradienttilaskeutumismenetelmien (GD) kanssa, jotka luonnollisesti pysähtyvät$x_k$ Lähestymistapoja$x^{\ast }$,kaltevuus $\nabla f(x_k)$ yleensä nollaan.

Kuva 2. Tasojoukkokaaviot kaksiulotteiselle logistiselle regressiolle käyttäen kiinteän askeleen SGD (vasemmalla) ja SAG (oikealla) iteratiivisia menetelmiä. Vihreä tähti osoittaa x:nirrottaa.

1.3 Klassinen varianssin vähennysmenetelmä

käsittelyn takia $\nabla f_i(x_k)$ On olemassa useita klassisia tekniikoita arvojen varianssin aiheuttamiin ei-konvergenssiongelmiin.Esimerkiksi Robbins ja Monro [64] käyttävät sarjaa laskevia askeleita${\gamma }_k$ ratkaista varianssiongelma ja varmistaa, että tuote${\gamma }_k\nabla f_{i_k}(x_k)$ voi supistua nollaan. Kuitenkin tämän pienentyvien vaiheiden sarjan säätäminen algoritmin pysäyttämisen estämiseksi liian aikaisin tai liian myöhään on vaikea ongelma.

Toinen klassinen tekniikka varianssin vähentämiseksi on käyttää useita $\nabla f_i(x_k)$ keskiarvo saadaksesi täyden gradientin$\nabla f(x)$ tarkempi arvio. Tätä lähestymistapaa kutsutaan minieräksi, ja se on erityisen hyödyllinen, kun useita gradientteja voidaan arvioida rinnakkain. Tämä johtaa lomakkeen iteraatioon:
$$x_{k+1}=x_k-\gamma \frac{1}{|B_k|}\sum _{i\in B_k}\nabla f_i(x_k)(7)$$
sisään$B_k$ on satunnainen indeksijoukko,$|B_k|$ ilmaista$B_k$ koko.jos$B_k$ Näytteenotto tasaisesti korvaamalla, tämän gradienttiarvion varianssi liittyy "erän kokoon"$|B_k|$ on kääntäen verrannollinen, joten varianssia voidaan pienentää suurentamalla eräkokoa.

Tällaisten iteraatioiden kustannukset ovat kuitenkin verrannollisia eräkokoon, joten tämä varianssin pienentämisen muoto maksaa kohonneet laskentakustannukset.

Toinen yleinen strategia varianssin vähentämiseksi ja SGD:n empiirisen suorituskyvyn parantamiseksi on lisätä "momentum", ylimääräinen termi, joka perustuu aiemmissa vaiheissa käytettyyn suuntaan. Erityisesti SGD:n muoto vauhdilla on seuraava:
$$x_{k+1}=x_k-\gamma m_k(9)$$
missä liikemääräparametri$\beta$ Sijaitsee alueella (0, 1).Jos alkuvauhti$m_0=0$ja laajenna (8) $m_k$ Päivityksiä varten saamme$m_k$ on aiempien gradientien painotettu keskiarvo:
$$m_k=\sum _{t=0}^k{\beta }^{k-t}\nabla f_{i_t}(x_t)(10)$$
siksi,$m_k$ on stokastisten gradienttien painotettu summa.koska${\sum }_{t=0}^k{\beta }^{k-t}=\frac{1-{\beta }^{k+1}}{1-\beta }$, voimme muuntaa $\frac{1-\beta }{1-{\beta }^k}{m}_k$ Pidetään stokastisten gradienttien painotettuna keskiarvona.Jos verrataan tätä täydellisen gradientin lausekkeeseen$\nabla f(x_k)=\frac{1}{n}{\sum }_{i=1}^n\nabla f_i(x_k)$ Vertaillaksemme voimme$\frac{1-\beta }{1-{\beta }^k}{m}_k$(yhtä hyvin kuin $m_k$ ) tulkitaan arvioksi täydellisestä gradientista. Vaikka tämä painotettu summa vähentää varianssia, se herättää myös keskeisiä kysymyksiä.Koska painotettu summa (10) antaa enemmän painoa äskettäin näytteitetyille gradienteille, se ei konvergoi koko gradienttiin$\nabla f(x_k)$ , jälkimmäinen on yksinkertainen keskiarvo. Ensimmäinen varianssin vähennysmenetelmä, jonka näemme luvussa II-A, ratkaisee tämän ongelman käyttämällä yksinkertaista keskiarvoa minkä tahansa painotetun keskiarvon sijaan.

1.4 Nykyaikaiset varianssin vähentämismenetelmät

Toisin kuin klassiset menetelmät, ne käyttävät suoraan yhtä tai useampaa $\nabla f_i(x_k)$ kuten$\nabla f(x_k)$ Approksimaationa nykyaikaiset varianssin vähentämismenetelmät (VR) käyttävät erilaista strategiaa.Nämä menetelmät käyttävät$\nabla f_i(x_k)$ päivittääksesi gradienttiarvion$g_k$, jonka tavoitteena on tehdä $g_k$ lähestyä$\nabla f(x_k)$ .Erityisesti toivomme$g_k$ pystyvät tyydyttämään$g_k\approx \nabla f(x_k)$ . Tällaisten gradienttiarvioiden perusteella suoritamme sitten likimääräisen gradienttivaiheen muodossa:
$$x_{k+1}=x_k-\gamma g_k(11)$$
tässä$\gamma >0$ on askelkoon parametri.

Varmistaaksesi, että käytetään tasaista askelkokoa $\gamma$ Kun iteraatio (11) voi konvergoida, meidän on varmistettava, että gradienttiestimaatti$g_k$ Varianssi on yleensä nolla. Matemaattisesti tämä voidaan ilmaista seuraavasti:
$$E\left[\Vert g_k-\nabla f(x_k){\Vert }^2\right]\to 0\text{kuten}k\to \infty (12)$$
odotuksia täällä$E$ perustuu algoritmiin asti$k$ Kaikki satunnaismuuttujat lasketaan iteraatioita varten. Ominaisuus (12) varmistaa, että VR-menetelmä voidaan pysäyttää, kun optimaalinen ratkaisu on saavutettu. Pidämme tätä ominaisuutta VR-lähestymistavan tunnusomaisena piirteenä ja kutsumme sitä siksi VR-omaisuudeksi. On syytä huomata, että ilmaisu "alennettu" varianssi voi olla harhaanjohtava, koska itse asiassa varianssilla on taipumus olla nolla. Ominaisuus (12) on avaintekijä, joka mahdollistaa VR-menetelmien nopeamman konvergenssin teoriassa (oikein oletuksin) ja käytännössä (kuten kuvassa 1).

1.5 Ensimmäinen esimerkki varianssin vähennysmenetelmästä: SGD²

Yksinkertainen parannusmenetelmä voi saada SGD-rekursiivisen kaavan (5) saavuttamaan konvergenssin pienentämättä askelkokoa, toisin sanoen kääntää jokainen gradientti. Erityinen menetelmä on vähentää $\nabla f_i(x^{\ast })$, tämä menetelmä määritellään seuraavasti:
$$x_{k+1}=x_k-\gamma (\nabla f_{i_k}(x_k)-\nabla f_{i_k}(x^{\ast }))(13)$$
Tätä menetelmää kutsutaan nimellä SGD² [22].Vaikka emme yleensä voi tietää varmasti jokaista$\nabla f_i(x^{\ast })$ , mutta esimerkkinä SGD² voi hyvin havainnollistaa varianssin vähennysmenetelmän perusominaisuuksia.Lisäksi monia varianssin vähentämismenetelmiä voidaan pitää SGD²-menetelmän likimääräisinä muotoina, nämä menetelmät eivät perustu tunnettuihin;$\nabla f_i(x^{\ast })$, mutta käytä sen sijaan menetelmää, joka voi arvioida $\nabla f_i(x^{\ast })$ arvioitu arvo.

On syytä huomata, että SGD² käyttää puolueetonta arviota täydellisestä gradientista.koska$\nabla f(x^{\ast })=0$,F:
$$E[\nabla f_{i_k}(x_k)-\nabla f_{i_k}(x^{\ast })]=\nabla f(x_k)-\nabla f(x^{\ast })=\nabla f(x_k)$$
Lisäksi kun SGD² saavuttaa optimaalisen ratkaisun, se pysähtyy luonnollisesti, koska tahansa$i$,omistaa:
$$(\nabla f_i(x)-\nabla f_i(x^{\ast })){|}_{x=x^{\ast }}=0$$

Lisähavainnon jälkeen, kanssa $x_k$ lähellä$x^{\ast }$(peräkkäin $\nabla f_i$), SGD² täyttää varianssin vähennysominaisuuden (12), koska:
$$\begin{gathered} E\left[\Vert g_k-\nabla f(x_k){\Vert }^2\right]= \\ E\left[\Vert \nabla f_{i_k}(x_k)-\nabla f_{i_k}(x^{\ast })-\nabla f(x_k){\Vert }^2\right]\le E\left[\Vert \nabla f_{i_k}(x_k)-\nabla f_{i_k}(x^{\ast }){\Vert }^2\right] \end{gathered}$$
Tässä käytämme Lemma 2:ta, anna$X=\nabla f_{i_k}(x_k)-\nabla f_{i_k}(x^{\ast })$, ja käytti hyväkseen $E[\nabla f_{i_k}(x_k)-\nabla f_{i_k}(x^{\ast })]=\nabla f(x_k)$ luonto. Tämä ominaisuus osoittaa, että SGD²:llä on nopeampi konvergenssinopeus kuin perinteisillä SGD-menetelmillä, joita olemme selostaneet liitteessä B.

1.6 Varianssin nopean konvergenssin vähentämismenetelmä

Tässä osiossa esittelemme kaksi vakiooletusta, joita käytetään varianssivähennysmenetelmän (VR) analysointiin, ja käsittelemme kiihtyvyysvaikutusta, joka voidaan saavuttaa näillä olettamuksilla verrattuna perinteiseen SGD-menetelmään. Ensin oletetaan, että gradientilla on Lipschitzin jatkuvuus, mikä tarkoittaa, että gradientin muutosnopeus on äärellinen.

Oletus 1 (Lipschitzin jatkuvuus)

Oletetaan, että funktio $f$on erotettavissa ja on $L$- sileä, kaikille $x$ ja$y$ ja joku$0<L<\infty$,Seuraavat ehdot:
$$\Vert \nabla f(x)-\nabla f(y)\Vert \le L\Vert x-y\Vert (14)$$
Tämä tarkoittaa, että jokainen$fi:{\mathbb{R}}^d\to \mathbb{R}$ on erilaista,$L_i$- sileä, määrittelemme $L_{\text{max}}$ varten max ⁡ { L 1 , . . . , L n } max{L_1, . . . , L_n}max{L1​,...,Ln​}。

Vaikka tätä pidetään yleisesti heikona oletuksena, käsittelemme seuraavissa luvuissa VR-menetelmiä, jotka soveltuvat epäsujuisiin ongelmiin. Kaksinkertaisesti differentioituvassa yksimuuttujafunktiossa,$L$-Sileys voidaan intuitiivisesti ymmärtää seuraavasti: se vastaa oletusta, että toinen derivaatta on $L$ yläraja, eli$|f^{\prime \prime }(x)|\le L$ kaikille$x\in {\mathbb{R}}^d$ .Useiden muuttujien kahdesti differentioituville funktioille se vastaa Hessenin matriisin oletusta${\nabla }^{2}f(x)$ Yksittäinen arvo$L$ yläraja.

Oletus 2 (voimakas kupera)

Toinen harkitsemamme hypoteesi on, että funktio (f) on $\mu$- Voimakkaasti kupera, mikä tarkoittaa, että tietyllä tavalla $\mu >0$,toiminto $x\mapsto f(x)-\frac{\mu }{2}\Vert x{\Vert }^2$ Se on kupera.Lisäksi jokaiselle$i=1,...,n$，$fi:{\mathbb{R}}^d\to \mathbb{R}$ Se on kupera.

Tämä on vahva oletus.Pienimmän neliösumman tehtävässä jokainen (fi$ on konveksi, mutta kokonaisfunktio (f) on vain suunnittelumatriisissa$A:=[a_1,...,a_n]$ Se on voimakkaasti kupera vain, jos sillä on täydellinen riviarvo. L2-reguloitu logistinen regressio-ongelma täyttää tämän oletuksen, koska on olemassa regularisointitermi, jossa$\mu \ge \lambda$。

Tärkeä ongelmaluokka, joka täyttää nämä oletukset, ovat optimointiongelmat muodossa:
$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^d}{\min }f(x)=\frac{1}{n}\sum _{i=1}^n{\ell }_i(a_i^{T}x)+\frac{\lambda }{2}\Vert x{\Vert }^2(15)$$
jossa jokainen "tappio" toimii${\ell }_i:\mathbb{R}\to \mathbb{R}$ on kahdesti differentioituva ja sen toinen derivaatta${\ell }_i^{\prime \prime }$ on rajoitettu nollaan ja johonkin ylärajaan$M$ välillä. Tämä sisältää erilaisia ​​​​häviöfunktioita, joissa on L2-regulaatio koneoppimisessa, kuten pienimmän neliösumman, logistisen regression, probit-regression, Huberin robustin regression jne.Tässä tapauksessa kaikille$i$,Meillä on $L_i\le M\Vert a_i{\Vert }^2+\lambda$ ja$\mu \ge \lambda$。

Näillä oletuksilla gradienttilaskeutumismenetelmän (GD) konvergenssinopeus määräytyy ehtonumeron mukaan $\kappa :=L/\mu$ Päättää. Ehtoluku on aina suurempi tai yhtä suuri kuin 1, ja kun se on merkittävästi suurempi kuin 1, funktion ääriviivat muuttuvat hyvin elliptisiksi, jolloin GD-menetelmän iteraatiot värähtelevät.Päinvastoin, milloin$\kappa$ Kun se on lähellä yhtä, GD-menetelmä konvergoi nopeammin.

Oletuksissa 1 ja 2 VR-menetelmä konvergoi lineaarisella nopeudella.Sanomme, että satunnaismenetelmän ({f(x_k)}) funktion arvo on annettu$0<\rho \le 1$ Lineaarisen konvergenssin nopeus (odotuksen alapuolella), jos vakio on olemassa$C>0$ Valmistaa:
$$E[f(x_k)]-f(x^{\ast })\le (1-\rho {)}^{k}C=O(\exp (-k\rho ))\forall k(16)$$
Tämä eroaa klassisista SGD-menetelmistä, jotka luottavat vain gradientin puolueettomiin arvioihin kussakin iteraatiossa, jotka saavat vain alilineaariset nopeudet seuraavilla olettamuksilla:
$$E[f(x_k)]-f(x^{\ast })\le O(1/k)$$
Minimi, joka tyydyttää tämän epätasa-arvon$k$ Sitä kutsutaan algoritmin iteratiiviseksi monimutkaiseksi. Seuraavat ovat GD-, SGD- ja VR-menetelmien perusversioille yhden iteroinnin iteratiivisuus ja hinta:

Algoritmin kokonaisajoaika määräytyy iteroinnin monimutkaisuuden ja iteroinnin suoritusajan tulon perusteella.käytetty täällä${\kappa }_{\text{max}}:={\max }_i{L}_i/\mu$ .Ilmoitus${\kappa }_{\text{max}}\ge \kappa$Siksi GD:n iteroinnin monimutkaisuus on pienempi kuin VR-menetelmän.

Kuitenkin, koska GD:n iteraatiokohtainen hinta on VR-menetelmän hinta $n$ kertaa, VR-menetelmä on ylivoimainen kokonaiskäyttöajan suhteen.

Klassisten SGD-menetelmien etuna on, että niiden ajoaika ja konvergenssinopeus eivät riipu $n$, mutta siinä on toleranssi $ϵ$ Riippuvuus on paljon huonompi, mikä selittää SGD:n huonon suorituskyvyn, kun toleranssi on pieni.

Liitteessä B tarjoamme yksinkertaisen todisteen siitä, että SGD²-menetelmällä on sama iteratiivinen monimutkaisuus kuin VR-menetelmällä.

2. Perusvarianssin vähennysmenetelmä

Varianssivähennysmenetelmien (VR) kehittäminen on käynyt läpi useita vaiheita, ja ensimmäinen menetelmäerä johti merkittävästi parantuneisiin konvergenssinopeuksiin. Tämän menetelmäsarjan alku on SAG-algoritmi. Myöhemmin stokastinen kaksoiskoordinaattinen nousu (SDCA) -algoritmi, MISO-algoritmi, stokastinen varianssia vähentävä gradientti (SVRG/S2GD) ja SAGA-algoritmi (eli "parannettu" SAG) ilmestyivät peräkkäin.

Tässä luvussa kerromme yksityiskohtaisesti näistä uraauurtavista VR-menetelmistä. Luvussa 4 tutkimme joitain uudempia menetelmiä, jotka osoittavat ylivoimaisia ​​ominaisuuksia verrattuna näihin perusmenetelmiin tietyissä sovellusskenaarioissa.

2.1 Stokastinen keskimääräinen gradienttimenetelmä (SAG)

Ensimmäisen varianssivähennysmenetelmän (VR) tutkiminen alkaa täyden gradienttirakenteen jäljittelemällä.Täydestä gradientista lähtien$\nabla f(x)$ on kaikki$\nabla f_i(x)$ Yksinkertainen gradienttien keskiarvo, sitten arviomme täydestä gradientista$g_k$ Sen pitäisi olla myös näiden gradienttiestimaattien keskiarvo. Tästä ideasta syntyi ensimmäinen VR-menetelmämme: stokastinen keskimääräinen gradientti (SAG).

SAG-menetelmä [37], [65] on satunnaistettu versio varhaisen inkrementaalisen aggregoidun gradientin (IAG) menetelmästä [4]. SAG:n ydinajatus on, että jokaiselle datapisteelle$i$ ylläpitää arviota$v_{ik}\approx \nabla f_i(x_k)$ .Käytä sitten näitä$v_{ik}$ Arvojen keskiarvoa käytetään arviona täydellisestä gradientista, eli:
$${\bar{g}}_k=\frac{1}{n}\sum _{j=1}^n{v}_{jk}\approx \frac{1}{n}\sum _{j=1}^n\nabla f_j(x_k)=\nabla f(x_k)(18)$$

Jokaisessa SAG:n iteraatiossa joukosta { 1 , … , n } {1, ldots, n}{1,…,n} Poimi hakemisto kohteesta$i_k$ja päivitetään sitten seuraavien sääntöjen mukaisesti $v_{jk}$：
$$v_{jk}^{k+1}=\{\begin{array}{ll}\nabla f_{i_k}(x_k),& \text{jos}j=i_k\\ v_{jk}^k,& \text{jos}j\ne i_k\end{array}(19)$$
Heidän joukossaan jokainen$v_{0i}$ Voidaan alustaa nollaan tai$\nabla f_i(x_0)$ likimääräinen arvo.Ratkaisun kanssa$x^{\ast }$ likiarvo, jokainen$v_{ik}$ vähitellen lähentyy$\nabla f_i(x^{\ast })$täten tyydyttää VR-ominaisuuden (12).

Jotta SAG voidaan toteuttaa tehokkaasti, meidän on kiinnitettävä huomiota laskemiseen ${\bar{g}}_k$ välttääksesi summan aloittamisen alusta joka kerta$n$ vektori, koska tämä on$n$ Kustannukset ovat korkeat, kun se on suuri.Onneksi, koska jokaisessa iteraatiossa on vain yksi$v_{ik}$ Ehdot muuttuvat, eikä meidän tarvitse joka kerta laskea koko summaa uudelleen.Tarkemmin sanottuna oletetaan, että iteroitaessa$k$ Indeksi poimittu kohteesta$i_k$, sitten on:
$${\bar{g}}_k=\frac{1}{n}\sum _{\begin{array}{c}j=1\\ j\ne i_k\end{array}}^n{v}_{jk}+\frac{1}{n}{v}_{i_k}^k={\bar{g}}_{k-1}-\frac{1}{n}{v}_{i_k}^{k-1}+\frac{1}{n}{v}_{i_k}^k(20)$$

Koska lisäksi $v_{i_k}$ kaikki paitsi$v_{jk}$ Arvot pysyvät samoina, vain tallennamme jokaisen$j$ Vektori, joka vastaa$v_j$ . Algoritmi 1 näyttää SAG-menetelmän erityisen toteutuksen.

SAG on ensimmäinen stokastinen menetelmä lineaarisen konvergenssin saavuttamiseksi, ja sen iteroinnin monimutkaisuus on $O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$, käyttämällä askelkokoa $\gamma =O(1/L_{\text{max}})$ . Tämä lineaarinen konvergenssi voidaan havaita kuvassa 1.On syytä huomata, että johtuen$L_{\text{max}}$-Smooth toiminto mille tahansa $L^{\prime }\ge L_{\text{max}}$ Liian$L^{\prime }$- Sileillä SAG-menetelmillä saavutetaan lineaariset konvergenssinopeudet riittävän pienille askelkokoille, toisin kuin klassisilla SGD-menetelmillä, joilla saavutetaan vain alilineaarisia nopeuksia pienenevien askelkokojen sekvensseillä, joita on vaikea säätää käytännössä.

Tuohon aikaan SAG:n lineaarinen konvergenssi oli merkittävä edistysaskel, koska se laski vain yhden stokastisen gradientin (käsitteli yhtä datapistettä) kussakin iteraatiossa. Schmidtin et al. [65] tarjoama konvergenssitodiste on kuitenkin erittäin monimutkainen ja perustuu tietokoneella varmennettuihin vaiheisiin. Tärkein syy siihen, miksi SAG:ta on vaikea analysoida, on se$g_k$ on gradientin puolueellinen arvio.

Seuraavaksi esittelemme SAGA-menetelmän, SAG:n muunnelman, joka hyödyntää kovariaattien käsitettä luodakseen SAG-menetelmästä puolueettoman muunnelman, jolla on samanlainen suorituskyky, mutta jota on helpompi analysoida.

---

Algoritmi 1: SAG-menetelmä

1. Parametrit: askelkoko $\gamma >0$
2. alustus:$x_0$，$v_i=0\in {\mathbb{R}}^d$ varten$i=1,\dots ,n$
3. oikein $k=1,\dots ,T-1$ toteuttaa:
   a. Satunnainen valinta ik ∈ { 1 , … , n } i_k in {1, ldots, n}ik​∈{1,…,n}
   b. Laske${\bar{g}}_k={\bar{g}}_{k-1}-\frac{1}{n}{v}_{i_k}^{k-1}$
   c. Päivitys$v_{i_k}^k=\nabla f_{i_k}(x_k)$
   d. Päivitä gradienttiarvio${\bar{g}}_k={\bar{g}}_k+\frac{1}{n}{v}_{i_k}^k$
   e. Päivitys$x_{k+1}=x_k-\gamma {\bar{g}}_k$
4. Lähtö:$x_T$

2.2.SAGA-menetelmä

Alennettu puolueeton perusgradienttiarvio $\nabla f_{i_k}(x_k)$ Varianssilähestymistapa perustuu niin kutsuttujen kovariaattien eli kontrollimuuttujien käyttöön.varten$i=1,\dots ,n$,perustaa $v_i\in {\mathbb{R}}^d$ on vektori.Näitä vektoreita käyttämällä voimme muuntaa täyden gradientin$\nabla f(x)$ Kirjoitettu uudelleen muotoon:
$$\nabla f(x)=\frac{1}{n}\sum _{i=1}^n(\nabla f_i(x)-v_i+v_i)=\frac{1}{n}\sum _{i=1}^n\nabla f_i(x)-v_i+\frac{1}{n}\sum _{j=1}^n{v}_j$$
$$:=\frac{1}{n}\sum _{i=1}^n\nabla f_i(x,v)(21)$$
joka määrittelee$\nabla f_i(x,v):=\nabla f_i(x)-v_i+\frac{1}{n}{\sum }_{j=1}^n{v}_j$ .Nyt voimme ottaa satunnaisesti näytteen a$\nabla f_i(x,v)$ rakentaaksesi täydellisen gradientin$\nabla f(x)$ Puolueeton arvio i ∈ { 1 , … , n } i in {1, ldots, n}i∈{1,…,n}, voit käyttää SGD-menetelmää ja gradienttiestimointia:
$$g_k=\nabla f_{i_k}(x_k,v)=\nabla f_{i_k}(x_k)-v_{i_k}+\frac{1}{n}\sum _{j=1}^n{v}_j(22)$$

tarkkailua varten $v_i$ Valintaparien ero$g_k$ voimme vaikuttaa$g_k=\nabla f_{i_k}(x_k,v)$ Korvaa ja käytä$E_i\sim \frac{1}{n}[v_i]=\frac{1}{n}{\sum }_{j=1}^n{v}_j$ Odotuksen laskemiseksi saamme:
$$E\left[\Vert \nabla f_i(x_k)-v_i+E_i\sim \frac{1}{n}[v_i-\nabla f_i(x_k)]{\Vert }^2\right]\le E\left[\Vert \nabla f_i(x_k)-v_i{\Vert }^2\right](23)$$
Lemma 2:ta käytetään tässä, missä$X=\nabla f_i(x_k)-v_i$ .Tämä raja (23) osoittaa, että jos$v_i$ kera$k$ Kasvu on lähellä$\nabla f_i(x_k)$ , voimme saada VR-attribuutteja (12).Siksi soitamme$v_i$ ovat kovariaatteja, ja voimme valita ne varianssin vähentämiseksi.

Esimerkiksi tämä lähestymistapa on toteutettu myös SGD²-menetelmällä (13), jossa $v_i=\nabla f_i(x^{\ast })$ .Tätä ei kuitenkaan yleisesti käytetä käytännössä, koska emme yleensä tiedä$\nabla f_i(x^{\ast })$ .Käytännöllisempi vaihtoehto on$v_i$ kuten tiedämme${\bar{x}}_i\in {\mathbb{R}}^d$ lähellä olevaa gradienttia$\nabla f_i({\bar{x}}_i)$ . SAGA jokaiselle toiminnolle$f_i$ käytä referenssipistettä${\bar{x}}_i\in {\mathbb{R}}^d$, ja käytä kovariaatteja $v_i=\nabla f_i({\bar{x}}_i)$, joista jokainen ${\bar{x}}_i$ on viimeinen arviomme$f_i$ kohta. Käyttämällä näitä kovariaatteja voimme rakentaa gradienttiestimaatin, seuraavan (22), jolloin saadaan:
$$g_k=\nabla f_{i_k}(x_k)-\nabla f_{i_k}({\bar{x}}_{i_k})+\frac{1}{n}\sum _{j=1}^n\nabla f_j({\bar{x}}_j)(24)$$

SAGAn toteuttamiseksi voimme tallentaa gradientteja $\nabla f_i({\bar{x}}_i)$ sijasta$n$ viitekohta${\bar{x}}_i$ .Eli oletetaan$v_j=\nabla f_j({\bar{x}}_j)$ varten j ∈ { 1 , … , n } j in {1, ldots, n}j∈{1,…,n}, jokaisessa iteraatiossa päivitämme stokastisen gradientin, kuten SAG $v_j$。

Algoritmi 2 SAGA

1. Parametrit: askelkoko $\gamma >0$
2. alustus:$x_0$，$v_i=0\in {\mathbb{R}}^d$ varten$i=1,\dots ,n$
3. käyttäytyminen $k=1,\dots ,T-1$ iteraatiot:
   a. Satunnainen valinta ik ∈ { 1 , … , n } i_k in {1, ldots, n}ik​∈{1,…,n}
   b. Tallenna vanha arvo$v_{\text{vanha}}=v_{i_k}$
   c. Päivitys$v_{i_k}=\nabla f_{i_k}(x_k)$
   d. Päivitys$x_{k+1}=x_k-\gamma (v_{i_k}-v_{\text{vanha}}+{\bar{g}}_k)$
   e. Päivitä gradienttiarvio${\bar{g}}_k={\bar{g}}_{k-1}+\frac{1}{n}(v_{i_k}-v_{\text{vanha}})$
4. Lähtö:$x_T$

SAGA-menetelmällä on sama iteroinnin monimutkaisuus kuin SAG:lla $O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$, käyttämällä askelkokoa $\gamma =O(1/L_{\text{max}})$ , mutta todiste on paljon yksinkertaisempi.Kuitenkin, kuten SAG, SAGA-menetelmä vaatii tallennusta$n$ apuvektorit$v_i\in {\mathbb{R}}^d$ varten$i=1,\dots ,n$, mikä tarkoittaa tarvetta $O(nd)$ säilytystilasta.kun$d$ ja$n$ Kun molemmat ovat suuria, tämä ei ehkä ole mahdollista. Seuraavassa osiossa kerromme yksityiskohtaisesti, kuinka tätä muistivaatimusta voidaan vähentää yleisissä malleissa, kuten regularisoiduissa lineaarisissa malleissa.

kun pystyy $n$ Kun kaksi apuvektoria on tallennettu muistiin, SAG ja SAGA yleensä käyttäytyvät samalla tavalla. Jos tämä muistitarve on liian korkea, SVRG-menetelmä, jota tarkastelemme seuraavassa osiossa, on hyvä vaihtoehto. SVRG-menetelmä saavuttaa saman konvergenssinopeuden ja on usein käytännössä yhtä nopea, mutta vaatii vain$O(d)$ muistia yleisiin ongelmiin.

2.3.SVRG-menetelmä

Ennen SAGA-menetelmän syntyä jotkin varhaiset työt esittelivät ensimmäistä kertaa kovariaatteja SAG-menetelmän vaatiman korkean muistin ongelman ratkaisemiseksi.Nämä tutkimukset perustuvat kiinteään vertailupisteeseen$\bar{x}\in {\mathbb{R}}^d$ kovariaatit, olemme laskeneet koko gradientin siinä vaiheessa$\nabla f(\bar{x})$ .tallentamalla vertailupisteitä$\bar{x}$ ja vastaava täydellinen gradientti$\nabla f(\bar{x})$, voimme tehdä tämän tallentamatta jokaista $\nabla f_j(\bar{x})$ Siinä tapauksessa käytä${\bar{x}}_j=\bar{x}$ kaikille$j$ päivityksen toteuttamiseksi(24).Tarkemmin sanottuna näiden vektorien tallentamisen sijaan hyödynnämme tallennettuja referenssipisteitä kussakin iteraatiossa$\bar{x}$ laskea$\nabla f_{i_k}(\bar{x})$ . Tätä menetelmää ehdottivat alun perin eri kirjoittajat eri nimillä, mutta se yhdistettiin myöhemmin SVRG-menetelmäksi noudattaen nimikkeistöä [28] ja [84].

Formalisoimme SVRG-menetelmän algoritmissa 3.

Käyttämällä (23) voimme johtaa gradienttiestimaatin $g_k$ Varianssi on rajoitettu:
$$E\left[\Vert g_k-\nabla f(x_k){\Vert }^2\right]\le E\left[\Vert \nabla f_i(x_k)-\nabla f_i(\bar{x}){\Vert }^2\right]\le L_{\text{max}}^2\Vert x_k-\bar{x}{\Vert }^2$$
jossa toinen epäyhtälö käyttää kutakin$f_i$ /$L_i$- Tasaisuus.

On syytä huomata, että vertailukohta $\bar{x}$ Mitä lähempänä nykyistä pistettä$x_k$, sitä pienempi on gradienttiestimaatin varianssi.

Jotta SVRG-menetelmä olisi tehokas, meidän on päivitettävä viitepisteet usein $\bar{x}$ (jotka edellyttävät täyden gradientin laskemista) punnitaan pienentyneen varianssin hyötyyn nähden.Tästä syystä me jokainen$t$ Päivitä vertailupiste kerran joka iteraatiossa, jotta se on lähellä$x_k$ (Katso algoritmin II-C rivi 11).Eli SVRG-menetelmä sisältää kaksi silmukkaa: ulomman silmukan$s$, jossa vertailugradientti lasketaan $\nabla f({\bar{x}}_{s-1})$(rivi 4) ja sisäsilmukka, jossa vertailupiste on kiinteä ja sisäinen iteraatio päivitetään stokastisen gradienttiaskeleen (22) perusteella. $x_k$(Rivi 10).

Toisin kuin SAG ja SAGA, SVRG vaatii vain $O(d)$ muistista. SVRG:n haittoja ovat: 1) Meillä on ylimääräinen parametri$t$, eli sisäisen silmukan pituutta, on säädettävä 2) Jokaiselle iteraatiolle on laskettava kaksi gradienttia, ja koko gradientti on laskettava aina, kun vertailupistettä muutetaan.

Johnson ja Zhang [28] osoittivat, että SVRG:llä on iteratiivinen monimutkaisuus $O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$ , samanlainen kuin SAG ja SAGA.Tämä on hypoteesin sisällä olevien silmukoiden lukumäärä$t$ kokoelmasta { 1 , … , m } {1, ldots, m}{1,…,m} Saatu yhtenäisen näytteenoton ehdolla, missä$L_{\text{max}}$，$\mu$, askelkoko $\gamma$ ja$t$ Tietyt riippuvuudet niiden välillä on täytettävä.Käytännössä käyttämällä$\gamma =O(1/L_{\text{max}})$ ja sisälenkin pituus$t=n$, SVRG toimii yleensä hyvin, mikä on täsmälleen sama asetus, jota käytimme kuvassa 1.

Nyt alkuperäisestä SVRG-menetelmästä on monia muunnelmia.Esimerkiksi joitain muunnelmia käytetään$t$ vaihtoehtoinen jakelu [32], jotkin muunnelmat sallivat muodon$O(1/L_{\text{max}})$ Askelkoko [27], [33], [35].Käytössä on myös joitain muunnelmia$\nabla f(\bar{x})$ mini-erän likiarvo pienentää näiden täydellisten gradienttiarviointien kustannuksia ja suurentaa minierän kokoa VR-ominaisuuksien säilyttämiseksi.On myös joitakin muunnelmia, joissa päivitykset toistetaan sisäisessä silmukassa [54]:n mukaisesti.$g_k$：
[ g_k = nabla f_{i_k}(x_k) - nabla f_{i_k}(x_{k-1}) + g_{k-1} quad (25) ]
Tämä tarjoaa paikallisemman likiarvon. Tämän jatkuvan päivityksen muunnelman (25) käyttäminen tarjoaa ainutlaatuisia etuja ei-kupereiden funktioiden minimoinnissa, kuten käsittelemme lyhyesti osiossa IV.Lopuksi huomaa, että SVRG voi hyödyntää$\nabla f({\bar{x}}_s)$ arvo auttaa päättämään, milloin algoritmi lopetetaan.

Algoritmin 3 SVRG-menetelmä

1. Parametrit: askelkoko $\gamma >0$
2. Alusta viitepiste ${\bar{x}}_0=x_0\in {\mathbb{R}}^d$
3. Suorita ulkoinen kierto $s=1,2,\dots$：
   a. Laske ja tallenna$\nabla f({\bar{x}}_{s-1})$
   b. Oletetaan$x_0={\bar{x}}_{s-1}$
   c. Valitse sisemmän silmukan iteraatioiden määrä$t$
   d. Suorita sisäinen kierto$k=0,1,\dots ,t-1$：
   i. Satunnainen valinta ik ∈ { 1 , … , n } i_k in {1, ldots, n}ik​∈{1,…,n}
   ii$g_k=\nabla f_{i_k}(x_k)-\nabla f_{i_k}({\bar{x}}_{s-1})+\nabla f({\bar{x}}_{s-1})$
   iii$x_{k+1}=x_k-\gamma g_k$
   e. Päivitä vertailupiste${\bar{x}}_s=x_t$

2.4 SDCA ja sen muunnelmat

Yksi SAG- ja SVRG-menetelmien puute on, että niiden askelkoko perustuu tuntemattomiin arvoihin, jotka voivat olla tuntemattomia joissakin ongelmissa. $L_{\text{max}}$ . Ennen SVRG:tä SDCA-menetelmä [70] yhtenä varhaisimmista VR-menetelmistä laajensi koordinaattilaskeutumismenetelmien tutkimuksen äärellisiin summaongelmiin. SDCA:n ja sen muunnelmien ideana on, että gradientin koordinaatit tarjoavat luonnollisen varianssia vähentävän gradienttiestimaatin.Tarkemmin sanottuna, oletetaan j ∈ { 1 , … , d } j in {1, ldots, d}j∈{1,…,d}, ja määrittele ${\nabla }_{j}f(x):=\left(\frac{\partial f(x)}{\partial x_j}\right)e_j$ on (f(x)) th$j$ derivaatat koordinaattisuunnassa, missä$e_j\in {\mathbb{R}}^d$ Se on ensimmäinen$j$ yksikkövektori.Koordinaattiderivaatojen keskeinen ominaisuus on se${\nabla }_{j}f(x^{\ast })=0$, koska tiedämme $\nabla f(x^{\ast })=0$ .Tämän johdannainen jokaisen datapisteen kanssa$\nabla f_j$ erilainen, jälkimmäinen on$x^{\ast }$ ei ehkä ole nolla. Siksi meillä on:
$$\Vert \nabla f(x)-{\nabla }_{j}f(x){\Vert }^2\to 0\text{kun}x\to x^{\ast }(26)$$
Tämä tarkoittaa, että koordinaattiderivaata täyttää varianssin vähennysominaisuuden (12).Lisäksi voimme käyttää${\nabla }_{j}f(x)$ rakentaa$\nabla f(x)$ puolueeton arvio.Oletetaan esimerkiksi$j$ on kokoelmasta { 1 , … , d } {1, ldots, d}{1,…,d} Tasaisesti satunnaisesti valittu indeksi .Siksi mille tahansa i ∈ { 1 , … , d } i in {1, ldots, d}i∈{1,…,d},Meillä on $P[j=i]=\frac{1}{d}$ . siksi,$d\times {\nabla }_{j}f(x)$ Joo$\nabla f(x)$ Puolueeton arvio, koska:
$$E\left[d{\nabla }_{j}f(x)\right]=d\sum _{i=1}^{d}P[j=i]\frac{\partial f(x)}{\partial x_i}{e}_i=\sum _{i=1}^d\frac{\partial f(x)}{\partial x_i}{e}_i=\nabla f(x)$$

siksi,${\nabla }_{j}f(x)$ Sillä on kaikki ihanteelliset ominaisuudet, joita odotamme VR:ltä arvioiden täydet gradientit, ilman tarvetta käyttää kovariaatteja. Yksi haittapuoli tämän koordinaattigradientin käytössä on, että se on laskennallisesti kallista summaongelmallemme (2).Tämä johtuu laskennasta${\nabla }_{j}f(x)$ Tarve käydä läpi koko tietojoukon, koska${\nabla }_{j}f(x)=\frac{1}{n}{\sum }_{i=1}^n{\nabla }_j{f}_i(x)$ . Siksi koordinaattiderivaataiden käyttö näyttää olevan yhteensopimaton summaongelmamme rakenteen kanssa. Usein voimme kuitenkin kirjoittaa alkuperäisen ongelman (2) uudelleen ns. kaksoisformulaatioon, jossa koordinaattiderivaatat voivat hyödyntää luontaista rakennetta.

Esimerkiksi L2-reguloidun lineaarisen mallin (15) kaksoiskaava on:
$$v^{\ast }\in \arg \underset{v\in {\mathbb{R}}^n}{\max }\frac{1}{n}\sum _{i=1}^n-{\ell }_i^{\ast }(-v_i)-\frac{\lambda }{2}{\Vert \frac{1}{\lambda }\sum _{i=1}^n{v}_i{a}_i\Vert }^2(27)$$
sisään${\ell }_i^{\ast }(v)$ Joo${\ell }_i$ kupera konjugaatti.Voimme käyttää kartoitusta$x=\frac{1}{\lambda }{\sum }_{i=1}^n{v}_i{a}_i$ palauttaa alkuperäinen ongelma (15)$x$ muuttuja.ratkaisee$v^{\ast }$ Korvaamalla yllä olevan kartoituksen oikealle puolelle, saadaan ratkaisu (15)$x^{\ast }$。

Huomaa, että tämä kaksoisongelma on $n$ todellisia muuttujia$v_i\in \mathbb{R}$ , joka vastaa yhtä kullekin harjoitusnäytteelle.Lisäksi jokainen kaksoishäviötoiminto${\ell }_i^{\ast }$ vain$v_i$ Toiminto. Eli häviöfunktion ensimmäinen termi on koordinoidusti erotettavissa. Tämä koordinaattien erotettavuus yhdistettynä toisen termin yksinkertaiseen muotoon mahdollistaa koordinaattien nousumenetelmän tehokkaan toteuttamisen.Todellakin, Shalev-Shwartz ja Zhang osoittivat, että koordinaattien nousu tässä ongelmassa on samanlainen iteratiivinen monimutkaisuus kuin SAG, SAGA ja SVRG$O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$。

Myös iterointikustannukset ja algoritmin rakenne ovat hyvin samankaltaisia: summaus seurannan avulla ${\sum }_{i=1}^n{v}_i{a}_i$ Toisen termin käsittelemiseksi kohdassa (27) jokaisen kaksoiskoordinaattisen nousuiteroinnin tarvitsee ottaa huomioon vain yksi harjoitusnäyte, ja kunkin iteroinnin hinta on sama kuin$n$ Ei mitään tehtävää.Lisäksi voimme käyttää 1D-viivahakua laskeaksemme tehokkaasti askelkoon maksimoitavaksi$v_i$ Toiminnon kaksi tavoitetta.Tämä tarkoittaa, että jopa ilman$L_{\text{max}}$ Tai merkityksellisten määrien tunteminen, on myös mahdollista saavuttaa nopeita pahimman tapauksen ajoaikoja VR-menetelmille.

3. Varianssin vähentämisen käytännön kysymyksiä

Perusvarianssin vähennysmenetelmän (VR) käyttöönottamiseksi ja kohtuullisen suorituskyvyn saavuttamiseksi on ratkaistava useita toteutuskysymyksiä. Tässä osiossa käsittelemme useita asioita, joita ei ole käsitelty yllä.

3.1.SAG/SAGA/SVRG-askelkoko

Optimointialgoritmien alalla, erityisesti vaihteluvähennysmenetelmissä, kuten stokastinen keskigradientti (SAG), stokastinen keskimääräinen gradientti (SAGA) ja stokastinen gradientti (SVRG), askelkoon asettaminen on keskeinen kysymys.Vaikka stokastisessa kaksoiskoordinaattinousumenetelmässä (SDCA) voimme käyttää kaksoistavoitetta askelkoon määrittämiseen, SAG:n, SAGAn ja SVRG:n alkuperäisten muuttujamenetelmien teoreettinen perusta on, että askelkoon tulisi olla$\gamma =O\left(\frac{1}{L_{\text{max}}}\right)$ muodossa.Käytännön sovelluksissa emme kuitenkaan usein tiedä$L_{\text{max}}$ tarkka arvo, ja muiden askelkokojen käyttö voi parantaa suorituskykyä.

Klassinen strategia askelkoon asettamiseen täyden gradientin laskeutumismenetelmässä (full-GD) on Armijon viivahaku.nykyinen piste$x_k$ ja hakusuunta$g_k$, Armijon linjahaku sisään ${\gamma }_k$ suoritetaan linjalla, joka on määritelty γ k ∈ { γ : xk + γ gk } gamma_k in {gamma : x_k + gamma g_k}γk​∈{γ:xk​+γgk​}, ja toimintoa on pienennettävä riittävästi, eli:
$$f(x_k+{\gamma }_k{g}_k)<f(x_k)-c{\gamma }_k\Vert \nabla f(x_k){\Vert }^2$$
Tämä lähestymistapa vaatii kuitenkin useita ehdokasvaiheita${\gamma }_k$ Laskeminen$f(x_k+{\gamma }_k{g}_k)$, joka arvioi $f(x)$ Koko tietojoukon läpikäyminen maksaa kohtuutonta.

Tämän ongelman ratkaisemiseksi voidaan käyttää satunnaisvaihtelumenetelmää sellaisten, jotka täyttävät seuraavat ehdot ${\gamma }_k$：
$$f_{ik}(x_k+{\gamma }_k{g}_k)<f_{ik}(x_k)-c{\gamma }_k\Vert \nabla f_{ik}(x_k){\Vert }^2$$
Tämä lähestymistapa toimii yleensä hyvin käytännössä, varsinkin kun$\Vert \nabla f_{ik}(x_k)\Vert$ ei ole lähellä nollaa, vaikka tällä hetkellä ei ole olemassa teoriaa, joka tukisi tätä lähestymistapaa.

Lisäksi Mairal ehdotti "Bottou-tekniikkaa" askelkoon asettamiseen käytännössä. Tämä menetelmä suorittaa binaarihaun ottamalla pienen osan tietojoukosta (esim. 5 %) yrittääkseen löytää optimaalisen askelkoon yhdellä kertaa tämän näytteen läpi. Samoin kuin Armijon rivihaku, tämä menetelmä toimii usein hyvin käytännössä, mutta siitä puuttuu jälleen teoreettinen perusta.

Huomaa, että yllä oleva sisältö on versio alkuperäisestä tekstistä, jossa käytetään Markdown-muotoa matemaattisten kaavojen ja muuttujien esittämiseen.

SDCA-menetelmällä on kuitenkin myös joitain haittoja.Ensinnäkin se vaatii konveksin konjugaatin laskemista${\ell }_i^{\ast }$ yksinkertaisen gradientin sijaan. Meillä ei ole automaattista differentiaaliekvivalenttia konveksille konjugaateille, joten tämä voi lisätä toteutusta. Viimeaikainen työ on ehdottanut "kaksoisvapaita" SDCA-menetelmiä, jotka eivät vaadi konjugointia ja käyttävät sen sijaan suoraan gradientteja. Näissä menetelmissä ei kuitenkaan ole enää mahdollista seurata kaksoiskohdetta askelkoon asettamiseksi.Toiseksi, vaikka SDCA vain vaatii$O(n+d)$ muistia ongelman (15) ratkaisemiseksi, mutta tätä ongelmaluokkaa varten SAG/SAGA tarvitsee vain$O(n+d)$ muistia (katso osa 3).SDCA-muunnos, joka sopii yleisempiin SAG/SAGA-ongelmiin$O(nd)$ muisti, koska$v_i$ tulla omistavaksi$d$ elementtien vektori. SDCA:n viimeinen hienoinen haittapuoli on, että se olettaa implisiittisesti vahvan kuperuusvakion$\mu$ yhtä suuri$\lambda$ .varten$\mu$ enemmän kuin$\lambda$ Ongelmana on, että alkuperäinen VR-menetelmä on yleensä huomattavasti parempi kuin SDCA.

3.2 Irtisanomisen ehtojen määrittäminen

Algoritmien optimoinnin alalla luotamme usein iteratiivisen monimutkaisuuden teoreettisiin tuloksiin ennustaaksemme pahimman tapauksen iteraatioiden lukumäärää, jota algoritmi vaatii tietyn tarkkuuden saavuttamiseksi. Nämä teoreettiset rajat perustuvat kuitenkin usein joihinkin vakioihin, joita emme voi ennustaa, ja käytännön sovelluksissa algoritmi voi usein saavuttaa odotetun tarkkuuden harvemmilla iteraatioilla. Siksi meidän on määritettävä joitain testikriteereitä määrittääksemme, milloin algoritmi tulisi lopettaa.

Perinteisessä täyden gradientin laskeutumismenetelmässä (full-GD) käytämme yleensä gradientin normia $\Vert \nabla f(x_k)\Vert$ Tai jokin muu tähän liittyvä määrä päättääkseen, milloin iteraatio lopetetaan.SVRG-menetelmälle voimme hyväksyä saman kriteerin, mutta käyttää$\Vert \nabla f({\bar{x}}_s)\Vert$ tuomion perusteeksi.SAG/SAGA-menetelmässä, vaikka emme eksplisiittisesti laske täydellistä gradienttia, määrä $ g_{bar{k}} $ on vähitellen likimääräinen$\nabla f(x_k)$, siksi käytä $\Vert g_{\bar{k}}\Vert$ pysäytysehtona on järkevä heuristinen.

SDCA-menetelmässä voimme seurata kaksoisobjektin gradienttia lisätallennustyöllä lisäämättä asymptoottisia lisäkustannuksia.Lisäksi järjestelmällisempi lähestymistapa olisi seurata kaksoiseroa, vaikka tämä lisäisikin$O(n)$ kustannuksia, mutta se pystyy tarjoamaan irtisanomisen ehdot kahdella aukkotodistuksella. Lisäksi vahvasti kuperoiden kohteiden optimaalisuusehtoon perustuen MISO-menetelmä ottaa käyttöön periaatteellisen menetelmän, joka perustuu neliölliseen alarajaan [41].

Seuraavat ovat matemaattisia kaavoja ja muuttujia, jotka on ilmaistu Markdown-muodossa:

• Gradienttinormi:$\Vert \nabla f(x_k)\Vert$
• Gradienttinormi SVRG-menetelmässä:$\Vert \nabla f({\bar{x}}_s)\Vert$
• Approksimaatiogradientin määrä SAG/SAGA-menetelmässä: $ g_{bar{k}} $
• Lisääntynyt iteraatiokohtainen hinta:$O(n)$
• MISO menetelmä
• neliöllinen alaraja

Huomaa, että yllä oleva sisältö on versio alkuperäisestä tekstistä, jossa käytetään Markdown-muotoa matemaattisten kaavojen ja muuttujien esittämiseen.

3.3 Vähennä muistivaatimuksia

Vaikka SVRG (Stochastic Variational Reduction of Gradient) -algoritmi eliminoi aikaisempien variaatioiden vähentämismenetelmien muistivaatimukset, käytännön sovelluksissa SAG (Stochastic Average Gradient Descent) ja SAGA (Stochastic Average Gradient Descent with Gradient Accumulation) -algoritmeja käytetään monissa ongelmissa. vaativat yleensä vähemmän iteraatioita kuin SVRG-algoritmi.Tämä herätti ajatuksen: Onko olemassa joitakin ongelmia, jotka sallivat SAG:n/SAGAn$O(nd)$ Muistivaatimukset on toteutettu alla. Tässä osiossa tarkastellaan lineaaristen mallien luokkaa, jonka muistivaatimuksia voidaan vähentää merkittävästi.

Harkitse lineaarista mallia, jossa jokainen funktio $f_i(x)$ Se voidaan ilmaista näin${\xi }_i({\mathbf{a}}_i^{\top }x)$ .oikein$x$ Johdannainen antaa gradienttimuodon:
$$\nabla f_i(x)={\xi }^{\prime }({\mathbf{a}}_i^{\top }x){\mathbf{a}}_i$$
tässä,${\xi }^{\prime }$ ilmaista$\xi$ johdannainen.Olettaen, että meillä on suora pääsy ominaisvektoreihin${\mathbf{a}}_i$, niin SAG/SAGA-menetelmän toteuttamiseksi meidän tarvitsee vain tallentaa skalaari $\xi ({\mathbf{a}}_i^{\top }x)$ .Tällä tavalla muistivaatimukset vaihtelevat$O(nd)$ vähennetty$O(n)$ . SVRG-algoritmi voi myös hyödyntää tätä gradienttirakennetta: tallentamalla tämän$n$ skalaari, voimme vähentää SVRG:n "sisäistä" iteraatiota kohti vaadittavien gradienttiarviointien lukumäärän 1:een tämän luokan ongelmatilanteissa.

On muitakin ongelmia, kuten todennäköisyyspohjaiset graafiset mallit, jotka tarjoavat myös mahdollisuuden vähentää muistivaatimuksia [66]. Tietyn tietorakenteen ja algoritmin optimoinnin avulla algoritmin ajon aikana vaatimia muistiresursseja voidaan edelleen vähentää.

Seuraavat ovat matemaattisia kaavoja ja muuttujia, jotka on ilmaistu Markdown-muodossa:

• Lineaarisen mallin toiminto:$f_i(x)={\xi }_i({\mathbf{a}}_i^{\top }x)$
• Gradienttilauseke:$\nabla f_i(x)={\xi }^{\prime }({\mathbf{a}}_i^{\top }x){\mathbf{a}}_i$
• Ominaisuusvektori:${\mathbf{a}}_i$
• Muistivaatimukset vaihtelevat $O(nd)$ Vähennetty$O(n)$。

3.4 Harvaiden gradienttien käsittely

Joissakin ongelmissa gradientti $\nabla f_i(x)$ Saattaa sisältää suuren määrän nolla-arvoja, kuten lineaarinen malli, jossa on vähän ominaisuuksia.Tässä tapauksessa perinteinen stokastinen gradienttilaskeutumisalgoritmi (SGD) voidaan toteuttaa tehokkaasti, jolloin laskennallinen monimutkaisuus on lineaarinen gradientin nollasta poikkeavien elementtien lukumäärässä, joka on yleensä paljon pienempi kuin ongelman ulottuvuus.$d$ . Tätä etua ei kuitenkaan hyödynnetä standardeissa variaatiovähennysmenetelmissä (VR). Onneksi on olemassa kaksi tunnettua tapaa parantaa tätä.

Ensimmäistä parannusta ehdottivat Schmidt et al., joka hyödyntää päivitysprosessin yksinkertaisuutta ja toteuttaa muunnelman "lennossa" tapahtuvasta laskennasta siten, että kunkin iteroinnin hinta on verrannollinen nollasta poikkeavien lukujen määrään. elementtejä.SAG esimerkkinä (mutta tämä lähestymistapa toimii kaikissa muunnelmissa), tämä tehdään siten, että koko vektoria ei tallenneta jokaisen iteraation jälkeen$v_{ik}$, mutta laskee vain ne, jotka vastaavat nollasta poikkeavia elementtejä $v_{i{k}_j}$, päivittämällä jokainen muuttuja sen jälkeen, kun elementti oli viimeksi muu kuin nolla $v_{i{k}_j}$。

Toista parannusmenetelmää ehdottivat Leblond et ai. SAGA:lle, joka päivittää kaavan $x_{k+1}=x_k-\gamma (\nabla f_{ik}(x_k)-\nabla f_{ik}({\bar{x}}_{ik})+{\bar{g}}_k)$ Lisäsatunnaisuus otetaan käyttöön. tässä,$\nabla f_{ik}(x_k)$ ja$\nabla f_{ik}({\bar{x}}_{ik})$ on harvaa, ja${\bar{g}}_k$ on tiheä.Tässä menetelmässä tiheä termi$({\bar{g}}_k{)}_j$ Jokainen komponentti korvataan$w_j({\bar{g}}_k{)}_j$,sisään $w\in {\mathbb{R}}^d$ on satunnainen harva vektori, jonka tukijoukko sisältyy$\nabla f_{ik}(x_k)$ , ja sen odotetaan olevan vakiovektori, jonka kaikki elementit ovat yhtä suuret kuin 1. Näin päivitysprosessi pysyy puolueettomana (vaikkakin nyt harvakseltaan), eikä lisääntynyt varianssi vaikuta algoritmin konvergenssinopeuteen. Lisätietoja tarjoavat Leblond et ai.

Seuraavat ovat matemaattisia kaavoja ja muuttujia, jotka on ilmaistu Markdown-muodossa:

• kaltevuus:$\nabla f_i(x)$
• SGD päivitys:$x_{k+1}=x_k-\gamma (\nabla f_{ik}(x_k)-\nabla f_{ik}({\bar{x}}_{ik})+{\bar{g}}_k)$
• Harva gradientti:$\nabla f_{ik}(x_k)$ ja$\nabla f_{ik}({\bar{x}}_{ik})$
• Tiheä gradientti:${\bar{g}}_k$
• Satunnaiset harvat vektorit:$w$
• Odottaa vakiovektoria: vektoria, jonka kaikki elementit ovat yhtä suuret kuin 1.