Projection Free Rank-Drop Steps

Edward Cheung, Yuying LiIJCAI 2017 · DOI

TL;DR

This paper introduces a novel "rank-drop" step for the Frank-Wolfe algorithm, specifically designed for nuclear norm-constrained problems. This method efficiently reduces the rank of intermediate solutions, leading to significantly faster convergence and lower memory requirements compared to existing Frank-Wolfe variants, especially for large-scale matrix completion tasks.

What Problem Does This Paper Address?

Many machine learning problems involve minimizing a function subject to a nuclear norm constraint, which is a convex relaxation for rank-constrained optimization. The standard Frank-Wolfe (FW) algorithm is attractive because it avoids computationally expensive projection steps. However, a major drawback of FW is that it often produces intermediate solutions with very high ranks. This high rank can be a significant bottleneck for large problems, as it requires storing and manipulating large matrices, making gradient computations and overall convergence prohibitively slow and memory-intensive. Existing methods to address this either require specific knowledge of the objective function or still involve computationally demanding steps. This paper aims to bridge this gap by developing a projection-free method that actively reduces the rank of the solution at each step.

Methods

The core contribution is the introduction of a "rank-drop" step. This step is formulated as a new optimization problem that seeks a rank-one matrix that, when added to the current iterate, reduces the matrix's rank by one while minimizing the objective function. The authors carefully consider two cases:

  • Interior Rank-Drop: When the current iterate is well within the nuclear norm ball, a specific optimization problem is formulated to find the best rank-drop direction. This problem leverages the first-order approximation of the objective and ensures the resulting iterate remains feasible.
  • Exterior Rank-Drop: When the iterate is close to the boundary of the nuclear norm ball, a different formulation is used, often involving a generalized eigenvalue problem, to find a rank-drop step that guarantees feasibility and rank reduction.

These rank-drop steps are designed to be seamlessly integrated into the projection-free Frank-Wolfe framework. The algorithm, termed Rank-Drop Frank-Wolfe (RDFW), selectively uses rank-drop steps when beneficial, falling back to standard Frank-Wolfe steps otherwise.

Datasets

The paper evaluates its method on matrix completion tasks using the following datasets:

  • MovieLens 100k
  • MovieLens 1M
  • MovieLens 10M
  • MovieLens 20M

These datasets are standard benchmarks for matrix completion and vary in size (number of users, movies, and ratings).

Key Insights and Ideas

  • Active Rank Reduction: The most significant insight is that actively seeking rank-reducing steps within a projection-free framework is not only possible but also highly effective. This contrasts with standard FW, which implicitly increases rank.
  • Feasibility Guarantees: The method carefully formulates rank-drop steps to ensure that the resulting iterate remains within the feasible region (the nuclear norm ball), a crucial aspect for convergence.
  • Efficiency for Large Matrices: By maintaining low-rank intermediate solutions, the method drastically reduces computational cost and memory footprint, making it practical for problems where storing the full matrix is infeasible.
  • Generality: The rank-drop framework is designed to work with general objective functions $f(\cdot)$, unlike some other methods that require specific properties of $f(\cdot)$ or its derivatives.

Key Results

The experimental results demonstrate that the proposed Rank-Drop Frank-Wolfe (RDFW) method significantly outperforms standard Frank-Wolfe and its Away-Step variant in terms of both the final rank of the solution and the computational time. For instance, on the ML-20M dataset, RDFW achieved a maximum rank of 202 compared to 471 for FW and 477 for Away-Step FW, with a drastically reduced time of 29,102 seconds versus 117,535 seconds for FW. While the ActiveALT solver (a state-of-the-art nuclear norm solver) shows competitive performance, RDFW offers the advantage of not requiring knowledge of the Hessian or specific objective function structures.

Limitations and Future Work

  • Computational Complexity: While RDFW is more efficient than standard FW, the interior rank-drop step still involves an eigen-decomposition of an $r \times r$ matrix (where $r$ is the current rank), which can be computationally intensive if the rank becomes large. The paper notes that the complexity per iteration is $O(r^3 + r^2h \min\{m, n\})$.
  • Rank-Drop Step Selection: The paper mentions that it is rare for the algorithm to choose a rank-drop step two iterations in a row, and the algorithm is designed to only generate the rank-drop direction when the previous step was a standard FW step. This heuristic aims to avoid unnecessary computations.
  • Future Work: The authors suggest that the proposed formulation can be deployed in other projection-free minimization methods. Further exploration of rank-drop steps for other types of matrix norms or constraints could also be a direction.

Summary updated

BibTeX
@inproceedings{cheung2017projection,
  author = {Edward Cheung and Yuying Li},
  title = {{Projection Free Rank-Drop Steps}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/213},
}
Figure