Projection Free Rank-Drop Steps
This addresses efficiency issues in large-scale optimization for machine learning and data analysis by reducing computational costs, though it is incremental as it builds on existing Frank-Wolfe methods.
The paper tackles the problem of high rank intermediate iterates in the Frank-Wolfe algorithm for nuclear norm constrained problems, which are expensive in time and space, by proposing a rank-drop method that generates descent steps to reduce rank and maintain low-rank solutions, resulting in greatly reduced rank compared to original Frank-Wolfe or its variants.
The Frank-Wolfe (FW) algorithm has been widely used in solving nuclear norm constrained problems, since it does not require projections. However, FW often yields high rank intermediate iterates, which can be very expensive in time and space costs for large problems. To address this issue, we propose a rank-drop method for nuclear norm constrained problems. The goal is to generate descent steps that lead to rank decreases, maintaining low-rank solutions throughout the algorithm. Moreover, the optimization problems are constrained to ensure that the rank-drop step is also feasible and can be readily incorporated into a projection-free minimization method, e.g., Frank-Wolfe. We demonstrate that by incorporating rank-drop steps into the Frank-Wolfe algorithm, the rank of the solution is greatly reduced compared to the original Frank-Wolfe or its common variants.