A Unified Framework for Stochastic Matrix Factorization via Variance Reduction

2017/05/19 by Renbo Zhao, William B. Haskell, Zhao, Renbo +3
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1705.06884

openalex publication_date 2017/05/19 · openalex created_date 2017/06/05 · openalex updated_date 2026/07/28

Abstract

We propose a unified framework to speed up the existing stochastic matrix factorization (SMF) algorithms via variance reduction. Our framework is general and it subsumes several well-known SMF formulations in the literature. We perform a non-asymptotic convergence analysis of our framework and derive computational and sample complexities for our algorithm to converge to an ε-stationary point in expectation. In addition, extensive experiments for a wide class of SMF formulations demonstrate that our framework consistently yields faster convergence and a more accurate output dictionary vis-à-vis state-of-the-art frameworks.

Citations

• Stochastic Approximation: A Dynamical Systems Viewpoint
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Matrix Factorization Techniques for Recommender Systems
• Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly\n Convex Composite Objectives

Related

• Stochastic variance reduced multiplicative update for nonnegative matrix factorization
• Variance Reduction for Matrix Computations with Applications to Gaussian Processes
• A Column-Wise Update Algorithm for Sparse Stochastic Matrix Factorization
• Stochastic Matrix Factorization
• Randomized methods for matrix computations