Rethinking Optimization Methods for Hierarchical Feature Selection

Xinyuan Song; Zekun Cai; Liang Zhao

cs.AINov 6, 2026

Rethinking Optimization Methods for Hierarchical Feature Selection

Authors: Xinyuan Song, Zekun Cai, Liang Zhao

Organizations: Emory University, Atlanta, GA, USA · The University of Tokyo, Tokyo, Japan

Abstract

Rare-event forecasting often depends on interpretable conjunctions: a single keyword, location, or temporal cue may be weak, while their joint occurrence can identify a meaningful precursor. Hierarchical-Task Numerical conjunctive feature Learning (HTNL) selects Numerical Conjunctive Features (NCFs) through a structured sparsity objective. However, the resulting optimization problem is challenging, making optimization design critical to its practical performance. We give a unified diagnosis of four HTNL optimization families: original majorization-minimization (MM), variational quadratic form (VQF), alternating direction method of multipliers (ADMM), and weighted group lasso (WGL). Our analysis distinguishes three key factors that jointly determine HTNL optimization behavior. First, VQF and MM are algebraically equivalent under matched variational updates and optimize a squared-penalty formulation. Second, ADMM optimizes the unsquared objective through consensus splitting; we replace its truncated FISTA proximal solver with a scalar bisection update (ADMM-Bisect) for more accurate treatment of near-threshold blocks. Third, WGL targets the same unsquared objective, while all methods face rapidly decaying active-set admission scores. Across two synthetic datasets and 11 civil-unrest and flu-surveillance tasks, VQF achieves the highest mean AUC with the most compact non-collapsing supports. ADMM-Bisect reduces measured runtime, while calibrated WGL avoids the empty-support failures of its original scale. Synthetic results further show how proximal accuracy, pruning, and search budget affect candidate recovery, especially for longer conjunctions. Code will be made publicly available upon publication.

Figures & tables

Figure 1: Main pipeline of HTNL optimization and NCF selection. HTNL constructs conjunction features from $X$ and optimizes the restricted two-level group-lasso problem using MM–VQF, ADMM, or WGL. The resulting coefficients score unseen NCFs by the KKT criterion, admitted candidates expand the working set $U$ , and the process repeats until convergence, producing event predictions and selected NCFs.

Best-of-class variants (post-hoc sweeps)
	Dataset 1		Dataset 2
Method	$\tau=0.20$	$\tau=0.40$	$\tau=0.20$	$\tau=0.40$
HTNL-MM	$0.580\pm 0.201$	$0.592\pm 0.253$	$0.581\pm 0.188$	$0.590\pm 0.246$
HTNL-VQF	$0.580\pm 0.201$	$0.592\pm 0.253$	$0.581\pm 0.188$	$0.590\pm 0.246$
HTNL-ADMM (FISTA, $\rho=10$ )	$0.468\pm 0.133$	$\mathbf{0.674\pm 0.187}$	$0.457\pm 0.147$	$\mathbf{0.674\pm 0.211}$
HTNL-WGL ( $\lambda=100$ )	$0.463\pm 0.336$	$0.463\pm 0.336$	$0.360\pm 0.306$	$0.360\pm 0.306$

Table 1: NCF support-selection F1 on two controlled synthetic datasets. Results are mean

\pm

standard deviation over 20 paired random seeds at active-set thresholds

\tau=0.20

and

0.40

Dataset	$n$	pos%	LogReg	MM/VQF	ADMM-Bisect	WGL( $\lambda=1$ )	$\Delta$ AUC
Flu $\star$	5,096	7.40%	$0.649$	$0.695$	$0.600$	$0.606$	$+0.046$
Ecuador	5,916	0.74%	$0.529$	$0.604$	$0.563$	$0.581$	$+0.075$
El Salvador	8,700	1.26%	$0.477$	$0.572$	$0.559$	$0.555$	$+0.095$
Uruguay	10,788	0.82%	$0.481$	$0.601$	$0.565$	$0.582$	$+0.120$
Venezuela	11,832	0.70%	$0.463$	$0.524$	$0.514$	$0.523$	$+0.061$
Chile	12,876	0.49%	$0.459$	$0.527$	$0.501$	$0.503$	$+0.068$

Table 2: Predictive AUC on 11 real-world datasets using identical train/test splits.

n

and pos% denote the number of training instances and positive-class fraction, respectively.

\Delta

AUC denotes the improvement of VQF over Logistic Regression. The final row reports mean

\pm

standard deviation across datasets.

Panel of Figure 2 — Figure 2: Controlled optimization diagnostics. Left: Bisection improves ADMM F1, while MM and VQF are identical. Right: KKT pruning preserves F1 while reducing runtime.

Figure 3: Synthetic F1 across active-set admission thresholds

\tau_{\mathrm{KKT}}

. Shaded bands show uncertainty across paired random seeds.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

c_{u,g}^{t}=\lambda\sum_{v\in A_{U}(u)}d_{v}\alpha_{v,u}^{t},\qquad u\in U,\ g\in\mathcal{G}.

(B.31)

Appendix

Algorithm 1 Two-Level Group Lasso via Weighted One-Level Group Lasso

$\lambda_{\mathrm{start}}$	$\lambda_{\mathrm{end}}$	Direction	AUC	[email protected]
500	50	high-to-low	0.500	0
50	5	high-to-low	0.572	1
5	0.5	high-to-low	0.540	9
1	1	single	0.581	7
0.1	0.1	single	0.536	13

Appendix

Table 3: Sensitivity of WGL to the regularization scale on Venezuela. “Direction” indicates either high-to-low continuation from

\lambda_{\mathrm{start}}

\lambda_{\mathrm{end}}

or a single fixed-

\lambda

run. “[email protected]” denotes the number of NCFs selected at the active-set threshold

\tau=0.40

Figure 4: Paired-seed F1 comparison between ADMM-Bisect and ADMM-FISTA at

\rho=1

. Each point represents the same random seed evaluated with the two proximal solvers; points above the identity diagonal favor ADMM-Bisect. Under this diagnostic condition, ADMM-Bisect matches or improves ADMM-FISTA on every evaluated seed, showing that the aggregate improvement is consistent across paired runs rather than driven by a small number of seeds.

Method	Jac. vs Orig./VQF	$\boldsymbol{\|\hat{S}\|}$	$\boldsymbol{\Delta}$ AUC
MM/VQF	$1.000$	${\approx}4$ – $5$	$+0.074^{***}$
ADMM-Bisect	$0.277$	${\approx}10$	$+0.034^{*}$
WGL( $\lambda=1$ )	$0.351$	${\approx}10$	$+0.044^{**}$
WGL-Cont (default)	$0.000$	$0$	—

Appendix

Table 4: Selected-support behavior on the LatAm civil-unrest datasets.

|\hat{S}|

denotes the selected set size at

\tau=0.40

, Jaccard similarity is measured against MM/VQF, and

\Delta

AUC is measured against class-weighted Logistic Regression.

Method	Default ( $m_{0}=2$ , add=5)	$m_{0}=3$	$m_{0}=4$	$m_{0}=5$
MM/VQF	$0.590$	$0.686$	$0.686$	$0.686$
ADMM-Bisect	$0.674$	$0.684$	$0.685$	$0.685$

Appendix

Table 5: Active-set sensitivity on the TKDE-faithful synthetic generator (Dataset 2).

m_{0}

denotes the initial active-set size; the default configuration uses

m_{0}=2

and adds five candidates per iteration. Entries report mean F1.

	Orig	VQF	ADMM	WGL-def.	WGL( $\lambda=1$ )
MM	1.000	1.000	$0.277$	$0.045$	$0.351$
VQF	1.000	1.000	$0.277$	$0.045$	$0.351$
ADMM-Bisect	$0.277$	$0.277$	1.000	$0.000$	$0.780$
WGL-Cont (def.)	$0.045$	$0.045$	$0.000$	1.000	$0.000$
WGL( $\lambda=1$ )	$0.351$	$0.351$	$0.780$	$0.000$	1.000

Appendix

Table 6: Mean Jaccard similarity between selected NCF sets across the 11 real-data benchmarks at

\tau=0.40

. MM and VQF have Jaccard similarity

1.000

, consistent with Proposition 3.2 .

Panel of Figure 5 — Figure 5: Selection size and outer active-set iterations across optimization methods. Each point represents one dataset–seed pair. MM/VQF produces more compact selected sets, whereas ADMM-Bisect and WGL( $\lambda=1$ ) retain broader supports. ADMM-Bisect requires more outer iterations but remains computationally efficient in the tested implementation.

Country	$n_{\text{train}}$	pos%	MM/VQF	ADMM-Bisect
Uruguay	10,788	0.8%	13	76
Venezuela	11,832	0.7%	15	62
Paraguay	14,964	1.5%	22	86
Colombia	19,140	0.5%	25	97
Argentina	19,836	0.5%	18	83
Mean	—	—	18.6	80.8

Appendix

Table 7: Selected-support sizes on five civil-unrest datasets.

n_{\mathrm{train}}

and pos% denote the number of training instances and the positive-class fraction, respectively. Support size is measured at

\tau=0.40

. MM and VQF are identical under matched updates and are therefore reported jointly. ADMM-Bisect uses

\rho=1

Figure 6: Predictive AUC across the 11 real-data benchmarks. MM/VQF provides the largest mean improvement over class-weighted Logistic Regression. ADMM-Bisect and WGL(

\lambda=1

) also improve mean AUC but retain broader selected supports, while the default WGL continuation produces empty models on the severely imbalanced civil-unrest datasets.

Panel of Figure 7 — Figure 7: Runtime and predictive performance across the 10 LatAm civil-unrest datasets and the flu dataset. The left panel compares wall-clock time, and the right panel compares per-dataset AUC with class-weighted Logistic Regression.

Figure 8: AUC as a function of the positive-class fraction. The 10 LatAm datasets have positive rates between

0.48\%

and

1.52\%

, whereas the flu dataset has a positive rate of

7.4\%

. Default WGL produces empty supports with AUC

=0.500

on all 10 LatAm datasets, while this failure is not observed on the flu dataset.

Dimension	MM	VQF	ADMM-Bisect	WGL-Cont
Formulation basis	Variational quadratic formulation	Same variational quadratic formulation as MM	ADMM decomposition of the original nonsmooth objective	Reformulation of the outer $\ell_{p}$ hierarchy as weighted group lasso
Inner solver	Weighted ridge subproblem	Same weighted ridge subproblem as MM	L-BFGS for the smooth step plus exact bisection for the nonsmooth proximal step	FISTA for the weighted group-lasso subproblem
Convergence behavior	Linear convergence for the strongly convex ridge subproblem	Same as MM	$O(1/K)$ ADMM residual convergence	$O(1/K^{2})$ convergence within each fixed- $\lambda$ FISTA stage; no recovery guarantee after support collapse
Per-iteration cost	$O(\|U\|\cdot\text{ridge})$	$O(\|U\|\cdot\text{ridge})$	$O(\|U\|\cdot\|D(v)\|\cdot\log(1/\varepsilon))$	$O(\|U\|\cdot G\cdot\text{FISTA})$
Selection regime	Sparse: ${\approx}4$ – $5$ NCFs	Identical to MM	Broad: ${\approx}10$ NCFs	Broad when $\lambda{=}1$ ; collapse under the default continuation schedule
Class-imbalance robustness	Robust in the tested rare-event datasets	Robust in the tested rare-event datasets	Robust in the tested rare-event datasets	Scale-sensitive; the default schedule collapses on all 10 severely imbalanced civil-unrest datasets

Appendix

Table 8: Multi-dimensional comparison of the four HTNL optimization families. “Sparse” denotes the sparse-selection regime (

{\approx}4

–

5

selected NCFs), “broad” denotes the broader-selection regime (

{\approx}10

selected NCFs), and “collapse” denotes an empty or nearly empty selected set. “Ridge” refers to the weighted ridge subproblem obtained after fixing the variational auxiliary variables, and “FISTA” refers to the accelerated proximal-gradient solver used for the weighted group-lasso subproblem. The parameter

\rho\in\mathbb{R}_{+}

is the ADMM augmented-Lagrangian penalty, while the

\lambda

schedule denotes the continuation path used by WGL.

Feature Selection

Feature selection identifies compact, informative variables or input dimensions to improve prediction, efficiency, interpretability, and statistical inference.

See all 210 papers

Random Feature Pruning for Multi-Class Classification
Oct 10, 2026Mohammad Amin Omidi, Babak Seyfe, Shahrokh ValaeeFeature Selection Random Feature Methods
Information Theoretic Learning Systems Laboratory (ITLSL), Department of Electrical Engineering, Shahed University, Tehran, Iran · Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada
Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models
May 22, 2026Hongyi Li, Jun Xu, Hong YanGradient-Boosted Decision Trees Decision Tree Learning
School of Intelligence Science and Engineering, Harbin Institute of Technology, Shenzhen, 518055, China and with the Shenzhen Key Lab for Advanced Motion Control and Modern Automation Equipments, Shenzhen, 518055, China · Department of Electrical Engineering, City University of Hong Kong, Kowloon, Hong Kong
Population-Robust Feature Selection via Generalized Welfare Optimization
Aug 3, 2026Ruiqi Lyu, Alistair Turcan, Bryan WilderDistribution Shift Robustness Social Welfare Maximization
Carnegie Mellon University

Oct 10, 2026J/K move · Enter open · S save

Random Feature Pruning for Multi-Class Classification

Mohammad Amin Omidi, Babak Seyfe, Shahrokh Valaee

Information Theoretic Learning Systems Laboratory (ITLSL), Department of Electrical Engineering, Shahed University, Tehran, Iran · Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada

Feature Selection Random Feature Methods Multiclass Classification Statistical Learning Theory

Open paper AskPDF arXiv

Weighted sums of random kitchen sinks (W-RKS) is a commonly used feature extraction technique for supervised learning tasks. A major drawback of this method is the redundancy and ineffectiveness of many extracted random features. This paper investigates efficient methods for reducing such redundancy in multi-class classification problems. We specifically formulate feature selection as a variant of the sequentially nested model selection problem and introduce the Successive Empirical Excess Risk Difference Maximization (SEED-MAX) algorithm. It recursively computes empirical risks to identify the most parsimonious yet informative set of features. We derive an analytical lower bound for the probability of correct feature selection by the SEED-MAX algorithm. This lower bound on the probability of correct feature selection can be made arbitrarily close to one by increasing the training dataset size. To further enhance the rate of pruning, we evaluate the features retained by SEED-MAX using the Fisher test (F-Test). Empirical evaluations on UCR time-series classification datasets show that the sequential application of SEED-MAX with the Fisher test achieves approximately 92 percent rate of pruning with negligible degradation in classification accuracy. Implementations of the SEED-MAX and SEED-MAX-F-Test methods are available at https://github.com/OmidiAmin/seed-max-ftest.

Abstract

Feature Selection

Explore similar work

Random Feature Pruning for Multi-Class Classification

Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models

Population-Robust Feature Selection via Generalized Welfare Optimization