ML Anthology

Fast Proximal Gradient Methods with Node Pruning for Tree-Structured Sparse Regularization

Yasutoshi Ida, Sekitoshi Kanai, Atsutoshi Kumagai, Tomoharu Iwata, Yasuhiro Fujiwara
ECML-PKDD 2025 pp. 113-128
doi:10.1007/978-3-032-06096-9_7 /ecmlpkdd/2025/ida2025ecmlpkdd-fast/

Abstract

Sparse learning with structural information is a fundamental framework for feature selection. Among the various structures, the tree is a basic one that appears in feature vectors, and tree-structured regularization has been utilized to incorporate trees into objective functions. Although proximal gradient methods (PGMs) are usually used for optimization, they incur high computation costs for deep tree structures or large datasets. We propose a fast PGM for tree-structured regularization. Our method safely skips parameter updates of PGMs for pruning unnecessary leaf nodes in the tree. In addition, it prunes unnecessary computations for internal nodes in a hierarchical manner. Our method guarantees the same optimization results and convergence rate as the original method. Furthermore, it can be applied to various PGMs for tree-structured regularization. Experiments show that our method reduces the processing time by up to $56\%$ 56 % from the original method without degrading accuracy.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Ida et al. "Fast Proximal Gradient Methods with Node Pruning for Tree-Structured Sparse Regularization." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025. doi:10.1007/978-3-032-06096-9_7

Markdown

[Ida et al. "Fast Proximal Gradient Methods with Node Pruning for Tree-Structured Sparse Regularization." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025.](https://mlanthology.org/ecmlpkdd/2025/ida2025ecmlpkdd-fast/) doi:10.1007/978-3-032-06096-9_7

BibTeX

@inproceedings{ida2025ecmlpkdd-fast,
  title     = {{Fast Proximal Gradient Methods with Node Pruning for Tree-Structured Sparse Regularization}},
  author    = {Ida, Yasutoshi and Kanai, Sekitoshi and Kumagai, Atsutoshi and Iwata, Tomoharu and Fujiwara, Yasuhiro},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2025},
  pages     = {113-128},
  doi       = {10.1007/978-3-032-06096-9_7},
  url       = {https://mlanthology.org/ecmlpkdd/2025/ida2025ecmlpkdd-fast/}
}