Nataly Brukhim will present her FPO "New Directions in Boosting" on Friday,
June 28, 2024 at 11:00 AM in CS 402 .
Location: CS 402
The members of Nataly's committee are as follows:
Examiners: Elad Hazan (Adviser), Ryan Adams, Robert Schapire (Microsoft
Research)
Readers: Sanjeev Arora, Shay Moran (Technion)
A copy of her thesis is available upon request. Please email
gradinfo(a)cs.princeton.edu if you would like a copy of the thesis.
Everyone is invited to attend her talk.
Abstract follows below:
Boosting is a fundamental methodology in machine learning used to boost the
accuracy of weak learning models, transforming them into strong learners.
This thesis establishes new directions in boosting theory, presenting
algorithms and their analyses for complex learning scenarios that go beyond
the realm of traditional classification. These developments extend the
benefits of the boosting methodology to modern and challenging learning
settings.
This thesis is divided into two main parts: Multiclass Boosting and Boosting
for Sequential Decision Making. Part I explores the generalization of
classical boosting theory to the multiclass setting, specifically focusing
on the challenging case of an extremely large label space. Initially, we
present a hardness result that illustrates that boosting does not easily
from the binary to the multiclass case. Subsequently, within the broader
context of multiclass learning, we develop novel algorithmic strategies
which provide a complete characterization of multiclass learnability,
resolving a longstanding open problem. Finally, leveraging these novel
ideas, we also introduce new boosting techniques that circumvent the
aforementioned hardness barrier, leading to efficient multiclass boosting
methods.
In Part II, we develop boosting frameworks for sequential decision making.
Sequential decision making tasks such as control, bandit and reinforcement
learning, can be thought of as challenging generalized variants of
statistical learning, which take into account interactive interactions with
the environment. As boosting was developed for static datasets, extending
the technique to these tasks poses significant challenges, and requires
grappling with the effects of feedback and systems that change over time. In
this line of work we develop boosting frameworks in various sequential
decision making tasks. Namely, the online agnostic learning setting, online
control of dynamical systems, the bandit setting in online learning, and
reinforcement learning.
