Trend Filtering on Graphs

Yu-Xiang Wang, James Sharpnack, Alex Smola, Ryan Tibshirani
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:1042-1050, 2015.

Abstract

We introduce a family of adaptive estimators on graphs, based on penalizing the \ell_1 norm of discrete graph differences. This generalizes the idea of trend filtering (Kim et al., 2009, Tibshirani, 2014) used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filtering exhibits a level of local adaptivity unmatched by the usual \ell_2-based graph smoothers. It is also defined by a convex minimization problem that is readily solved (e.g., by fast ADMM or Newton algorithms). We demonstrate the merits of graph trend filtering through examples and theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-wang15d, title = {{Trend Filtering on Graphs}}, author = {Wang, Yu-Xiang and Sharpnack, James and Smola, Alex and Tibshirani, Ryan}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {1042--1050}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/wang15d.pdf}, url = {https://proceedings.mlr.press/v38/wang15d.html}, abstract = {We introduce a family of adaptive estimators on graphs, based on penalizing the \ell_1 norm of discrete graph differences. This generalizes the idea of trend filtering (Kim et al., 2009, Tibshirani, 2014) used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filtering exhibits a level of local adaptivity unmatched by the usual \ell_2-based graph smoothers. It is also defined by a convex minimization problem that is readily solved (e.g., by fast ADMM or Newton algorithms). We demonstrate the merits of graph trend filtering through examples and theory.} }
Endnote
%0 Conference Paper %T Trend Filtering on Graphs %A Yu-Xiang Wang %A James Sharpnack %A Alex Smola %A Ryan Tibshirani %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-wang15d %I PMLR %P 1042--1050 %U https://proceedings.mlr.press/v38/wang15d.html %V 38 %X We introduce a family of adaptive estimators on graphs, based on penalizing the \ell_1 norm of discrete graph differences. This generalizes the idea of trend filtering (Kim et al., 2009, Tibshirani, 2014) used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filtering exhibits a level of local adaptivity unmatched by the usual \ell_2-based graph smoothers. It is also defined by a convex minimization problem that is readily solved (e.g., by fast ADMM or Newton algorithms). We demonstrate the merits of graph trend filtering through examples and theory.
RIS
TY - CPAPER TI - Trend Filtering on Graphs AU - Yu-Xiang Wang AU - James Sharpnack AU - Alex Smola AU - Ryan Tibshirani BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-wang15d PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 1042 EP - 1050 L1 - http://proceedings.mlr.press/v38/wang15d.pdf UR - https://proceedings.mlr.press/v38/wang15d.html AB - We introduce a family of adaptive estimators on graphs, based on penalizing the \ell_1 norm of discrete graph differences. This generalizes the idea of trend filtering (Kim et al., 2009, Tibshirani, 2014) used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filtering exhibits a level of local adaptivity unmatched by the usual \ell_2-based graph smoothers. It is also defined by a convex minimization problem that is readily solved (e.g., by fast ADMM or Newton algorithms). We demonstrate the merits of graph trend filtering through examples and theory. ER -
APA
Wang, Y., Sharpnack, J., Smola, A. & Tibshirani, R.. (2015). Trend Filtering on Graphs. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:1042-1050 Available from https://proceedings.mlr.press/v38/wang15d.html.

Related Material