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.

本文提出了一种在线算法，通过将最大规范化重构为等效的矩阵分解形式，可以在处理大型数据时保持基础组件的记忆，并对每个样本的基础组件和系数进行交替优化，证明了该算法的解序列渐近地收敛于期望损失函数的稳态点。