Research map / Learning theory and algorithms / Matrix and tensor methods

Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization

ICML 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Structured low-rank learning

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves that projected gradient descent on a nonconvex low-rank matrix factorization of pairwise comparison data (Plackett-Luce-style link) converges exponentially from a warm start, with sample complexity near-optimal in n, using matrix Bernstein concentration.

Problem

Learning user-item latent features from sparse pairwise comparison data via nonconvex matrix factorization lacks recovery guarantees; prior theory only covered convex formulations that are computationally infeasible at scale.

Approach

Adapts matrix-completion analysis (symmetric regularized factorization, incoherence-projected gradient descent) to comparison data by treating each sample as a user with an item pair, and proves strong-convexity-like and smoothness properties via matrix Bernstein concentration over sampling matrices.

Key results

• Theorem gives exponential convergence rate (1 - alpha*eta/4)^t for the distance Delta(Z^t) under a sample size m >= 10^7 (mu r kappa/tau)^2 n log(8n/delta) and warm start within ball of radius tau/50.
• Simulations on synthetic data with (n1,n2)=(200,300) and (2000,3000), r=3, show linear convergence even from initializations without warm start or projection.
• Empirical constants are much less conservative than theory: the dataset-size threshold c0(mu r kappa)^2 n log(n/delta) with c0 = 1/4 or 1/2 matches observed convergence.

Measured effects reported in the paper

Surprising findings

• Simulations show warm start and projection steps are not needed in practice, though theory requires them.
• Empirical performance exceeds theoretical predictions, with theoretical constants being conservative.

Limitations

• Analysis assumes noiseless comparisons (expected outcomes instead of binary choices).
• Requires a warm start within a neighborhood of the ground truth; no global convergence from random initialization.
• Theoretical constants are large and conservative.

Experimental setup

Metrics: normalized Frobenius error of Delta(Z^t)/sqrt(n1 n2)

Builds on: matrix completion via nonconvex factorization (Sun & Luo style analysis) Plackett-Luce choice model Negahban & Wainwright-style matrix completion concentration

Closest papers by meaning

• Rethinking Neural vs. Matrix-Factorization Collaborative Filtering: the Theoretical Perspectives (ICML 2021 · similarity 0.88)
• Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation (NeurIPS 2017 · similarity 0.88)
• Preference Diffusion for Recommendation (ICLR 2025 · similarity 0.88)
• A Geometric Approach to Personalized Recommendation with Set-Theoretic Constraints Using Box Embeddings (ICML 2025 · similarity 0.87)
• Learning-Efficient Yet Generalizable Collaborative Filtering for Item Recommendation (ICML 2024 · similarity 0.87)
• Fading to Grow: Growing Preference Ratios via Preference Fading Discrete Diffusion for Recommendation (NeurIPS 2025 · similarity 0.87)