Online konvex programmering har nyligen vuxit fram som en kraftfull primitiv för att designa maskininlärningsalgoritmer. Till exempel kan OCP användas för att lära sig en linjär klassificering, dynamiskt ombalansera ett binärt sökträd, hitta den kortaste vägen i en graf med okända kantlängder, lösa ett strukturerat klassificeringsproblem, eller hitta en bra strategi i ett omfattande-form spel. Flera forskare har konstruerat algoritmer utan motstycke för OCP. Men jämfört med algoritmer för speciella fall av OCP såsom lärande från expertråd, dessa algoritmer är inte särskilt många eller flexibla. När man lär sig av expertrådgivningen är ett verktyg som har visat sig vara särskilt värdefullt överensstämmelse mellan algoritmer utan motstycke och konvexa potentiella funktioner: genom att resonera om dessa potentiella funktioner har forskarna utformat algoritmer med ett brett utbud av användbara garantier såsom bra prestanda när målhypotesen är gles. Hittills har det inte funnits något sådant recept för det mer allmänna OCP-problemet, och därför ingen förmåga att ställa in OCP-algoritmer för att dra nytta av egenskaperna hos problemet eller data. I den här artikeln härleder vi en ny klass av icke-regelbunden inlärningsalgoritmer för OCP. Dessa Lagrangian Hedging algoritmer är baserade på en allmän klass av potentiella funktioner, och är en direkt generalisering av kända inlärningsregler som viktad majoritet och extern-regret matchning. Förutom att bevisa ånger gränser, visar vi våra algoritmer lära sig att spela ett kort poker.
REF utvecklade Lagrangian Hedging algoritm, som kan användas för att hitta en Nash jämvikt i EFGs.
No-regret algorithms for online convex programs
{'venue': 'In Neural Information Processing Systems 19', 'journal': None, 'mag_field_of_study': ['Computer Science']}