Algorithms for Lipschitz Learning on Graphs
Abstract
We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large $p$ of $p$-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time $\widetilde{O} (m n)$. The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform $l_{0}$-regularization on the given values in polynomial time and $l_{1}$-regularization on the initial function values and on graph edge weights in time $\widetilde{O} (m^{3/2})$.
Cite
Text
Kyng et al. "Algorithms for Lipschitz Learning on Graphs." Annual Conference on Computational Learning Theory, 2015.Markdown
[Kyng et al. "Algorithms for Lipschitz Learning on Graphs." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/kyng2015colt-algorithms/)BibTeX
@inproceedings{kyng2015colt-algorithms,
title = {{Algorithms for Lipschitz Learning on Graphs}},
author = {Kyng, Rasmus and Rao, Anup and Sachdeva, Sushant and Spielman, Daniel A.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {1190-1223},
url = {https://mlanthology.org/colt/2015/kyng2015colt-algorithms/}
}