Fast Block Coordinate Descent for Non-Convex Group Regularizations

Yasutoshi Ida, Sekitoshi Kanai, Atsutoshi KumagaiAISTATS 2023 · OpenReview

Abstract

Non-convex sparse regularizations with group structures are useful tools for selecting important feature groups. For optimization with these regularizations, block coordinate descent (BCD) is a standard approach. However, BCD faces scalability issues with massive group counts. This paper introduces AccelGSCAD, an accelerated BCD method that utilizes gradual parameter addition and a novel snapshot bounding technique to significantly reduce computational overhead without compromising accuracy.

Introduction

In high-dimensional data analysis, such as bioinformatics and causal inference, selecting significant groups of features is a critical task. Non-convex regularizers like Group SCAD and Group MCP are often preferred over simpler methods like Group Lasso because they reduce the estimation bias inherent in convex penalties.

Block Coordinate Descent (BCD) is the standard optimization algorithm for these problems, iteratively updating each group of parameters. However, BCD performance degrades significantly as the number of groups increases. While existing "pruning" techniques attempt to skip updates for groups likely to remain at zero, they typically compute a "safety bound" for every group in every iteration. This overhead often becomes a new bottleneck, making accelerated versions slower than the original algorithm in many practical scenarios.

The AccelGSCAD Method

AccelGSCAD addresses these bottlenecks through two primary innovations: Gradual Parameter Addition and Snapshot Bounding.

The algorithm treats optimization as a sequence of growing subproblems by categorizing feature groups into three subsets based on their likelihood of being shrunk to zero:

  1. Non-shrink subset (N): Groups likely to contain significant, non-zero values.
  2. Small-shrink subset (S): Groups that may be important but require regularization.
  3. Large-shrink subset (L): Groups likely to be zero or near-zero.
Comparison of the proposed AccelGSCAD method and previous BCD methods. AccelGSCAD uses gradual parameter addition and reduces the frequency of bound computations.

Instead of checking every group constantly, AccelGSCAD starts by optimizing only the $N$ subset. Once converged, it progressively adds the $S$ and $L$ subsets. This "working set" strategy focuses computational resources on the most relevant parameters. Furthermore, "Snapshot Bounding" replaces the per-iteration bound calculation with a periodic approach. Bounds are only recalculated when it is time to expand the active subset, drastically reducing redundant computations by a factor of $10^4$ to $10^5$.

Experimental Evaluation

The method was evaluated on five real-world datasets: eunite2001 (electricity load forecasting) and four drug design datasets (qsbralks, qsfrdhla, qsbr_rw1, triazines). Second-degree polynomial kernels were used to generate group structures, resulting in up to 1,770 groups and over 10,000 features.

Results and Discussion

AccelGSCAD demonstrated significant performance gains over both the original BCD and the previous state-of-the-art, FastGSCAD.

Performance comparison (percentage of time) across various datasets for $\lambda = \lambda' / 10^4$. AccelGSCAD consistently outperforms the original BCD and FastGSCAD.

Key findings include:

  • Speedup: AccelGSCAD achieved up to a 68x speedup over standard BCD and was up to 4x faster than FastGSCAD.
  • Efficiency: The frequency of bound computations was reduced by several orders of magnitude. Total inner-loop updates were reduced to approximately 10% of those required by previous methods.
  • Accuracy: The method reached identical or slightly better objective values compared to baselines, ensuring that speed does not come at the cost of precision.
  • Robustness: Unlike traditional pruning methods that struggle with less sparse solutions, AccelGSCAD maintains its advantage even in denser settings due to its minimal overhead.

Conclusion

AccelGSCAD provides a highly efficient framework for non-convex group sparse optimization. By prioritizing important features and eliminating the "bound bottleneck," it enables the application of sophisticated regularizers to much larger datasets. Future work includes extending the method to overlapping group structures and automating the selection of the snapshot interval hyperparameter $m$.

Summary updated

Abstract

Non-convex sparse regularizations with group structures are useful tools for selecting important feature groups. For optimization with these regularizations, block coordinate descent (BCD) is a sta...
BibTeX
@inproceedings{ida2023fast,
  author = {Yasutoshi Ida and Sekitoshi Kanai and Atsutoshi Kumagai},
  title = {{Fast Block Coordinate Descent for Non-Convex Group Regularizations}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=j014BaSH1MM},
}

Loading related content...

Figure