Online optimization for max-norm regularization

DOI10.1007/S10994-017-5628-6MaRDI QIDQ2014582zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 25 August 2017

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.3190

zbMATH Keywords

matrix factorizationstochastic optimizationlow-rank matrixmax-norm

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Learning and adaptive systems in artificial intelligence (68T05) Online algorithms; streaming algorithms (68W27) Factorization of matrices (15A23)

Abstract: Max-norm regularizer has been extensively studied in the last decade as it promotes an effective low-rank estimation for the underlying data. However, such max-norm regularized problems are typically formulated and solved in a batch manner, which prevents it from processing big data due to possible memory budget. In this paper, hence, we propose an online algorithm that is scalable to large-scale setting. Particularly, we consider the matrix decomposition problem as an example, although a simple variant of the algorithm and analysis can be adapted to other important problems such as matrix completion. The crucial technique in our implementation is to reformulating the max-norm to an equivalent matrix factorization form, where the factors consist of a (possibly overcomplete) basis component and a coefficients one. In this way, we may maintain the basis component in the memory and optimize over it and the coefficients for each sample alternatively. Since the memory footprint of the basis component is independent of the sample size, our algorithm is appealing when manipulating a large collection of samples. We prove that the sequence of the solutions (i.e., the basis component) produced by our algorithm converges to a stationary point of the expected loss function asymptotically. Numerical study demonstrates encouraging results for the efficacy and robustness of our algorithm compared to the widely used nuclear norm solvers.

Recommendations

• Max-norm optimization for robust matrix recovery
• Matrix completion via max-norm constrained optimization
• Online Schatten quasi-norm minimization for robust principal component analysis
• Near-optimal algorithms for online matrix prediction
• Learning Theory

Cites work

• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 1569102 (Why is no real title available?)
• 1-bit matrix completion
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• A Singular Value Thresholding Algorithm for Matrix Completion
• Asymptotic Statistics
• Clustering, Hamming Embedding, Generalized LSH and the Max Norm
• De-noising by soft-thresholding
• Exact matrix completion via convex optimization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Learning Theory
• Local minima and convergence in low-rank semidefinite programming
• Matrix completion via max-norm constrained optimization
• Noisy low-rank matrix completion with general sampling distribution
• Online learning for matrix factorization and sparse coding
• Optimization Problems with Perturbations: A Guided Tour
• Outlier-Robust PCA: The High-Dimensional Case
• Principal component analysis.
• Robust PCA via Outlier Pursuit
• Robust principal component analysis?

Cited in

(9)

• scientific article; zbMATH DE number 5957285 (Why is no real title available?)
• The relaxed online maximum margin algorithm
• Max-norm optimization for robust matrix recovery
• Online regularized matrix regression with streaming data
• Online BP functions maximization
• Near-optimal algorithms for online matrix prediction
• Online manifold regularization by dual ascending procedure
• Online Schatten quasi-norm minimization for robust principal component analysis
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation

This page was built for publication: Online optimization for max-norm regularization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2014582)