Timezone: »

 
Poster
Random Permutation Online Isotonic Regression
Wojciech Kotlowski · Wouter Koolen · Alan Malek

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #58
in Posters Wed »

We revisit isotonic regression on linear orders, the problem of fitting monotonic functions to best explain the data, in an online setting. It was previously shown that online isotonic regression is unlearnable in a fully adversarial model, which lead to its study in the fixed design model. Here, we instead develop the more practical random permutation model. We show that the regret is bounded above by the excess leave-one-out loss for which we develop efficient algorithms and matching lower bounds. We also analyze the class of simple and popular forward algorithms and recommend where to look for algorithms for online isotonic regression on partial orders.

Keywords: Learning Theory · Online Learning · Regression
[ Paper] 

Author Information

Wojciech Kotlowski (Poznan University of Technology)
Wouter Koolen (Centrum Wiskunde & Informatica, Amsterdam)
Alan Malek (MIT)

More from the Same Authors