Vi studerar en allmän online konvex optimering problem. Vi har en konvex uppsättning S och en okänd sekvens av kostnadsfunktioner ct, c2,..., och i varje period väljer vi en genomförbar punkt xt i S, och lära sig kostnaden ct (xt). Om fimction ct också avslöjas efter varje period då, som Zinkevitj visar i [25], lutning nedstigning kan användas på dessa funktioner för att få ångra gränser för O (~ / ~). Det vill säga, efter n rundor, den totala kostnaden som uppstår kommer att vara O(v/~ ) mer än kostnaden för det bästa enskilda möjliga beslut som valts med fördelen av efterhand, min~ ~ ct (x). Vi utvidgar detta till "bandit" inställning, där, under varje period, endast kostnaden ct (xt) avslöjas, och bundna den förväntade ångra som O(na/4). Vårt tillvägagångssätt använder en enkel approximation av lutningen som beräknas fl'om utvärdera ct vid en enda (random) punkt. Vi visar att denna partiska uppskattning är tillräcklig för ap-3. proximat lutning nedstigning på sekvensen av flmctions. Med andra ord är det möjligt att använda lutning nedstigning utan att se något mer än värdet av funktionerna vid en enda punkt. Garantierna håller även i det mest allmänna fallet: online mot en adaptiv motståndare. För online linjär optimering problem [15], algoritmer med låg ånger i bandit inställning har nyligen getts mot glömska [1] och adaptiva motståndare [19]. I motsats till dessa algoritmer, som skiljer mellan explicit utforska och utnyttja perioder, kan vår algoritm tolkas som att göra en liten mängd prospektering i varje period.
I synnerhet föreslog REF att man skulle använda ett enkelt trick för att uppskatta lutningen av en funktion med ett enda dataprov.
Online convex optimization in the bandit setting: gradient descent without a gradient
{'venue': "SODA '05", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}