TY - JOUR
T1 - Online optimization for max-norm regularization
AU - Shen, Jie
AU - Xu, Huan
AU - Li, Ping
N1 - Publisher Copyright:
© 2017, The Author(s).
PY - 2017/3/1
Y1 - 2017/3/1
N2 - The 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 bottleneck. In this paper, hence, we propose an online algorithm that is scalable to large problems. In particular, 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 reformulate 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 size 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 robustness of our algorithm compared to the widely used nuclear norm solvers.
AB - The 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 bottleneck. In this paper, hence, we propose an online algorithm that is scalable to large problems. In particular, 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 reformulate 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 size 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 robustness of our algorithm compared to the widely used nuclear norm solvers.
KW - Low-rank matrix
KW - Matrix factorization
KW - Max-norm
KW - Stochastic optimization
UR - http://www.scopus.com/inward/record.url?scp=85011915337&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85011915337&partnerID=8YFLogxK
U2 - 10.1007/s10994-017-5628-6
DO - 10.1007/s10994-017-5628-6
M3 - Article
AN - SCOPUS:85011915337
SN - 0885-6125
VL - 106
SP - 419
EP - 457
JO - Machine Learning
JF - Machine Learning
IS - 3
ER -