Abstract: The Frank-Wolfe method and its extensions are well-suited for delivering solutions with desirable structural properties, such as sparsity or low-rank structure. We introduce a new variant of the Frank-Wolfe method that combines Frank-Wolfe steps and steepest descent steps, as well as a novel modification of the "Frank-Wolfe gap" to measure convergence in the non-convex case. We further extend this method to incorporate in-face directions for preserving structured solutions as well as block coordinate steps, and we demonstrate computational guarantees in terms of the modified Frank-Wolfe gap for all of these variants. We are particularly motivated by the application of this methodology to the training of neural networks with sparse properties, and we apply our block coordinate method to the problem of $\ell_1$ regularized neural network training. We present the results of several numerical experiments on both artificial and real datasets demonstrating significant improvements of our method in training sparse neural networks.
1. Introduction
Modern machine learning increasingly demands structured models—those exhibiting sparsity or low-rank properties—to facilitate memory efficiency and accelerate inference. While standard approaches often involve post-training pruning or $\ell_1$ regularization via Stochastic Gradient Descent (SGD), these methods do not inherently respect structural constraints during the optimization process. The Frank-Wolfe (FW) algorithm offers a promising alternative by promoting sparsity through updates toward the extreme points of a feasible set. However, extending FW to the non-convex, stochastic, and high-dimensional landscape of deep learning presents significant challenges, including handling mixed variables, defining appropriate convergence metrics, and overcoming slow convergence rates.
2. Methodology: Stochastic Frank-Wolfe Steepest Descent
To address these challenges, we introduce the Stochastic Frank-Wolfe Steepest Descent (FW-SD) method. This hybrid framework combines Frank-Wolfe-style updates for constrained variables (e.g., weights targeted for sparsity) with standard steepest descent steps for unconstrained parameters (e.g., biases).
A core innovation is the incorporation of "in-face" directions, such as away steps, which allow the optimizer to refine solutions within a specific sparsity pattern. This prevents the "zig-zagging" behavior typical of basic FW and preserves structural properties more effectively. Furthermore, we define a novel convergence metric—a modified Frank-Wolfe gap—that accounts for both parameter types. We theoretically demonstrate that this algorithm achieves an $O(1/K)$ convergence rate for the expected squared value of this gap. For practical implementation in neural networks, we also provide a block-coordinate extension that permits layer-wise step sizes and constraints.
3. Experimental Evaluation
We evaluated the proposed methods on several benchmarks:
- MNIST: Utilizing both Multilayer Perceptron (MLP) and Convolutional Neural Network (CNN) architectures.
- CIFAR-10: Using a standard CNN architecture.
- Synthetic Data: Designed to assess the recovery of known "ground truth" sparsity patterns under varying noise levels.
4. Results and Discussion
Our experiments reveal that sparsity can be treated as a dynamic property of the optimization path rather than a post-processing step. A key finding is the remarkable robustness of FW-SD models to hard thresholding. Unlike SGD-trained models, where aggressive pruning typically leads to catastrophic accuracy loss, our method pushes weights toward zero so effectively that they can be removed with minimal impact.
As detailed in Table 1, the SFW-IF (In-Face) variant achieves extreme sparsity. For instance, in the MNIST-MLP task, SFW-IF reduced the second layer's average non-zero edges to just 1.55%, compared to 97.79% for SGD. Crucially, when pruned to the top 5% of weights, the SFW-IF model maintained 96.49% accuracy, whereas the SGD model's performance dropped to 81.12%. In synthetic tests, the in-face directions significantly accelerated the reduction of the modified Frank-Wolfe gap, confirming their practical utility.
5. Conclusion and Future Work
While the FW-SD framework shows great promise for training sparse networks, some limitations remain. The method's performance is sensitive to the Lipschitz constant of the gradient, which currently requires tuning. Additionally, while empirical results with ReLU activations are strong, a theoretical gap exists as these functions are non-smooth. Future research will focus on scaling this methodology to larger architectures like Transformers and deep ResNets, where managing the overhead of tracking "faces" will be a critical consideration.
Summary updated