Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01tm70mx606
 Title: Minimax Rates for Online Convex Optimization with Limited Decision Changes Authors: Altschuler, Jason Advisors: Hazan, Elad Department: Computer Science Class Year: 2016 Abstract: Online convex optimization has rececently received substantial attention due to its elegant theory and many practical applications. It is well-known that when the player receives either fullinformation feedback or partial-information (bandit) feedback, the minimax rate for expected regret is Θ(√T), where T is the number of iterations in the game. However, real world constraints often limit the player from making many decision changes. We analyze the setting where the player is limited to S ≤ T switches between actions, and give a complete characterization of the minimax rate. When the player receives bandit feedback, we prove the minimax rate is Θ( ˜ T/√S) up to a logarithmic factor in T. When the player receives full-information feedback, the minimax rate is known to be Θ(√T) for S = Ω(√T); we complete the story by proving the minimax rate is Θ( TS) for S = O(√T). Our lower bound proofs are information theoretic in nature, whereas our upper bounds are shown by presenting algorithms which provably achieve the optimal minimax rate. Extent: 25 pages URI: http://arks.princeton.edu/ark:/88435/dsp01tm70mx606 Type of Material: Princeton University Senior Theses Language: en_US Appears in Collections: Computer Science, 1988-2016

Files in This Item:
File SizeFormat
Altschuler_Jason_thesis.pdf361.82 kBAdobe PDF

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.