Abstract
We consider the minimization of a smooth loss with trace-norm regularization, which is a natural objective in multi-class and multi-task learning. Even though the problem is convex, existing approaches often struggle with scalability due to the computational cost of singular value decompositions (SVDs) or convergence issues with non-convex variational bounds. We introduce Rank-1 Descent (R1D), a novel algorithm that solves trace-norm regularized optimization problems by "lifting" them into an infinite-dimensional space. By treating every possible rank-one matrix as a potential coordinate, we transform a non-smooth matrix problem into a smooth one solvable via coordinate descent, significantly outperforming standard SVD-based methods in speed and scalability.
Introduction
In modern machine learning, models are frequently represented as matrices—for instance, in multi-class classification where each column corresponds to a weight vector for a specific class, or in multi-task learning. To prevent overfitting and enhance interpretability, trace-norm regularization (the nuclear norm) is often employed to encourage low-rank solutions. While the resulting optimization problem is convex, it remains computationally challenging at scale.
Existing methods typically encounter two primary hurdles:
- The SVD Bottleneck: Proximal gradient descent methods (like Prox++) require a full SVD at every iteration, which is computationally prohibitive for large-scale matrices.
- Non-convexity Issues: Variational bounds methods lack guarantees for convergence to a global optimum.
This paper proposes a method to bring the efficiency of coordinate descent—which has been highly successful for $\ell_1$ (Lasso) optimization—to matrix-based problems.
Methodology: Infinite-Dimensional Lifting
The core innovation of this work is a mathematical "lifting" trick that transforms the problem space.
1. Infinite-Dimensional Representation
The authors define an overcomplete, uncountable basis consisting of all possible normalized rank-one matrices ($uv^\top$). The target matrix $W$ is represented as a weighted sum of these rank-one "atoms." This process "lifts" the problem from a finite-dimensional matrix space into an infinite-dimensional space of weights ($\theta$).
2. Smooth Reformulation and Rank-One Descent (R1D)
In this lifted space, the non-smooth trace-norm objective is reformulated as a smooth objective subject to a simple non-negativity constraint. Instead of a full SVD, the R1D algorithm identifies the "steepest" coordinate to update, which corresponds to finding the top singular-vector pair of the gradient. This operation is significantly faster than a full SVD.
3. Continuation Strategy (ContR1D)
To accelerate convergence, the authors implement a "warm-start" strategy called ContR1D (C-R1D). This approach solves the problem across a sequence of decreasing regularization strengths ($\lambda$), effectively following a regularization path.
Experimental Evaluation
The performance of R1D was evaluated on several benchmarks, including synthetic data for multi-class logistic regression, conjoint analysis for user preferences, and a subset of ImageNet for large-scale classification.
Key Insights
- Matrix Lasso: R1D functions as a "Lasso for matrices," picking one rank-one component at a time and maintaining a low-rank factorization throughout.
- Steepest Descent: The steepest direction in the infinite-dimensional space is the top singular vector pair of the gradient, bridging coordinate descent and power-method iterations.
- The "Staircase" Phenomenon: Optimization plots for R1D often exhibit a "staircase" pattern, resulting from alternating between adding new rank-one components and optimizing existing weights.
Results
The experimental results highlight the efficiency of the proposed method, particularly in terms of wall-clock time. While proximal methods like Prox++ may require fewer iterations to reach a certain precision, each iteration is far more costly than those of R1D.
On high-correlation synthetic data, ContR1D outperformed Prox++ in terms of CPU time. On ImageNet and Conjoint (II) datasets, R1D reached lower test errors faster. Notably, early iterations of R1D produce very low-rank solutions that often generalize better than the final converged optimum.
Conclusion and Future Work
While R1D has a theoretically slower convergence rate ($O(1/\epsilon^2)$) compared to accelerated proximal methods ($O(1/\sqrt{\epsilon})$), its drastically lower per-iteration cost makes it faster in practice for reaching useful precision levels. The "lifting" framework presented here could potentially be extended to other structured regularizations beyond the trace norm.
Summary updated