Sammanfattning I den här artikeln anser vi att en klass av konvexa optimeringsproblem i finit-summan, vars objektiva funktion ges av summan av m (≥ 1) släta komponenter tillsammans med några andra relativt enkla termer. Vi introducerar först en deterministisk primal-dual gradient (PDG) metod som kan uppnå optimal blackbox iteration komplexitet för att lösa dessa sammansatta optimeringsproblem med hjälp av ett primal-dual termineringskriterium. Vårt stora bidrag är att utveckla en randomiserad primal-dual gradient (RPDG) metod, som behöver beräkna gradienten av endast en slumpmässigt vald jämn komponent vid varje iteration, men kan möjligen uppnå bättre komplexitet än PDG i termer av det totala antalet gradient utvärderingar. Mer specifikt visar vi att det totala antalet gradient bedömningar som utförs av RPDG kan vara O ( ε m) gånger mindre, både i förväntan och med hög sannolikhet, än de som utförs med deterministiska optimala första ordningen metoder under gynnsamma situationer. Vi visar också att komplexiteten i RPDG-metoden inte är improvisationsbar genom att utveckla en ny lägre komplexitet bundet för en allmän klass av randomiserade metoder för att lösa storskaliga konvexa optimeringsproblem. Genom utvecklingen av PDG och RPDG introducerar vi dessutom en ny spelteoretisk tolkning för dessa optimala metoder för konvex optimering.
En primal-dual form av den legaliserade accelererade lutningsmetoden visas i REF.
An optimal randomized incremental gradient method
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}