Please use this identifier to cite or link to this item:
|Title:||Minimax Rates for Online Convex Optimization with Limited Decision Changes|
|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.|
|Type of Material:||Princeton University Senior Theses|
|Appears in Collections:||Computer Science, 1988-2016|
Files in This Item:
|Altschuler_Jason_thesis.pdf||361.82 kB||Adobe PDF||Request a copy|
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.