Klassiska stokastiska gradientmetoder är väl lämpade för att minimera förväntade objektiva funktioner. De gäller dock inte för minimering av en ickelinjär funktion som innefattar förväntade värden eller en sammansättning av två förväntade värdefunktioner, d.v.s. problem med formen min. För att lösa detta stokastiska kompositionsproblem föreslår vi en klass av stokastisk kompositionsnedstigningsalgoritmer (SCGD) som kan ses som stokastiska versioner av kvasigradientmetoden. SCGD uppdaterar lösningarna baserat på bullriga provgradienter av f v, g w och använder en hjälpvariabel för att spåra den okända mängden E w [g w (x)]. Vi bevisar att SCGD nästan säkert konvergerar till en optimal lösning för konvexa optimeringsproblem, så länge en sådan lösning finns. Konvergensen innefattar samspelet mellan två iterationer med olika tidsskalor. För konvexa konvexa problem uppnår SCGD en konvergensgrad av O(k −1/4 ) i det allmänna fallet och O(k −2/3 ) i det starkt konvexa fallet, efter att ha tagit k prover. För smidiga konvexa problem kan SCGD accelereras för att konvergera med en hastighet av O(k −2/7 ) i det allmänna fallet och O(k −4/5 ) i det starkt konvexa fallet. För icke konvexa problem bevisar vi att varje gränspunkt som genereras av SCGD är en stationär punkt, för vilken vi också tillhandahåller konvergensanalysen. I själva verket är den stokastiska inställningen där man vill optimera sammansättningar av förväntade värdefunktioner mycket vanlig i praktiken. De föreslagna SCGD-metoderna finner breda tillämpningar när det gäller lärande, uppskattning, dynamisk programmering m.m.
Allmänna kompositionella stokastiska problem, där målet är att minimera sammansättningar av förväntade värdefunktioner, diskuterades först i REF och löstes via SCGD-algoritmen.
Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
{'venue': None, 'journal': 'arXiv: Machine Learning', 'mag_field_of_study': ['Mathematics', 'Computer Science']}