# Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization

arXiv: https://arxiv.org/abs/2607.24518 · HTML: https://mlsanity.com/paper/2607.24518/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 71 references that are in the map.
- First posted on arXiv 27 Jul 2026.

## Builds on (most cited first, 12 of 12)

- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Variants of RMSProp and Adagrad with Logarithmic Regret Bounds](https://mlsanity.com/paper/1706.05507/) (2017)
- [Disentangling Adaptive Gradient Methods from Learning Rates](https://mlsanity.com/paper/2002.11803/) (2020)
- [Decompositions of Dependence for High-Dimensional Extremes](https://mlsanity.com/paper/1612.07190/) (2016)
- [Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Method](https://mlsanity.com/paper/2206.06900/) (2022)
- [MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization](https://mlsanity.com/paper/1609.09154/) (2016)
- [Randomized Algorithms for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2402.08134/) (2024)
- [SymNMF-Net for The Symmetric NMF Problem](https://mlsanity.com/paper/2205.13214/) (2022)

## Abstract (arXiv)

Symmetric non-negative matrix factorization (SymNMF) recovers latent group structure from a dependence matrix, but its dense, quadratic-memory objective has confined prior work to moderate sizes. We present a large-scale GPU study of seven algorithm families (over 30 configurations) on absolute Pearson correlation and tail pairwise dependence matrices from Extreme Value Theory, two proxies for empirical risk-factor estimation on large portfolios. A trace-identity reformulation eliminates all n × n intermediates, so a single GPU reaches n ≈ 105 and multi-node distribution scales to n = 106 and beyond. Under a two-phase protocol, eleven methods converge at moderate scale; six remain efficient enough at n = 105 (five AdaGrad-family plus ADMM), and five AdaGrad-family methods still converge at n = 106: AdaGrad, RMSprop, and three we introduce (Piecewise AdaGrad, Row-Stochastic SVRG, Block-SVRG AdaptGrow). At n = 106 the fastest solver tracks the matrix spectrum: Block-SVRG AdaptGrow wins on the flat, ill-conditioned tail-dependence spectrum, where its lower per-iteration cost decides a long factorization, and full-batch AdaGrad wins on the dominant-low-rank correlation spectrum, where the run is short. We also benchmark spherical K-means as a hard-label baseline: cheaper when angular cluster structure is present, yet provably degenerate once the matrix collapses toward a single common factor, where the soft factorization remains necessary.