Variable Clustering via Distributionally Robust Nodewise Regression

Conference: ICML 2026
arXiv: 2212.07944
Code: https://github.com/xuxiao2695/dro-subspace-clustering
Area: Optimization / Variable Clustering
Keywords: Variable clustering, subspace clustering, nodewise regression, distributionally robust optimization, uncertainty quantification

TL;DR

A distributionally robust optimization framework is utilized to transform the parameter tuning problem of nodewise regression into a convex optimization problem with spectral norm regularization—achieving a parameter-free clustering method that significantly outperforms Lasso sparse clustering on simulated, facial, and financial data.

Background & Motivation

Background: Nodewise regression is a classic tool for subspace clustering, generating a similarity matrix by regressing each variable against all others, followed by spectral clustering to recover variable clusters. Existing methods primarily employ \(L_1\)-regularized Sparse Subspace Clustering (SSC) or nuclear norm-regularized Low-Rank Representation (LRR).

Limitations of Prior Work: SSC faces three main issues—(1) tuning the parameter \(\lambda_i\) is difficult as it depends on unknown power noise variance; (2) pursuing coefficient sparsity is unnatural, as the true affinity matrix is often dense when subspaces are non-orthogonal or intra-cluster variables are strongly correlated; (3) recovery is difficult for strongly correlated variables.

Key Challenge: Existing regularization strategies either over-sparsify (disrupting true associations) or rely on prior parameters (high tuning cost), making it difficult to balance data-driven, interpretable, and computationally efficient approaches.

Goal: Reformulate the nodewise regression problem from the perspective of Distributionally Robust Optimization (DRO) to naturally derive the spectral norm regularization term while providing a data-driven method for parameter selection.

Core Idea: Frame the nodewise regression problem as a DRO problem maximized within an uncertainty set \(\mathcal{U}_\delta(\mathbb{P}_n)\), where the uncertainty radius \(\delta\) is defined by the Wasserstein distance. After convex relaxation, this is equivalent to regularizing the spectral norm of \((I-B)\).

Method

Overall Architecture

Under a multi-factor block model, each variable \(X_i = (F_G^{z(i)})^\top \beta_i + U_i\). Standard nodewise regression solves \(\min_B \|X - XB\|_F^2, \text{s.t.} \text{diag}(B)=0\). This paper improves it to a distributionally robust version—\(\min_B \sup_{\mathcal{D}_c(\mathbb{P}, \mathbb{P}_n) \le \delta} \mathbb{E}_\mathbb{P}[\|X - B^\top X\|_2^2]\), where \(\mathcal{D}_c\) is the Wasserstein-2 distance and \(\delta\) is the uncertainty radius.

Key Designs

1. DRO Transformation to Spectral Norm Regularization:

   • Function: Relaxes the infinite-dimensional DRO problem into a finite-dimensional convex optimization.
   • Mechanism: Theorem 3.1 proves \(\frac{1}{2}f(B) \le \text{DRO objective} \le f(B)\), where \(f(B) = (\frac{1}{\sqrt{n}}\|X-XB\|_F + \sqrt{\delta}\|I-B\|_2)^2\). The spectral norm \(\|I-B\|_2\) acts as a robustness regulator, constraining model sensitivity to data perturbations.
   • Design Motivation: Distributional uncertainty within a Wasserstein ball naturally yields a spectral norm penalty, which aligns better with subspace structures than \(L_1\) sparsification (allowing dense combinations rather than requiring absolute sparsity).

2. Data-driven Parameter Selection:

   • Function: Automatically determines the uncertainty radius \(\delta\) without manual tuning.
   • Mechanism: Derived based on the confidence level that \(Z = (I-B)^{-1}U\) satisfies constraints, or via parametric bootstrap estimation of quantiles. With confidence \(1-\alpha = 0.95\), \(M=1000\) samples generate the distribution of \(Z\), and the \((1-\alpha)\) quantile is calculated as \(\delta\).
   • Design Motivation: Parameter selection depends on data scale and noise levels; automation avoids the computational overhead of cross-validation.

3. Efficient ADMM Algorithm:

   • Function: Solves high-dimensional convex optimization problems, accelerating by over 80% compared to general convex solvers.
   • Mechanism: Reformulates the primal problem into constrained form \(B_1 + B_2 = I\), decomposing it into two subproblems—the \(B_1\) update remains a Frobenius norm with quadratic penalty solved via first-order optimization; the \(B_2\) update introduces Lemma 3.2 (automatically zeroing out smaller singular values via SVD). Each iteration requires only one full SVD.
   • Design Motivation: Utilizes spectral operation structures to avoid the lengthy process of variable-wise iterative tuning for \(\lambda_i\).

Key Experimental Results

Main Results (Simulated Data)

Method	Mean AMI	Std Dev	Description
DRO	0.92	0.02	Proposed method, spectral norm regularization
Lasso	0.83	0.04	SSC baseline, \(L_1\) regularization
MFC	0.43	-	Multi-factor model, underfitting
k-medoids	0.33	-	Centroid-based method
ACC	0.15	-	Assumes single factor, inconsistent with multi-factor

Dataset	500 dims, 25 clusters, 250 samples	AMI Difference
No global factor	DRO=0.92, Lasso=0.83	\(\Delta=0.09\)
Global factor \(\beta_H^2=0.5\)	DRO=0.88, Lasso=0.78	\(\Delta=0.10\)
Global factor \(\beta_H^2=0.9\)	DRO=0.82, Lasso=0.65	\(\Delta=0.17\)

Facial Clustering (Extended Yale B)

Metric	DRO	Lasso	SSC-EnSC	MFC
Mean AMI	0.580	0.403	0.218	0.172
Median AMI	0.584	0.422	0.220	0.171

Financial Data Experiment

S&P 500 stock portfolio construction—the DRO-ACC combination method (first clustering into \(K_1=6\) clusters via DRO, then splitting into \(K_2=6\) sub-clusters via ACC, totaling 36 stocks) significantly improves annual excess returns and Sharpe ratios compared to Lasso-ACC and LRR baselines (backtest period 2001-2020).

Key Findings

• As the global factor increases, the AMI of all methods decreases, but DRO maintains its lead.
• Parameter selection is highly insensitive to the confidence level \(1-\alpha\) (AMI stabilizes at 0.91-0.93 when \(\alpha \in [0.001, 0.2]\)).

Highlights & Insights

• Clever DRO-Spectral Norm Equivalence: Transforms Wasserstein uncertainty sets into operator norm constraints, unifying the role of regularization from the perspective of "robustness constraints."
• Adaptive Parameters: \(\delta\) is automatically determined via bootstrap quantiles, offering a transparent mechanism that is highly insensitive to confidence levels.
• General Framework for Subspace Cluster Discovery: Not limited to sparse recovery; extendable to any convex regularization terms.
• Feasibility for Large-scale Scenarios: The ADMM algorithm exploits SVD structural properties, achieving >80% speedup over general solvers.

Limitations & Future Work

• Number of clusters \(K\) must be known a priori.
• Performance may degrade when subspace dimensions differ significantly.
• Performance decay with global factors—AMI drops for all methods.
• Lack of comparison with other DRO methods (e.g., using KL divergence as an uncertainty measure).

Related Work & Insights

• vs SSC: SSC pursues coefficient sparsity and relies on hand-tuned \(\lambda_i\); this work uses spectral norm constraints that allow dense combinations with adaptive parameters.
• vs LRR: LRR imposes a nuclear norm penalty on all \(B\); this work uses the spectral norm to control only the maximum eigenvalue of \((I-B)\).
• vs MFC: Also based on a multi-factor block model, but MFC uses eigenvalue decomposition, which is numerically unstable when \(d\) is large and \(n\) is small.
• Generalization to Graphical Models: This DRO framework can potentially be transferred to causal structure recovery.

Rating

• Novelty: ⭐⭐⭐⭐⭐ First application of DRO theory in nodewise regression; Wasserstein-spectral norm equivalence is novel.
• Experimental Thoroughness: ⭐⭐⭐⭐ Simulation + Vision + Finance + Sensitivity analysis; lacks empirical validation of theoretical convergence rates.
• Writing Quality: ⭐⭐⭐⭐⭐ Clear logical chain; rigorous theorem statements.
• Value: ⭐⭐⭐⭐ Provides principled improvements for variable clustering; financial portfolio application carries industry significance.

Related Papers

• [NeurIPS 2025] Distributionally Robust Feature Selection
• [ICLR 2026] Distributionally Robust Classification for Multi-Source Unsupervised Domain Adaptation
• [ICML 2026] Markov Chain Monte Carlo without Evaluating the Target: An Auxiliary Variable Approach
• [ICML 2026] Estimating Correlation Clustering Cost in Node-Arrival Stream
• [ICML 2026] Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering