Fast and Flexible ADMM Algorithms for Trend Filtering

This article presents a fast and robust algorithm for trend filtering, a recently developed nonparametric regression tool. It has been shown that, for estimating functions whose derivatives are of bounded variation, trend filtering achieves the minimax optimal error rate, while other popular methods like smoothing splines and kernels do not. Standing in the way of a more widespread practical adoption, however, is a lack of scalable and numerically stable algorithms for fitting trend filtering estimates. This article presents a highly efficient, specialized alternating direction method of multipliers (ADMM) routine for trend filtering. Our algorithm is competitive with the specialized interior point methods that are currently in use, and yet is far more numerically robust. Furthermore, the proposed ADMM implementation is very simple, and, importantly, it is flexible enough to extend to many interesting related problems, such as sparse trend filtering and isotonic trend filtering. Software for our method is freely available, in both the C and R languages.

本文提出一种面向趋势滤波（trend filtering）的快速鲁棒算法，该方法是近年发展起来的非参数回归工具。已有研究证实，针对导数具有有界变差的函数开展估计时，趋势滤波可达到极小极大最优误差率，而平滑样条、核方法等主流方法则无法实现该性能。然而，制约趋势滤波技术更广泛实际应用的核心瓶颈在于，缺乏可扩展且数值稳定的算法以拟合趋势滤波的估计结果。本文提出一种针对趋势滤波的高效专用交替方向乘子法（alternating direction method of multipliers, ADMM）求解例程。所提算法与当前主流的专用内点法性能相当，且具备更优异的数值鲁棒性。此外，该ADMM实现方案极为简洁，尤为重要的是，其灵活性足以拓展至诸多颇具研究价值的相关问题，例如稀疏趋势滤波与保序趋势滤波。本文方法的配套软件已以C语言与R语言两种形式免费开源发布。