Fast, Provable Algorithms for Isotonic Regression in all p -norms *
Given a directed acyclic graph G, and a set of values y on the vertices, the Isotonic Regression of y is a vector x that respects the partial order described by G, and minimizes x − y , for a specified norm. This paper gives improved algorithms for computing the Isotonic Regression for all weighted p -norms with rigorous performance guarantees. Our algorithms are quite practical, and variants of them can be implemented to run fast in practice.
The problemThe paper studies the Isotonic Regression in $\ell_p$-norms, $1\leq p \leq \infty$. Given a DAG $G(V,E)$ and observations $y\in \bR^{|V|}$, and a weight vector $w$, the isotonic regression is the following minimization problem (which is shown in line 053) \begin{eqnarray} \min_x \|x-y\|_{w,p} \mbox{ such that } x_u \leq x_v \mbox{ for all } (u,v)\in E, \end{eqnarray} where $\|\cdot\|_{w,p}$ is the weighed $\ell_p$-norm. The resultsAllowing a small error $\delta$ from the optimal result, a bound of $O(m^{1.5}\log^2 n \log(npw_{max}^p/\delta))$ on the time complexity which holds with high probability for $1\leq p < \infty$ is shown in Theorem~2.1. For $p<\infty$, the time complexities of this paper are compared with that from previous works which require exact solutions in Table 1. For $p=\infty$ and a variant called the Strict Isotonic Regression (which is defined in line 079), upper bounds of the time complexity to compute exact results are shown in Theorems 1.2 and 1.3, respectively. The time complexity bounds shown in the aforementioned theorems improve the previous results, except for an $\ell_1$ bound in two dimensional space ($V \subset \bR^2$). For $\ell_1$-norm, there is an additional constraint on the number of edges $|E|$.The authors transform the original regression problem to an instance which can be solved by an approximate interior point algorithm called \textsc{ApproxIPM}. By showing the efficiency and the accuracy of a critical subroutine of \textsc{ApproxIPM} called \textsc{BlockSolve} which is designed to compute an approximate Hessian inverse, the proposed algorithm achieves a better time complexity for $1\leq p<\infty$. The contribution of this paper is that the authors generalize a result for linear programs in [23] to $\ell_p$ objectives, and they also provide an improved analysis. For the $\ell_\infty$ Isotonic Regression and the Strict Isotonic Regression, the authors reduce the previous problems to Lipschitz Learning problems defined in [29] and apply the algorithms in [29] to compute the solutions.The paper also provides preliminary experiments on the proposed algorithm, which are listed in Table 2. CommentsThe theoretical part of this paper is an incremental work. The main contributions of this work are the reductions of the problems and the design and the analysis of the critical subroutine \textsc{BlockSolve} which is used to compute an approximate Hessian inverse efficiently. Most of the mathematical techniques used in the analysis can be found in convex optimization, interior point method, and the referenced papers mentioned in this work.It is hard to classify this paper as a theoretical work or an experimental work. The experiments shown in Table 2 are preliminary, and there is no comparisons with other state-of-the-art algorithms. On the other hand, the main algorithm and its analysis ideas are not mentioned clearly in the main body of the paper, although they can be found in the supplementary file. The paper might need restructuring for better presentation. Typos and undefined notations- In line 056, it should be $m \geq n-1$ for a connected graph, rather than $n \geq m-1$. - In line 342, the failing probability should be $n^{-3}$, rather than $n^3$. - In line 663, $\textsc{Solve}_{H_F}$ is not defined, thus making the proof of Theorem 2.7 hard to follow. - In line 716, \textsc{Solve} is not defined, thus making the proof of Lemma A.5 hard to follow. - In line 722, there might be an unnecessary z. QualityFor the theory part of this work it is an acceptable paper. The experimental results are not good enough for publish. The entire presentation of the paper (considering only the main body without the supplementary file) falls between a border line paper and a weakly rejection. ClarityThe algorithm and its critical analysis and analyzing idea are missing in the main body of the paper, making readers not easy to grasp a good understanding to this work.  Originality and SignificanceThis is an incremental work on the Isotonic Regression.