Exact Algorithms for Isotonic Regression and Related

International Meeting on High-Dimensional Data-Driven Science 2015

Yu, Yao-Liang^1 ; Xing, Eric P.^1

Machine Learning Department, Carnegie Mellon University, Pittsburgh

PA

15213, United States^1

关键词: Algorithm for solving;    Correctness conditions;    Isotonic regression;    Nonconvex functions;    Order restriction;    Proximity operator;    Regularization function;    Statistical estimation;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/699/1/012016/pdf
DOI  :  10.1088/1742-6596/699/1/012016

来源: IOP

【 摘 要 】

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.