Abstract
Projection-free methods, such as the Frank-Wolfe algorithm, are essential for high-dimensional optimization where projecting onto feasible sets is computationally prohibitive. However, extending these methods to product domains using block-coordinate strategies has faced a significant "theory gap," particularly regarding convergence rates for non-convex objectives. This paper presents a new block-coordinate framework that utilizes a "Short Step Chain" (SSC) procedure to overcome these limitations. We demonstrate that this framework achieves local linear convergence and provides finite-time active set identification. Empirical results on non-convex Multi-Standard Quadratic Programming (Multi-StQP) problems show that the proposed methods significantly outperform existing block-coordinate Frank-Wolfe variants in terms of both speed and gradient efficiency.
Introduction
In modern large-scale optimization, the complexity of the feasible set often dictates the choice of algorithm. While gradient descent is a standard tool, its reliance on projections can become a bottleneck when the feasible set is defined by complex constraints, such as nuclear-norm balls or flow polytopes. Projection-free methods, specifically the Frank-Wolfe (FW) family, offer an alternative by replacing the projection step with a linear minimization oracle (LMO), which is often much cheaper to compute.
When the feasible set possesses a product structure—common in multi-agent systems, matrix completion, and network flows—it is natural to employ block-coordinate strategies. These strategies update only a subset of variables at each iteration, reducing the per-iteration cost. Despite their practical appeal, block-coordinate FW variants have historically lacked robust theoretical guarantees for linear convergence, especially in non-convex settings. The primary obstacle has been the occurrence of "bad steps"—iterations that satisfy feasibility but provide negligible progress toward the optimum.
The Short Step Chain Framework
To bridge this gap, we introduce a general block-coordinate framework centered on the Short Step Chain (SSC) procedure. The core innovation of the SSC is its departure from the traditional single-step FW update.
The SSC Procedure
Instead of performing a single step and immediately recomputing the gradient, the SSC executes a sequence of "short steps" while recycling the same gradient information. The procedure continues until it either achieves a predefined progress threshold or encounters a boundary of the feasible set. This mechanism effectively "cleans up" the small, unproductive steps that typically stall convergence proofs, ensuring that every macro-iteration results in significant objective reduction.
Block Selection and Directions
The framework is designed for flexibility, supporting three primary block selection strategies:
- Parallel (Jacobi-like): Updates all blocks simultaneously, making it highly suitable for distributed and multi-core environments.
- Gauss-Southwell (Greedy): Selects the block that exhibits the greatest violation of optimality conditions, prioritizing the most impactful updates.
- Random Sampling: Selects blocks stochastically, which is often the most scalable approach for extremely high-dimensional "big data" problems.
Furthermore, the framework integrates advanced FW variants, including Away-step (AFW), Pairwise (PFW), and In-face (FDFW) directions. These variants are critical for preventing the "zig-zagging" behavior that often plagues the original FW algorithm as it approaches the boundary of the feasible set.
Theoretical Contributions
The introduction of the SSC allows for a rigorous convergence analysis that was previously elusive.
Local Linear Convergence
We prove that the proposed algorithm achieves a local linear convergence rate under the Kurdyka-Łojasiewicz (KL) property. This is a significant advancement for non-convex optimization, as it provides a theoretical guarantee that the algorithm will efficiently converge to a local stationary point even in complex landscapes.
Active Set Identification
A key feature of many sparse optimization problems is that the optimal solution lies on a low-dimensional face of the feasible set. We provide a proof that our framework identifies this "active set" (the support of the optimal solution) in a finite number of iterations. Once the active set is identified, the effective dimensionality of the problem is reduced, leading to accelerated convergence in the final stages of optimization.
Experimental Results
We evaluated the framework using Multi-Standard Quadratic Programming (Multi-StQP), a challenging non-convex benchmark defined over a product of simplices. The objective matrices were specifically designed to yield sparse solutions that do not necessarily coincide with the vertices of the simplices, creating a difficult scenario for standard FW methods.
In tests involving up to 62,500 variables (where the number of blocks $m$ and block dimension $l$ reached 250), our SSC-based methods (specifically PAFW+SSC and BCAFW+SSC) demonstrated superior performance:
- Computational Efficiency: The new methods reached target optimality gaps orders of magnitude faster than standard Block-Coordinate Frank-Wolfe (BCFW).
- Gradient Economy: By recycling gradients within the SSC, the framework significantly reduced the total number of gradient calls required, which is typically the most expensive part of the optimization process.
- Global Optimization: When used as local solvers within a "Monotonic Basin Hopping" meta-heuristic, our methods consistently located better global minima compared to traditional alternatives.
Conclusion and Future Directions
This work provides a robust theoretical and practical foundation for block-coordinate projection-free optimization. By addressing the "bad step" problem through the Short Step Chain, we enable linear convergence and active set identification in non-convex settings.
Future research will focus on relaxing the technical assumptions required for the random selection strategy and extending the active set identification results beyond products of simplices to more general atomic sets, such as the nuclear-norm ball. Additionally, developing adaptive methods to estimate the Lipschitz constant $L$ will enhance the algorithm's usability for practitioners.
Summary updated