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    Request a copy


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