2019/02/24 by Ashok Cutkosky, Cutkosky, Ashok
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1902.09013
openalex publication_date 2019/02/24 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
We provide algorithms that guarantee regret RT(u)\≤ O(G\‖u\‖3 +\nG(\‖u\‖+1)\√(T)) or RT(u)\≤ O(G\‖u\‖3T1/3 + GT1/3+\nG\‖u\‖\√(T)) for online convex optimization with G-Lipschitz losses for\nany comparison point u without prior knowledge of either G or \‖u\‖.\nPrevious algorithms dispense with the O(\‖u\‖3) term at the expense of\nknowledge of one or both of these parameters, while a lower bound shows that\nsome additional penalty term over G\‖u\‖\√(T) is necessary. Previous\npenalties were exponential while our bounds are polynomial in all quantities.\nFurther, given a known bound \‖u\‖\≤ D, our same techniques allow us to\ndesign algorithms that adapt optimally to the unknown value of \‖u\‖ without\nrequiring knowledge of G.\n