Abstrakt. I detta dokument studerar vi effekten av stokastiska fel på två begränsade inkrementella sub-gradientalgoritmer. Vi ser de inkrementella sub-gradientalgoritmer som decentraliserade nätverksoptimeringsalgoritmer som tillämpas för att minimera en summa av funktioner, när varje komponentfunktion är känd endast för en viss agent i ett distribuerat nätverk. Vi studerar först standard cyklisk inkrementell undergradientalgoritm där agenterna bildar en ringstruktur och passerar iteraten i en cykel. Vi anser att metoden med stokastiska fel i de sub-gradient utvärderingar och ger tillräckliga villkor på ögonblicken av stokastiska fel som garanterar nästan säker konvergens när en minskande steg-storlek används. Vi får också nästan säkra gränser på algoritmens prestanda när en konstant stegstorlek används. Vi betraktar sedan Markov randomiserade inkrementella subgradientmetoden, som är en icke-cyklisk version av den inkrementella algoritmen där sekvensen av dataagenter modelleras som en tid icke-homogen Markov kedja. En sådan modell är lämplig för mobila nät, eftersom nätets topologi förändras över tid i dessa nät. Vi fastställer konvergensresultaten och felgränserna för Markovs randomiserade metod i närvaro av stokastiska fel för att minska respektive konstanta stegstorlekar. Ett problem av nyligen intresse för distribuerade nätverk är utformningen av decentraliserade algoritmer för att minimera en summa av funktioner, när varje komponent funktion är känd endast för en viss agent [4, 9, 20, 24, 29]. Sådana problem uppstår i många nättillämpningar, bland annat i nätuppskattning, inlärning, signalbehandling och resursfördelning [6, 16, [28] [29] [30] [31]. I dessa tillämpningar finns det ingen central samordnare som har tillgång till all information och därför behövs decentraliserade algoritmer för att lösa problemen. I detta dokument, vi anser decentraliserade subgradienta metoder för begränsad minimering av en summa av konvexa funktioner, när varje komponent funktion endast är känd delvis (med stokastiska fel) till en specifik nätverksagent. Vi studerar två inkrementella subgradienta metoder med stokastiska fel: en cyklisk och en (icke-cyklisk) Markov randomiserad inkrementell metod. Den cykliska inkrementella algoritmen är en decentraliserad metod där nätverksagenterna bildar en ring och bearbetar informationen cykliskt. Den inkrementella metoden föreslogs ursprungligen av Kibardin [11] och har studerats mer nyligen i [4, 7, 17, 20, 33]. Inkrementella gradientalgoritmer användes först för att optimera vikterna i neurala nätverk utbildning [7, 17, 33], och de flesta av den tillhörande litteraturen behandlar olika icke-konvexa okonstruerade optimeringsproblem [3, 4, 7, 33, 34]. Den inkrementella subgradientalgoritmen för icke-differentierad konvex optimering har undersökts i [19,20] utan fel, och i [13,21,29,34] där effekterna av deterministiska fel beaktas. Algoritmen som vi betraktar i denna uppsats är stokastisk och skiljer sig som sådan från den befintliga litteraturen. För denna algoritm skapar vi konvergens för att minska stegstorleken och ger ett fel som är bundet till konstant stegstorlek. Markov randomiserade inkrementell algoritm är en decentraliserad metod där iteraterna genereras stegvis inom nätverket genom att överföra dem från agent till agent. Till skillnad från den cykliska inkrementella metoden, där agentnätverket har en ringstruktur och informationsflödet är längs denna ring (cykel), i Markov
Den asymptotiska analysen av dubbla problem i detta arbete följer samma allmänna översikt som den av den cykliska inkrementella algoritmen i REF, med ytterligare ändringar som införts för att hantera asynkroni.
Incremental Stochastic Subgradient Algorithms for Convex Optimization
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Computer Science', 'Mathematics']}