- Yaoliang Yu, E. Xing. 2016. Exact Algorithms for Isotonic Regression and Related. Abstract: Statistical estimation under order restrictions, also known as isotonic regression, has been extensively studied, with many important practical applications. The same order restrictions also appear implicitly in sparse estimation, where intuitively we should shrink variables starting from smaller ones. Inspired by the achievements in both fields, we first propose the GPAV algorithm for solving problems with order restrictions. We study its theoretical properties, present an online linear time implementation, and prove a converse theorem to pinpoint the exact correctness condition. When specialized to the proximity operator of an order restricted regularization function, GPAV recovers, as special cases, many existing algorithms, and also leads to many new extensions that even involve nonconvex functions.
