Linjär optimering är många gånger algoritmiskt enklare än icke-linjär konvex optimering. Linjär optimering över matroidpolytoper, matchande polytoper och vägpolytoper är exempel på problem för vilka vi har enkla och effektiva kombinatoriska algoritmer, men vars icke-linjära konvexa motsvarighet är svårare och medger betydligt mindre effektiva algoritmer. Detta motiverar beräkningsmodellen för konvex optimering, inklusive offline, online och stokastiska inställningar, med hjälp av en linjär optimering orakel. I denna beräkningsmodell ger vi flera nya resultat som förbättras jämfört med den tidigare tekniken. Vårt huvudresultat är en ny villkorad gradientalgoritm för smidig och starkt konvex optimering över polyhedral set som utför endast ett linjärt optimeringssteg över domänen på varje iteration och har en linjär konvergenshastighet. Detta ger en exponentiell förbättring av konvergensen jämfört med tidigare resultat. Baserat på denna nya villkorade gradient algoritm ger vi de första algoritmerna för online konvex optimering över polyhedral uppsättningar som utför endast en linjär optimering steg över domänen samtidigt som de har optimala ångergarantier, svarar på en öppen fråga om [20, 16]. Våra online-algoritmer innebär också villkorliga gradientalgoritmer för icke-smooth och stokastisk konvex optimering med samma konvergenshastighet som projicerade (sub)gradientmetoder.
En förbättrad villkorad gradientalgoritm utformades senare för smidig och starkt konvex optimering som uppnår den optimala O( ε T ) motariska ångra bundna REF.
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
{'venue': None, 'journal': 'arXiv: Learning', 'mag_field_of_study': ['Mathematics', 'Computer Science']}