When several organizations hold different columns of the same table, for example a bank holding transaction history and a retailer holding purchase records for the same customers, the data is vertically partitioned. Training a sparse model on such data, meaning a model that uses only a few columns and sets the rest exactly to zero, is expensive. Every optimization step must touch every column under encryption, because no party can see the whole table. This note proposes a way to discard most columns before that encrypted work begins, with a mathematical guarantee that no discarded column would have received a nonzero weight in the exact centralized solution.
The tool comes from centralized statistics. Safe screening rules are cheap tests that prove a feature's Lasso coefficient is zero before the Lasso is solved. Our observation is that these tests split cleanly across organizations. Each test needs only two things. The first is the norm of the feature column, which its owner computes alone. The second is one inner product between that column and a "dual vector," which for the Lasso is a scaled residual and is computable by the party that holds the labels. One encrypted matrix-vector product per point on the regularization path therefore gives every data holder a provably safe keep/discard decision. Because the test is computed against the current model's residual rather than against the raw label, it also catches redundancy that crosses organizational boundaries. Once a feature held by party B is in the model, a near-duplicate held by party A no longer correlates with the residual and is removed. Marginal screening, which scores each feature against the label alone, cannot do this.
Core Claim
Exact, safe screening for the Lasso and sparse logistic regression can be run over vertically partitioned data at the cost of one homomorphically encrypted inner-product pass per regularization value. It reveals only one bit per feature to its owner. Combined with a secure solver restricted to the surviving features, it reproduces the centralized Lasso path exactly while doing most of its encrypted computation on a small fraction of the features. As a byproduct, parties whose features are all screened out leave the protocol entirely, which also reduces the dropout fragility that comes with every party being a hard dependency of the joint model.
What Exists and Where This Sits
Two centralized papers supply the method. Lasso Screening Rules via Dual Polytope Projection bounds the Lasso dual optimum inside a ball, using the fact that projecting onto a convex polytope does not expand distances. It reports more than 130x solver speedups on 100,000 synthetic features. A Safe Screening Rule for Sparse Logistic Regression (Slores) builds an analogous safe region from strong convexity of the logistic dual. On Newsgroups at $\lambda = 0.1\lambda_{\max}$ it discards roughly 99% of inactive features and runs about 10x faster. Both assume that labels and all columns sit in one place. Our contribution is to show that their tests factor along the vertical split, and to build the cryptographic protocol that evaluates them.
The vertical feature-selection literature motivates the gap. Vertical Federated Feature Screening (VFS) is the closest work. It screens ultra-high-dimensional features in the vertical setting with an encrypted distance-covariance statistic and proves that the probability of wrongly discarding an active feature vanishes as the sample size grows. It is marginal by design, and its authors state that it cannot remove collinear redundant features. Its guarantee is also asymptotic, whereas ours holds deterministically, for every finite sample, relative to the exact Lasso solution.
Several other methods do selection in the vertical setting, but none with exactness guarantees. LESS-VFL decouples selection: the server runs Group Lasso on embeddings and sends proxy targets back to each party, which then prunes locally. Its selections answer a proxy problem rather than the joint objective. FedSDG-FS uses stochastic gates trained under Paillier encryption and needs an encrypted Gini warm start to stay stable. ICAFS captures interactions between clients by learning gates on WGAN-synthesized data, so its quality is bounded by how well the generative models fit. All three target neural models, and none certifies that a discarded feature was truly irrelevant to a specified objective.
CAESAR supplies the secure solver. It is a hybrid of homomorphic encryption and secret sharing for vertical sparse logistic regression and matches plaintext AUC (0.9914) and KS (0.9415) on a 100,000-feature risk-control dataset. However, it exploits sparsity already present in the inputs and performs no $L_1$ selection. We add soft-thresholding and screening on top of it.
One paper constrains the design. Local Feature Selection without Label or Feature Leakage shows that selection masks can themselves carry label information. Label Leakage in Vertical Federated Learning: A Survey documents how gradients leak labels in vertical training. Together these mean that the screening output must be treated as a leakage channel and measured, not assumed harmless.
Research Program
Take the Lasso first. Let $X_k$ be the columns held by party $k$, let $y$ be the labels held by the active party, and let $\theta^*(\lambda)$ be the dual optimum at regularization $\lambda$. The safe region takes a ball form: given the solution at the previous path value $\lambda_0$, the new dual optimum satisfies $\|\theta^*(\lambda) - \theta^*(\lambda_0)\| \le r(\lambda, \lambda_0)$, where the radius $r$ depends only on $y$, $\lambda$, and $\lambda_0$. Feature $j$ is then provably inactive at $\lambda$ whenever
$$|x_j^\top \theta^*(\lambda_0)| + r(\lambda,\lambda_0)\,\|x_j\| < 1.$$
The term $\|x_j\|$ is local to the feature owner. The radius $r$ is a scalar the label party can release. For binary labels, releasing it reveals essentially $n$. The only cross-party quantity is the inner product.
Note that $\theta^*(\lambda_0) = (y - X\beta(\lambda_0))/\lambda_0$, where $\beta(\lambda_0)$ is the coefficient vector at $\lambda_0$. Since $X\beta = \sum_k X_k\beta_k$, every party can contribute its share of the prediction to a secret-shared sum. The label party therefore obtains the residual inside the secure computation without learning any party's partial predictions.
The protocol works as follows. The label party Paillier-encrypts the dual vector and sends it to each passive party. Each passive party computes its encrypted inner products homomorphically. This costs one plaintext-ciphertext pass over its own columns, which is the same sparse-times-encrypted pattern CAESAR made efficient. The passive party then masks each result additively, converts it to secret shares, and evaluates the comparison above in the secret-shared domain. Only the bit for feature $j$ is opened, and only to the owner of $j$.
The surviving features enter a CAESAR-style secure proximal gradient solver with soft-thresholding evaluated in secret shares. A final secure KKT check certifies the solution. The path then advances to the next $\lambda$.
For logistic regression we port the Slores safe region. Its center is again a residual-like vector held by the label party, so the same inner-product-plus-local-norm structure applies. Its radius calculation needs a few extra scalar terms, which we will derive and also compute securely. Group Lasso with each party's columns treated as a group is the third case. It permits a party-level test that removes an entire organization from the protocol in one decision.
The analysis has three parts. First, we prove exactness: the secure path equals the centralized path, up to the fixed-point precision of the secret-sharing arithmetic. We will bound that precision error and widen the test by the bound so that safety survives rounding. Second, we account for cost in bytes, ciphertext operations, and rounds, as a function of $n$, $p$, the number of survivors, and the number of parties. Third, we characterize leakage. The opened bits reveal which of a party's own features correlate with the current residual, information the party would learn anyway from the final model. We will measure empirically whether sequences of these bits along the path let a passive party infer individual labels better than chance.
Baselines
The naive reference point is the same secure proximal gradient solver run with no screening at all, on identical data and network settings and over the same 100-point regularization path. It produces the same coefficients. It differs only in cost, so it isolates exactly what screening buys. Beating it means equal coefficients at a measurably lower total ciphertext-operation count and wall-clock time.
The strongest existing competitor for redundancy-sensitive vertical screening is VFS, run with its published coarse-to-fine procedure and with its kernel tuned on held-out data under the same tuning budget we give our path selection. We will also run VFS followed by the same secure Lasso on its survivors, which is the realistic pipeline a practitioner would build. The strongest number in the file for VFS is on its industrial credit data, which we do not have: AUC rose from 0.901 to 0.937 and runtime fell from about 1,911 s to about 129 s (Vertical Federated Feature Screening). We will therefore compare on shared public data. Beating VFS means equal or better held-out AUC with fewer selected features, especially when features are duplicated across parties, together with zero false rejections relative to the centralized Lasso, a property VFS does not claim at finite sample size.
For neural vertical selection we run LESS-VFL and FedSDG-FS on their own datasets, with the protocols, noise injection, and hyperparameter grids those papers describe. LESS-VFL reports roughly 20x less communication than standard Group Lasso on Phishing. FedSDG-FS reports 27% higher test accuracy than the best baseline on MADELON, using 47% fewer features. Neither file entry gives an absolute accuracy, so we will reproduce the absolute numbers rather than quote them. For ARCENE, GISETTE, and ISOLET, no reported result found on Lacuna for absolute accuracy. These comparisons place a convex sparse model next to nonlinear selectors. We count it as a success if our method recovers more planted signal features at comparable accuracy and lower cost, not necessarily if it wins on raw accuracy against a neural network.
The ablation that isolates the key ingredient replaces the safe ball test with the heuristic strong rule plus a KKT re-check, computed by the identical encrypted protocol. It shows whether guaranteed safety costs rejection power or saves re-solve rounds. A second ablation replaces the residual-based center with the raw label, which turns the test into a marginal one. It shows that the redundancy removal comes from conditioning on the current model.
Why not just…?
Why not just screen marginally with VFS and then fit locally? Marginal statistics score every member of a correlated cluster highly, as the VFS authors themselves acknowledge, so duplicated or near-duplicated columns spread across parties all survive. Our residual-based test removes a redundant copy once its partner enters the model. The planted cross-party duplicate experiment below tests this directly. If VFS-then-Lasso matches our survivor count and cost on that experiment, the redundancy argument fails, and the contribution reduces to the safety guarantee alone.
Why not just use strong rules with a KKT check, as centralized solvers do? This is a genuine threat. Strong rules typically reject more features, and the KKT check needs the same encrypted inner products we already compute. The difference is in rounds. Each time the KKT check catches a violation, the parties must run another encrypted solve, and in a vertical setting every round crosses organizations. The ablation counts violations and total rounds across the path. If violations are rare enough that strong rules win on total cost, we will report that and recommend a hybrid: the safe test to discard features permanently, and the strong rule only to order which survivors are solved first.
Why not just let each party select its own features locally? Purely local selection cannot see the labels or the other parties' columns. The LESS-VFL ablation without server guidance lost accuracy and needed more communication, and ICAFS shows that intra-client selection misses cross-client redundancy. We include an unsupervised local baseline, variance filtering at matched feature budgets, to show the gap on our data.
Why not just run stochastic gates as in FedSDG-FS? Gates can model nonlinear interactions that a sparse linear model misses, and on data where those interactions matter they may win on accuracy. They provide no certificate that a dropped feature is irrelevant, and they needed an encrypted warm start to train stably. We frame our method as the exact choice for generalized linear models. When a nonlinear model is required downstream, it can serve as a certified pre-filter, and we test that use by feeding our survivors into FedSDG-FS.
Proposed Experiments
The datasets are split vertically across two to ten parties. They are Prostate Cancer and Newsgroups from the Slores evaluation, the 100,000-feature synthetic regression design from DPP, and MADELON, ARCENE, and GISETTE from FedSDG-FS, plus Activity and Phishing from LESS-VFL. On the synthetic data and on MADELON we additionally plant cross-party near-duplicates: a copy of a signal column placed at a different party, with controlled correlation from 0.8 to 0.99. We also plant 50% Gaussian noise columns following LESS-VFL.
Metrics are as follows. Rejection ratio is the share of truly inactive features discarded. False rejections are counted against a centralized plaintext Lasso path and must be exactly zero. We also measure coefficient agreement with that path, held-out AUC or accuracy, selected-feature count, recovery of planted signal and removal of duplicates, total bytes, ciphertext operations, rounds, and wall-clock time on a simulated 10 Mbps link matching the CAESAR setting.
The decisive checks are three. First, the secure path must reproduce the centralized path with zero false rejections across all datasets and party counts. Second, rejection ratios on Newsgroups should approach the roughly 99% Slores reports centrally at $\lambda = 0.1\lambda_{\max}$, since the test is mathematically identical apart from precision widening. A large shortfall would indicate that fixed-point widening is too conservative. Third, on the planted-duplicate experiments, the number of surviving duplicates should fall well below VFS's as correlation rises. Finally, a label-inference attack trained on the sequence of opened bits seen by a passive party must do no better than an attack using the final model alone. If it does better, we will add calibrated noise to the comparison threshold and report the resulting cost in rejection power.
References
- Lasso Screening Rules via Dual Polytope Projection
- A Safe Screening Rule for Sparse Logistic Regression
- Vertical Federated Feature Screening
- LESS-VFL: Communication-Efficient Feature Selection for Vertical Federated Learning
- FedSDG-FS: Efficient and Secure Feature Selection for Vertical Federated Learning
- ICAFS: Inter-Client-Aware Feature Selection for Vertical Federated Learning
- When Homomorphic Encryption Marries Secret Sharing: Secure Large-Scale Sparse Logistic Regression and Applications in Risk Control
- Local Feature Selection without Label or Feature Leakage for Interpretable Machine Learning Predictions
- Label Leakage in Vertical Federated Learning: A Survey