A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening
In the 1-dimensional multiple changepoint detection problem, we derive a new fast error rate for the fused lasso estimator, under the assumption that the mean vector has a sparse number of changepoints. This rate is seen to be suboptimal (compared to the minimax rate) by only a factor of log log n. Our proof technique is centered around a novel construction that we call a lower interpolant. We extend our results to misspecified models and exponential family distributions. We also describe the implications of our error analysis for the approximate screening of changepoints.
The authors study the problem of multiple change point detection and provide provide bounds for the fused-lasso estimator. The problem of change point detection is well studied in the statistics literature and the authors provide good references. 
The paper is well written and flows well. As claimed by the authors, one of the major contribution of this paper is in the technique of the proof and, unfortunately, the authors had to put it in the appendix to fit the NIPS page limits. I can not think of a way to fit that in the main section without a major rewrite. In its current form, the appendix is longer than the main paper.
A recent independent development, Guntuboyina et al. (2017), provide the bounds for the lasso estimator. The authors claim that their method of proof is of independent interest as that generalizes to other related problems. It is not clear why the methods of this generalizes but that of Guntuboyina et al. (2017) does not. I would have loved to see discussions on how theorem 3.1 compares to the main results in Guntuboyina et al. (2017) which seem to be stronger.
A comment on inequality (7): This seems to follow directly from the definition of \hat\theta unless I am missing something. Isn’t \hat\theta defined to be the parameter that minimizes 
1/2 ||y-\theta||_2^2 + \lambda ||D\theta||_1