Timezone: »
Poster
Learning with Partially Absorbing Random Walks
Xiao-Ming Wu · Zhenguo Li · Shih-Fu Chang · John Wright · Anthony Man-Cho So
Tue Dec 04 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
We propose a novel stochastic process that is with probability $\alpha_i$ being absorbed at current state $i$, and with probability $1-\alpha_i$ follows a random edge out of it. We analyze its properties and show its potential for exploring graph structures. We prove that under proper absorption rates, a random walk starting from a set $\mathcal{S}$ of low conductance will be mostly absorbed in $\mathcal{S}$. Moreover, the absorption probabilities vary slowly inside $\mathcal{S}$, while dropping sharply outside $\mathcal{S}$, thus implementing the desirable cluster assumption for graph-based learning. Remarkably, the partially absorbing process unifies many popular models arising in a variety of contexts, provides new insights into them, and makes it possible for transferring findings from one paradigm to another. Simulation results demonstrate its promising applications in graph-based learning.
Author Information
Xiao-Ming Wu (Columbia University)
Zhenguo Li (Huawei Noah's Ark Lab, Hong Kong)
Shih-Fu Chang (Columbia University)
John Wright (Columbia University)
Anthony Man-Cho So (CUHK)
More from the Same Authors
-
2022 : Nonsmooth Composite Nonconvex-Concave Minimax Optimization »
Jiajin Li · Linglingzhi Zhu · Anthony Man-Cho So -
2022 : Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization »
Kaiwen Zhou · Anthony Man-Cho So · James Cheng -
2023 : Testing Approximate Stationarity Concepts for Piecewise Smooth Functions »
Lai Tian · Anthony Man-Cho So -
2023 Poster: ReSync: Riemannian Subgradient-based Robust Rotation Synchronization »
Huikang Liu · Xiao Li · Anthony Man-Cho So -
2023 Poster: Outlier-Robust Gromov-Wasserstein for Graph Data »
Lemin Kong · Jiajin Li · Jianheng Tang · Anthony Man-Cho So -
2023 Poster: Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization »
Taoli Zheng · Linglingzhi Zhu · Anthony Man-Cho So · Jose Blanchet · Jiajin Li -
2023 Poster: LogSpecT: Feasible Graph Learning Model from Stationary Signals with Recovery Guarantees »
Shangyuan LIU · Linglingzhi Zhu · Anthony Man-Cho So -
2021 Poster: Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery »
Junhui Zhang · Jingkai Yan · John Wright -
2021 Poster: Deep Networks Provably Classify Data on Curves »
Tingran Wang · Sam Buchanan · Dar Gilboa · John Wright -
2020 Poster: Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates »
Kaiwen Zhou · Anthony Man-Cho So · James Cheng -
2020 Poster: Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine »
Jiajin Li · Caihua Chen · Anthony Man-Cho So -
2019 Poster: A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression »
Jiajin Li · SEN HUANG · Anthony Man-Cho So -
2014 Poster: Discrete Graph Hashing »
Wei Liu · Cun Mu · Sanjiv Kumar · Shih-Fu Chang -
2014 Poster: Finding a sparse vector in a subspace: Linear sparsity using alternating directions »
Qing Qu · Ju Sun · John Wright -
2014 Spotlight: Discrete Graph Hashing »
Wei Liu · Cun Mu · Sanjiv Kumar · Shih-Fu Chang -
2013 Poster: Analyzing the Harmonic Structure in Graph-Based Learning »
Xiao-Ming Wu · Zhenguo Li · Shih-Fu Chang -
2013 Poster: On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization »
Ke Hou · Zirui Zhou · Anthony Man-Cho So · Zhi-Quan Luo -
2012 Workshop: Analysis Operator Learning vs. Dictionary Learning: Fraternal Twins in Sparse Modeling »
Martin Kleinsteuber · Francis Bach · Remi Gribonval · John Wright · Simon Hawe -
2009 Poster: Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming »
Xiao-Ming Wu · Anthony Man-Cho So · Zhenguo Li · Shuo-Yen Robert Li -
2009 Spotlight: Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming »
Xiao-Ming Wu · Anthony Man-Cho So · Zhenguo Li · Shuo-Yen Robert Li