Primal-Dual Active-Set Methods for Isotonic Regression and Trend Filtering
This provides a more efficient and scalable method for isotonic regression and trend filtering, which are important for calibration in supervised learning, though it appears incremental as it builds on existing active-set approaches.
The authors tackled the problem of performing large-scale isotonic regression by proposing a primal-dual active-set algorithm that can be parallelized and warm-started, making it suitable for online settings. Their algorithm achieves O(n) work complexity and is shown in experiments to often be faster than the state-of-the-art Pool Adjacent Violators algorithm.
Isotonic regression (IR) is a non-parametric calibration method used in supervised learning. For performing large-scale IR, we propose a primal-dual active-set (PDAS) algorithm which, in contrast to the state-of-the-art Pool Adjacent Violators (PAV) algorithm, can be parallized and is easily warm-started thus well-suited in the online settings. We prove that, like the PAV algorithm, our PDAS algorithm for IR is convergent and has a work complexity of O(n), though our numerical experiments suggest that our PDAS algorithm is often faster than PAV. In addition, we propose PDAS variants (with safeguarding to ensure convergence) for solving related trend filtering (TF) problems, providing the results of experiments to illustrate their effectiveness.