YINS Seminar, “Boosting for Online Convex Optimization”

Speaker: Karan Singh
Postdoc, Princeton University

Talk summary: Boosting is a computational framework for compositional learning. There are two traditions to the theory of boosting. First: Classical boosting, arising from theoretical CS, converts weak slightly-better-than-random learners to an accurate one, enhancing the accuracy. Originally designed for the binary classification setting, the literature on boosting was extended to multi-class, multi-label, and ranking-based settings (all examples of linear loss) with specialized constructions in each case. Second: Gradient boosting, on the other hand, aggregates simple (but accurate) learners into a more expressive one; it guarantees competitiveness with the convex hull of the weak hypothesis class.  The main contribution of this work is an efficient algorithm that enhances the accuracy and expressivity of the learning process at the same time, while operating on general convex loss (vs. linear for classical boosting) and any convex decision set. This resultant excess risk (average regret) guarantee unifies and delivers on the twin objectives of classical boosting and gradient boosting. The reduction holds for both the (non-stochastic) online and statistical settings, and is amenable to bandit feedback.  

To participate:

Join from PC, Mac, Linux, iOS or Android: https://yale.zoom.us/j/98411487580
    Or Telephone：203-432-9666 (2-ZOOM if on-campus) or 646 568 7788
    Meeting ID: 984 1148 7580
    International numbers available: https://yale.zoom.us/u/aypRvb6I6

Speaker bio: Karan Singh is a postdoctoral researcher at Microsoft Research in Redmond. He received a PhD in Computer Science, under the supervision of Prof. Elad Hazan, from Princeton University in 2021. His research looks at questions in supervised and interactive learning through the lens of optimization. This has, in recent years, shaped into a quest towards an algorithmic (vs. traditionally, analytic) foundation for control theory, for learning in dynamical systems that do not “forget”, and for provably sound mechanisms of compositional learning.

.