Abstract
Projection-free block-coordinate methods avoid high computational cost per iteration and at the same time exploit the particular problem structure of product domains. Frank-Wolfe-like approaches rank among the most popular ones of this type. However, as observed in the literature, there was a gap between the classical Frank-Wolfe theory and the block-coordinate case. Moreover, most of previous research concentrated on convex objectives. This study now deals also with the non-convex case and reduces above-mentioned theory gap, in combining a new, fully developed convergence theory with novel active set identification results which ensure that inherent sparsity of solutions can be exploited in an efficient way. Preliminary numerical experiments seem to justify our approach and also show promising results for obtaining global solutions in the non-convex case.
Introduction
Many modern optimization challenges, ranging from traffic assignment and structural SVMs to dictionary learning, involve feasible sets that are "block separable." In these scenarios, constraints are defined as a product of several smaller, independent sets. While Frank-Wolfe (FW) algorithms have gained popularity due to their "projection-free" nature—avoiding the often prohibitive computational cost of projection steps—their application in a block-coordinate framework has historically faced significant theoretical hurdles.
Prior to this research, a notable "theory gap" existed. While standard FW variants demonstrated linear convergence rates for convex problems, these guarantees were not easily transferable to block-coordinate settings, particularly when dealing with non-convex objectives. Furthermore, the ability to exploit solution sparsity through active set identification within a block-coordinate context remained an unresolved challenge.
Methodology: The Short Step Chain (SSC) Framework
This paper introduces a novel algorithmic framework that integrates block-coordinate selection with a "Short Step Chain" (SSC) procedure. This approach is designed to bridge the gap between theory and practice in non-convex optimization.
The Short Step Chain (SSC) Procedure
The core innovation is the SSC procedure. Rather than performing a single update per iteration, the algorithm executes a sequence of "short steps" within a chosen block. This mechanism allows the algorithm to "recycle" gradient information, facilitating significant progress without the need to recompute the full gradient at every incremental step. This stabilization is crucial for handling the complexities of non-convex landscapes.
Block Selection Strategies
The framework analyzes three distinct strategies for block selection:
- Parallel (Jacobi-like): This strategy updates all blocks simultaneously, making it highly suitable for multi-core and distributed architectures.
- Gauss-Southwell (Greedy): This method selects the block that most significantly violates optimality conditions, focusing effort where it is most needed.
- Random Sampling: Blocks are picked at random, a standard approach for large-scale "big data" applications.
Advanced Frank-Wolfe Directions
To mitigate the "zig-zagging" behavior common in original Frank-Wolfe algorithms near feasible set boundaries, the framework supports advanced directions: Away-step FW (AFW), Pairwise FW (PFW), and "In-face" FW (FDFW). These variants are essential for maintaining convergence speed in constrained environments.
Experimental Evaluation
The proposed methods were evaluated using a structurally complex benchmark: Multi-Standard Quadratic Programming (Multi-StQP). This involves a non-convex quadratic optimization problem defined on a product of multiple simplices. The objective matrices ($Q$) were generated using perturbations of stochastic StQPs and Erdős-Rényi random graphs, ensuring that solutions are sparse but not trivially located at vertices, thus providing a rigorous test for active set identification.
Key Insights and Results
The research yields several critical advancements in the field of projection-free optimization:
- Closing the Theory Gap: The authors provide proof that the block-coordinate framework achieves a local linear convergence rate under the Kurdyka-Lojasiewicz (KL) property. This establishes a rigorous foundation for applying these methods to non-convex problems.
- Active Set Identification: A significant finding is the algorithm's ability to identify the "support" of a solution (the non-zero variables) in a finite number of iterations. This allows for potential computational optimizations, such as "freezing" zero-valued variables.
- Efficiency and Gradient Savings: Numerical tests demonstrate that Parallel Away-step (PAFW + SSC) and Block-Coordinate Away-step (BCAFW + SSC) significantly outperform standard Block-Coordinate Frank-Wolfe (BCFW) baselines, requiring fewer block gradient computations to reach the same optimality gap.
- Global Search Capabilities: When integrated into a "Monotonic Basin Hopping" framework, the new methods showed superior performance in identifying better local and potentially global minima in non-convex landscapes.
Conclusion and Future Directions
While this work represents a major step forward, several avenues for future research remain. The current linear convergence guarantees are local, meaning they apply once the algorithm is sufficiently close to a stationary point; global linear convergence for non-convex cases remains an open problem. Additionally, while active set identification was demonstrated for products of simplices, extending these proofs to other structured sets, such as nuclear-norm balls, is a logical next step. Finally, the SSC procedure's reliance on the Lipschitz constant $L$ suggests that future work could focus on more robust estimation techniques for this parameter in practical applications.
Summary updated