图 书 馆
图上的Lipschitz学习算法Algorithms for Lipschitz Learning on Graphs |
|
| 课程网址: | https://videolectures.net/videos/colt2015_sachdeva_lipschitz_lear... |
| 主讲教师: | Sushant Sachdeva |
| 开课单位: | 信息不详。欢迎您在右侧留言补充。 |
| 开课时间: | 2015-08-20 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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 $O (m n)$. The latter algorithm has variants that seem to run much faster in practice. These extensions are particulary amenable to regularization: we can perform $l_{0}$ regularization on the given values in polynomial time and $l_{1}$ regularization on the graph edge weights in time $\widetilde{O} (m^{3/2})$. Our algorithms naturally extend to directed graphs. |
| 关 键 词: | 回归问题：期望时间：正则化 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2025-04-20：zsp |
| 最后编审: | 2025-04-20：zsp |
| 阅读次数: | 5 |