2017
NIPS
NeurIPS 2017
Random Permutation Online Isotonic Regression
Abstract
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.
🌉
Interdisciplinary Bridge
— Machine Learning and Mathematics & Optimization
📈
Trend Setter
— Regression
🧭
Keyword Pioneer
— random permutation
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio
Authors
Topics
Machine Learning > Core Methods > Regression
Machine Learning > Optimization & Theory > Learning Theory
Mathematics & Optimization > Optimization > Online Algorithms
Machine Learning > Learning Types > Online Learning
Machine Learning > Optimization & Theory > Online Algorithms
Machine Learning > Learning Types > Regression