The $k$-Cap Process on Geometric Random Graphs

Mirabel E. Reid, Santosh S. Vempala
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3469-3509, 2023.

Abstract

The $k$-cap (or $k$-winners-take-all) process on a graph works as follows: in each iteration, a subset of $k$ vertices of the graph are identified as winners; the next round winners are the vertices that have the highest total degree from the current winners, with ties broken randomly. This natural process is a simple model of firing activity and inhibition in the brain and has been found to have desirable robustness properties as an activation function. We study its convergence on directed geometric random graphs in any constant dimension, revealing rather surprising behavior, with the support of the current active set converging to lie in a small ball and the active set itself remaining essentially random within that.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-reid23a, title = {The $k$-Cap Process on Geometric Random Graphs}, author = {Reid, Mirabel E. and Vempala, Santosh S.}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {3469--3509}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/reid23a/reid23a.pdf}, url = {https://proceedings.mlr.press/v195/reid23a.html}, abstract = {The $k$-cap (or $k$-winners-take-all) process on a graph works as follows: in each iteration, a subset of $k$ vertices of the graph are identified as winners; the next round winners are the vertices that have the highest total degree from the current winners, with ties broken randomly. This natural process is a simple model of firing activity and inhibition in the brain and has been found to have desirable robustness properties as an activation function. We study its convergence on directed geometric random graphs in any constant dimension, revealing rather surprising behavior, with the support of the current active set converging to lie in a small ball and the active set itself remaining essentially random within that. } }
Endnote
%0 Conference Paper %T The $k$-Cap Process on Geometric Random Graphs %A Mirabel E. Reid %A Santosh S. Vempala %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-reid23a %I PMLR %P 3469--3509 %U https://proceedings.mlr.press/v195/reid23a.html %V 195 %X The $k$-cap (or $k$-winners-take-all) process on a graph works as follows: in each iteration, a subset of $k$ vertices of the graph are identified as winners; the next round winners are the vertices that have the highest total degree from the current winners, with ties broken randomly. This natural process is a simple model of firing activity and inhibition in the brain and has been found to have desirable robustness properties as an activation function. We study its convergence on directed geometric random graphs in any constant dimension, revealing rather surprising behavior, with the support of the current active set converging to lie in a small ball and the active set itself remaining essentially random within that.
APA
Reid, M.E. & Vempala, S.S.. (2023). The $k$-Cap Process on Geometric Random Graphs. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:3469-3509 Available from https://proceedings.mlr.press/v195/reid23a.html.

Related Material