För att klara av icke-stationära miljöer har de senaste framstegen inom onlineoptimering introducerat begreppet adaptiv ånger, som mäter prestandan hos en onlineinlärare mot olika jämförelseprodukter inom olika tidsintervall. Tidigare studier har föreslagit olika algoritmer för att ge låg adaptiv ånger under olika scenarier. Alla befintliga algoritmer måste dock fråga gradienten för förlustfunktionen minst O(logt) gånger i varje iteration t, vilket hindrar deras tillämpningar till breda domäner, särskilt när utvärderingen av gradienter är dyr. För att ta itu med denna begränsning föreslår vi en serie beräkningseffektiva algoritmer för att minimera adaptiv ånger av allmänna konvexa, starkt konvexa och exponentiellt konkava funktioner respektive. Nyckelidén är att ersätta varje förlustfunktion med en noggrant utformad surrogatförlust, som begränsar den ursprungliga förlustfunktionen underifrån. Vi visar att de föreslagna algoritmerna bara frågar lutningen en gång per iteration, och uppnå samma teoretiska garantier som tidigare optimala algoritmer. Empiriska resultat visar hur effektiva och effektiva våra metoder är.
Nyligen, REF visar att för att minimera adaptiv ånger av konvexa funktioner, kan vi använda surrogat förlust för att minska antalet gradient utvärderingar per runda från O(log T ) till 1.
Minimizing Adaptive Regret with One Gradient per Iteration
{'venue': 'IJCAI', 'journal': None, 'mag_field_of_study': ['Computer Science']}