Vi föreslår en version av follow-the-perturbed-leader online förutsägelse algoritm där de kumulativa förlusterna störs av oberoende symmetriska slumpmässiga promenader. Prognosatorn har visat sig uppnå ett förväntat beklagande av den optimala ordningen O( ε n log N ) där n är tidshorisonten och N är antalet experter. Ännu viktigare, det visas att prognosmakaren ändrar sin förutsägelse vid de flesta O ( ε n log N ) gånger, i förväntan. Vi utökar också analysen till online combinatorial optimering och visar att även i denna mer allmänna inställning, prognostiseraren sällan växlar mellan experter samtidigt som den har ett beklagande av nära-optimal ordning. Online-inlärning, online-kombinatorisk optimering, Följ Perturbed Leader, Random walk I. PRELIMINARIER I denna artikel studerar vi problemet med online-förutsägelse med expertråd, se [1]. Problemet kan beskrivas som ett upprepat spel mellan en prognosmakare och en motståndare-miljön. Vid varje tillfälle omedelbart t = 1,...., n, prognostaren väljer en av de N tillgängliga åtgärder (ofta kallas experter) och lider en förlust l i,t [0, 1] som motsvarar den valda åtgärden i. Vi anser att den så kallade omedvetna motståndaren modell där miljön väljer alla förluster innan förutsägelsen spelet börjar och avslöjar förluster l i,t vid tidpunkten t efter prognosen har gjort sin förutsägelse. Förlusterna är deterministiska men prognosmakaren kan randomisera: vid tiden t, prognostaren väljer en sannolikhetsfördelning p t över uppsättningen N åtgärder och drar en slumpmässig åtgärd I t enligt fördelningen p t. Förutsägelseprotokollet beskrivs i figur 1. Det vanliga målet för standard förutsägelse problemet är att utforma en algoritm sådan att den kumulativa förlusten L n = n t=1 l Det,t är så liten som möjligt, i förväntan och / eller med hög sannolikhet (där sannolikheten är med avseende på prognosatorns randomisering). Eftersom vi inte gör några antaganden om hur miljön genererar förlusterna kan vi inte
Devroye m.fl. REF föreslog en PFE-algoritm vars förväntade ånger och förväntade antal växlar är både O( ε T log n), där n är storleken på åtgärden uppsättningen.
Prediction by Random-Walk Perturbation
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}