Vi betraktar det grundläggande problemet med förutsägelse med expertråd där experterna är "optimerbara": det finns en svart-box optimering oracle som kan användas för att beräkna, i konstant tid, den ledande experten i retrospekt när som helst i tiden. I denna inställning ger vi en ny online-algoritm som uppnår försvinnande ånger med avseende på N experter totalt r Op? N q beräkningstid. Vi ger också en lägre gräns som visar att denna körtid inte kan förbättras (upp till loggfaktorer) i oraklet modellen, vilket uppvisar en quadratic speedup jämfört med standard, oraklefri inställning där den tid som krävs för att försvinna ånger är r  påpN q. Dessa resultat visar ett exponentiellt gap mellan kraften av optimering i online-inlärning och dess kraft i statistisk inlärning: i det senare, en optimering oracle-d.v.s., en effektiv empirisk riskminimer-tillåter att lära sig en ändlig hypotes klass av storlek N i tid Oplog N q. Vi studerar också konsekvenserna av våra resultat för att lära sig i upprepade nollsummespel, i en miljö där spelarna har tillgång till orakel som beräknar, i ständig tid, deras bästa svar på någon blandad strategi av sin motståndare. Vi visar att den körtid som krävs för att approximera spelets minimax-värde i denna inställning är r  påp? N q, vilket återigen ger en quadratic förbättring på orakle-fri inställning, där r  påpN q är känd för att vara tight.
I det senaste arbetet visar REF att en online-algoritm kräver en tid för att approximera värdet av ett nollsummespel med två spelare, även när det ges tillgång till bästa-respons-orakel med konstant tid.
The computational power of optimization in online learning