مقاله Regret bounded by gradual variation for online convex optimization : تی پی بین

خلاصه مقاله

Recently, it has been shown that the regret of the Follow the Regularized Leader (FTRL) algorithm for online linear optimization can be bounded by the total variation of the cost vectors rather than the number of rounds. In this paper, we extend this result to general online convex optimization. In particular, this resolves an open problem that has been posed in a number of recent papers. We first analyze the limitations of the FTRL algorithm as proposed by Hazan and Kale (in Machine Learning 80(2–3), 165–188, 2010) when applied to online convex optimization, and extend the definition of variation to a gradual variation which is shown to be a lower bound of the total variation. We then present two novel algorithms that bound the regret by the gradual variation of cost functions. Unlike previous approaches that maintain a single sequence of solutions, the proposed algorithms maintain two sequences of solutions that make it possible to achieve a variation-based regret bound for online convex optimization.To establish the main results, we discuss a lower bound for FTRL that maintains only one sequence of solutions, and a necessary condition on smoothness of the cost functions for obtaining a gradual variation bound. We extend the main results three-fold: (i) we present a general method to obtain a gradual variation bound measured by general norm; (ii) we extend algorithms to a class of online non-smooth optimization with gradual variation bound; and (iii) we develop a deterministic algorithm for online bandit optimization in multipoint bandit setting.

نویسندگان

Tianbao Yang [ NEC Laboratories America, Cupertino, USA ]

Mehrdad Mahdavi [ Department of Computer Science and Engineering, Michigan State University, East Lansing, USA ]

Rong Jin [ Department of Computer Science and Engineering, Michigan State University, East Lansing, USA ]

Shenghuo Zhu [ NEC Laboratories America, Cupertino, USA ]

کلمات کلیدی

Online convex optimization Regret bound Gradual variation Bandit

آدرس این مقاله

آدرس مستقیم دسترسی به این مقاله

مشخصات کنفرانس

مشاهده مقالات

Machine Learning 2013

Machine Learning is an international forum for research on computational approaches to learning. The journal publishes articles reporting substantive results on a wide range of learning methods applied to a variety of learning problems. The journal features papers that describe research on problems and methods, applications research, and issues of research methodology. Papers making claims about learning problems or methods provide solid support via empirical studies, theoretical analysis, or comparison to psychological phenomena. Applications papers show how to apply learning methods to solve important applications problems. Research methodology papers improve how machine learning research is conducted. All papers describe the supporting evidence in ways that can be verified or replicated by other researchers. The papers also detail the learning component clearly and discuss assumptions regarding knowledge representation and the performance task.

حوزه های تحت پوشش : Artificial Intelligence, Control, Robotics, Mechatronics, Computing Methodologies,Simulation and Modeling