Projection free methods on product domains

Immanuel M. Bomze, Francesco Rinaldi, Damiano Zeffiro

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

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.
BibTeX
@article{bomze2025projection,
  author = {Immanuel M. Bomze and Francesco Rinaldi and Damiano Zeffiro},
  title = {{Projection free methods on product domains}},
  journal = {Comput. Optim. Appl.},
  year = {2025},
  doi = {10.1007/s10589-024-00585-5},
}
Figure