Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations

H. Brendan McMahan, Francesco Orabona

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

We study algorithms for online linear optimization in Hilbert spaces, focusing on the case where the player is unconstrained. We develop a novel characterization of a large class of minimax algorithms, recovering, and even improving, several previous results as immediate corollaries. Moreover, using our tools, we develop an algorithm that provides a regret bound of O ((Equation presented)), where U is the L2 norm of an arbitrary comparator and both T and U are unknown to the player. This bound is optimal up to √ log log T terms. When T is known, we derive an algorithm with an optimal regret bound (up to constant factors). For both the known and unknown T case, a Normal approximation to the conditional value of the game proves to be the key analysis tool.
Original languageEnglish (US)
Title of host publicationJournal of Machine Learning Research
PublisherMicrotome [email protected]
Pages1020-1039
Number of pages20
StatePublished - Jan 1 2014
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-25

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Statistics and Probability
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations'. Together they form a unique fingerprint.

Cite this