Abstract
Block coordinate descent (BCD) methods are prevalent in large scale optimization problems due to the low memory and computational costs per iteration, the predisposition to parallelization, and the ability to exploit the structure of the problem. The theoretical and practical performance of BCD relies heavily on the rules defining the choice of the blocks to be updated at each iteration. We propose a new deterministic BCD framework that allows for very flexible updates, while guaranteeing state-of-the-art convergence guarantees on non-smooth nonconvex optimization problems. While encompassing several update rules from the literature, this framework allows for priority on updates of particular blocks and correlations in the block selection between iterations, which is not permitted under the classical convergent stochastic framework. This flexibility is leveraged in the context of multilevel optimization algorithms and, in particular, in multilevel image restoration problems, where the efficiency of the approach is illustrated.
Introduction
In large-scale optimization—such as training massive neural networks or restoring high-resolution images—updating every variable simultaneously is often computationally or memory-prohibitive. Block Coordinate Descent (BCD) addresses this by updating only a subset (a "block") of variables at each step. However, existing BCD methods face a significant trade-off. Stochastic rules, while popular, do not easily allow for the prioritization of specific blocks or the use of correlated selection strategies. Conversely, traditional deterministic rules like cyclic updates are often too rigid to exploit problem-specific structures or support efficient parallelization in non-convex settings.
This paper introduces FLEX-BC-PG (Flexible Block-Coordinate Proximal Gradient), a deterministic framework designed for non-smooth and non-convex optimization. FLEX-BC-PG provides the flexibility to prioritize "important" blocks and supports parallel updates, significantly accelerating convergence in structured problems like image restoration.
The FLEX-BC-PG Framework
The core of FLEX-BC-PG lies in its flexible block selection rules. Unlike strict cyclic methods that follow a fixed order (1, 2, 3...), this framework employs an essentially cyclic rule. This requires only that every block is updated at least once within a fixed window of $K$ iterations, allowing for shuffling and prioritizing specific blocks based on their impact on the objective function.
As illustrated in Figure 1, the framework supports both parallel updates and hierarchical structures. This flexibility is crucial for non-convex problems, where convergence is theoretically guaranteed through the Kurdyka-Łojasiewicz (KL) inequality. This mathematical tool ensures that the sequence of iterates converges to a critical point rather than oscillating indefinitely.
Multilevel Optimization and Image Restoration
A major contribution of this work is the formal proof that multilevel optimization—which utilizes a hierarchy of coarse-to-fine approximations—can be viewed as a specific instance of the FLEX-BC-PG framework. The authors show that the "first-order coherence" term used in multilevel methods is mathematically equivalent to a specific block update in their framework.
This bridge is particularly effective in image restoration tasks. Using the classic "Cameraman" image ($1024 \times 1024$) degraded by Gaussian blur and noise, the authors applied a non-convex, non-smooth regularization via a 2-level log-sum-Haar wavelet decomposition. In wavelet-based restoration, "approximation" coefficients (low-frequency parts) are significantly more important for the overall structure than "detail" coefficients. FLEX-BC-PG allows researchers to update these high-impact blocks more frequently, leading to faster global progress.
Key Results and Insights
Experimental comparisons against standard Forward-Backward (FB) and traditional BCD (Cyclic and Random) methods revealed several key insights:
- Significant Speedup: FLEX-BC-PG and its "Alternating" variant (which alternates between coarse updates and full updates) significantly outperformed all baselines in terms of CPU time.
- Faster Convergence: The flexible variants reached lower objective function values much faster than the standard FB algorithm.
- The Power of Priority: The authors observed that the partial gradient associated with approximation coefficients is much higher initially. By prioritizing these blocks, the algorithm reduces the most significant errors first, validating the efficiency of structured deterministic rules over random selection.
Conclusion and Future Work
FLEX-BC-PG offers a unified theory for BCD and multilevel optimization in non-convex settings, providing a rigorous convergence theory where proofs were previously scarce. While the framework requires tuning hyperparameters like the window size $K$, its ability to exploit problem structure through deterministic, flexible rules provides a powerful alternative to standard stochastic methods.
Future research may expand the application of this theory to other non-convex domains, such as specific layers in deep neural networks or matrix factorization. Additionally, while this work focuses on deterministic rules, the authors suggest that a hybrid "flexible-stochastic" approach might be a fruitful direction for further exploration.
Summary updated