# On subdifferential chain rule of matrix factorization and beyond

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 55 references that are in the map.
- First posted on arXiv 7 Oct 2024.

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

- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Neural Factorization Machines for Sparse Predictive Analytics](https://mlsanity.com/paper/1708.05027/) (2017)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Attentional Factorization Machines: Learning the Weight of Feature Interactions via Attention Networks](https://mlsanity.com/paper/1708.04617/) (2017)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [NAIS: Neural Attentive Item Similarity Model for Recommendation](https://mlsanity.com/paper/1809.07053/) (2018)
- [Higher-Order Factorization Machines](https://mlsanity.com/paper/1607.07195/) (2016)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions](https://mlsanity.com/paper/2112.09002/) (2021)
- [Relational Collaborative Filtering:Modeling Multiple Item Relations for Recommendation](https://mlsanity.com/paper/1904.12796/) (2019)
- [The effect of smooth parametrizations on nonconvex optimization landscapes](https://mlsanity.com/paper/2207.03512/) (2022)
- [The Law of Parsimony in Gradient Descent for Learning Deep Linear Networks](https://mlsanity.com/paper/2306.01154/) (2023)
- [Understanding Notions of Stationarity in Non-Smooth Optimization](https://mlsanity.com/paper/2006.14901/) (2020)
- [Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1811.05642/) (2018)
- [Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications](https://mlsanity.com/paper/1708.07850/) (2017)
- [No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzians](https://mlsanity.com/paper/2210.06907/) (2022)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms](https://mlsanity.com/paper/1607.08810/) (2016)
- [Multi-output Polynomial Networks and Factorization Machines](https://mlsanity.com/paper/1705.07603/) (2017)
- [Efficiently testing local optimality and escaping saddles for ReLU networks](https://mlsanity.com/paper/1809.10858/) (2018)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [Factorization Machines with Regularization for Sparse Feature Interactions](https://mlsanity.com/paper/2010.09225/) (2020)
- [Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms](https://mlsanity.com/paper/2302.12261/) (2023)

## Abstract (arXiv)

In this paper, we study equality-type Clarke subdifferential chain rules of matrix factorization and factorization machine. Specifically, we show for these problems that provided the latent dimension is larger than some multiple of the problem size (i.e., slightly overparameterized) and the loss function is locally Lipschitz, the subdifferential chain rules hold everywhere. In addition, we examine the tightness of the analysis through some interesting constructions and make some important observations from the perspective of optimization; e.g., we show that for all this type of problems, computing a stationary point is trivial. Some tensor generalizations and neural extensions are also discussed, albeit they remain mostly open.