TL;DR
This paper provides a rigorous theoretical foundation for the "subgradient" algorithms used in matrix factorization and factorization machines. The authors prove that as long as these models are slightly overparameterized (the latent dimension is large enough), the Clarke subdifferential chain rule holds as an equality everywhere, ensuring that standard optimization techniques are mathematically well-behaved.
What Problem Does This Paper Address?
In deep learning and recommender systems, we often optimize nonsmooth functions (like those using ReLU activations or absolute loss) using "subgradient" methods. Mathematically, these methods rely on the chain rule to calculate gradients through layers of a model.
However, there is a catch: for the specific type of nonsmoothness used in these fields (Clarke subdifferentials), the chain rule is usually only an inclusion ($\subseteq$), not an equality ($=$). If the equality fails, the "subgradient" calculated by software like PyTorch or TensorFlow might not actually be a valid subgradient of the total loss function. This makes it difficult to prove that an algorithm will actually converge to a meaningful point.
While previous work addressed this for linear structures (like standard ReLU networks), this paper tackles multilinear structures found in Matrix Factorization (MF) and Factorization Machines (FM). These are trickier because their "slope" (Jacobian) can vanish entirely at the origin, breaking standard calculus rules.
Methods
The authors employ tools from nonsmooth analysis and variational geometry. Their primary weapon is the local surjection property (also known as "openness").
- Local Surjection as a Bridge: They show that if a mapping (like the one that multiplies two matrices together) is "locally surjective," it guarantees that the subdifferential chain rule holds as an equality.
- Dimension Analysis: They derive specific thresholds for the latent dimension ($d$) relative to the problem size ($m, n$). They prove that if $d$ is large enough, the mapping is locally surjective everywhere.
- Constructive Counterexamples: To show their bounds are "tight," the authors construct clever examples where the chain rule explicitly fails when the latent dimension is just one unit below their suggested threshold.
- Peeling Arguments: For Factorization Machines, which have a more complex recursive structure, they use a "peeling" induction strategy to prove surjectivity.
Datasets
As this is a theoretical mathematics paper focusing on proving fundamental properties of functions, no empirical datasets (such as MovieLens or MNIST) were used. The "data" consists of mathematical proofs and symbolic constructions.
Key Insights and Ideas
- The "Triviality" of Stationarity: One of the most striking observations is that for these multilinear problems, the origin is always a stationary point if the loss function is locally Lipschitz. This means that simply "finding a stationary point" is a very weak goal for an optimizer, as you could just return all zeros and technically be "done."
- Overparameterization is a Feature, Not a Bug: In many contexts, overparameterization is seen as a risk for overfitting. Here, it is shown to be a mathematical necessity for "smooth" behavior of the subdifferential. It ensures the model has enough "directions" to move in so that the chain rule doesn't collapse.
- The Multilinear Hurdle: The authors highlight why tensors and neural networks are harder than matrices. In a matrix $X^T Y$, the variables are somewhat independent. In a neural network or a higher-order tensor, the variables become "coordinate dependent," making it much harder to prove that the function can move in any arbitrary direction.
Key Results
- Matrix Factorization (MF): The mapping $H(X, Y) = X^T Y$ is locally surjective at the origin if and only if the latent dimension $d \ge \min\{m, n\}$. To be locally surjective everywhere, the threshold is $d \ge m + n + \min\{m, n\}$.
- Factorization Machines (FM): The FM mapping is locally surjective at the origin if and only if $d \ge d_0 - 1$ (where $d_0$ is the input dimension).
- Chain Rule Validity: Under these dimension conditions, the Clarke subdifferential of the composite loss function is exactly equal to the product of the Jacobian and the subdifferential of the loss. This justifies the use of backpropagation-style algorithms for these models.
- Neural Extensions: The paper successfully extends these results to "Generalized Matrix Factorization," a core component of modern Neural Collaborative Filtering.
Limitations and Future Work
- The Tensor Gap: While the authors provide some results for third-order tensors (CP factorization), the general case remains "mostly open." The coordinate dependence in tensors makes proving local surjection significantly more difficult.
- Neural MF Failure: The authors show that for the "overall" Neural Matrix Factorization (which adds a linear neural network component to the MF component), the local surjection property actually fails everywhere if the dimensions are small. This suggests that new, even more sophisticated techniques are needed to analyze the most complex neural architectures.
- Symmetric Case: The current theory doesn't apply to symmetric matrix factorization ($X^T X$). Because $X^T X$ is always non-negative, it can never be "locally surjective" at the origin (you can't move into the negative space), leaving a gap for future researchers to fill.
Summary updated