Random Permutation Online Isotonic Regression
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.
I am not an expert in online learning, and did not read the proofs in the appendix. My
overall impression of the paper is positive, but I am not able to judge the importance of
the results or novelty of the analysis techniques. My somewhat indifferent score is more a
reflection of this than the quality of the paper.
Summary: The authors study isotonic regression in an online setting, where an adversary
initially chooses the dataset but the examples are shown in random order. Regret is
measured against the best isotonic function for the data set. 
The main contribution of the paper seems to be in Section 4, i.e a class of "forward
algorithms" which encompass several well known methods, achieve sqrt(T) regret. The authors
also prove a bunch of complementary results such as lower bounds and results for different
settings and loss functions.
Can the authors provide additional motivation for studying the random permutation model?
I don't find the practical motivation in lines 46-47 particularly convincing. It might
help to elaborate on what is difficult/interesting for the learner this setting and what
makes the analysis different from existing work (e.g. [14]). 
Section 3: How do Theorems 3.1 and 3.2 fit into the story of the paper? Are they simply
some complementary results or are they integral to the results in Section 4?
- The estimator in (3) doesn't seem computationally feasible. Footnote 2 states that the
  result holds in expectation if you sample a single data and permutation but this is
  likely to have high variance. Can you comment on how the variance decreases when you
  sample multiple data points and multiple permutations? 
Clarity: Despite my relative inexperience in the field, I was able to follow most of the
details in the paper. That said, I felt the presentation was math driven and could be
toned down in certain areas, e.g. lines 149-157, 242-250 
 
While there seem to a some gaps in the results, the authors have been fairly thorough in
exploring several avenues (e.g. sections 4.3-4.6). The paper makes several interesting
contributions that could be useful for this line of research. 
----------------------------------------------------
Post rebuttal: I have read the authors' rebuttal and am convinced by their case for the setting. I have upgraded my score.