Fairness-Aware Tensor ALS over Encrypted Aggregates

Federated learning trains one model across many data holders, such as hospitals or banks, without pooling their raw records. Two demands pull against each other here. Protecting individuals usually means adding random noise to what clients send, and that noise hurts small demographic groups the most. Enforcing fairness across groups requires knowing group membership, which the server is not supposed to see. This proposal makes a narrow claim. If the model is a low-rank tensor model trained by alternating least squares, meaning one factor is updated at a time while the others are held fixed, then a fairness-penalized update can be computed exactly. The server needs only a few small encrypted sums. It never sees per-client gradients, per-group statistics, or any added noise, and the encrypted computation needs at most two rounds of ciphertext multiplication.

The reason is structural. Freezing all factors but one turns a tensor model's training problem into ordinary least squares (Tensor Decompositions and Data Mining; Tensor Decompositions and Applications). Least squares depends on the data only through sums of small matrices. Sums are the cheap operation in homomorphic encryption, which is encryption that allows arithmetic directly on encrypted values. In such schemes, additions grow the cryptographic noise linearly, while each multiplication grows it much faster. A squared fairness penalty adds only a rank-one term built from products of those sums. FHAIM showed the same move works for synthetic data, swapping a non-smooth $\ell_1$ score for a squared $\ell_2$ one that encryption evaluates natively (FHAIM). Together these let fairness, exactness, and encryption cost scale with the tensor rank rather than with model size or dataset size.

Core Claim

Take one alternating step on a low-rank (canonical polyadic or tensor-train) model with squared loss. Let $x$ be the active factor, flattened to dimension $p = I_n R$, where $I_n$ is the mode size and $R$ is the rank. Each prediction is linear in $x$: $\hat y_i = z_i^\top x$, where $z_i$ is built from sample $i$ and the frozen factors.

We penalize the squared covariance between predictions and a binary sensitive attribute $s_i$. This is a smooth stand-in for demographic parity. The update solves

$$\big(G + \lambda\, v v^\top + \mu I\big)\,x = b,$$

where $G=\sum_i z_i z_i^\top$ and $b=\sum_i y_i z_i$. The fairness direction, scaled by the total sample count $N$ to avoid division, is $N v = N\sum_i s_i z_i - (\sum_i s_i)(\sum_i z_i)$. Here $\lambda$ is the fairness weight and $\mu$ is a ridge term.

Each client encrypts its local $G_k$, $b_k$, $\sum s_i z_i$, $\sum z_i$ and $\sum s_i$. These are of size $O(p^2)$, independent of how many samples the client holds. The server adds the ciphertexts. It then forms $N^2 v v^\top$ homomorphically, which takes multiplicative depth two. Only the combined system matrix and right-hand side are decrypted, using threshold decryption among clients or a restricted decryption service of the kind FHAIM uses. The protected-group sums themselves are never revealed. The server solves the small linear system in plaintext and broadcasts the new factor.

What is new is the combination of three properties. The update is exact, because no noise is injected. It is fairness-aware at the group level without exposing group statistics. Its encrypted cost depends only on rank and needs no bootstrapping, the expensive procedure that refreshes a ciphertext's noise budget.

Relation to Prior Work

Three papers motivate the gap. Wasif et al. find that encryption keeps fairness within 5% of the non-private baseline, while noise-based differential privacy (DP) widens group disparities. They also find that fairness-tuned optimizers leak more: their differential leakage rate rose from 0.00267 to 0.00443 on MNIST. They treat encryption as a wrapper around flat gradient vectors, however, and pay 2–3× more compute than DP. Chen et al. and Tian et al. supply the mechanisms: DP noise drowns the weaker gradient signal of small groups, and the predictable boundary shifts of fair models enable a fairness-discrepancy membership attack. That attack constrains our design, because even exact encrypted training must be checked against it.

The method is assembled from existing pieces. ALS and tensor-train sweeping come from Kolda, Bader et al. and Dolgov et al.. Packing ciphertext slots follows CryptoNets and the HE tensor compiler. The squared-penalty trick follows FHAIM.

The closest work is Homomorphic Matrix Completion. It masks each client's data vector with a structured key, so the server can run alternating minimization on masked data with exact recovery. It is limited to two-way matrices, lists tensors as open, and has no fairness term. We differ in what is protected and how. We aggregate encrypted sufficient statistics rather than masking raw data. We handle tensors of three or more modes. We compute a group-fairness term from data the server cannot see.

On the federated tensor side, Coupled Tensor Train FL converges in 2 rounds and runs about 15× faster than FedGTF-EF on CDC Diabetes, but it exchanges shared cores in plaintext and ignores fairness. TDPFed averages factor matrices in plaintext with gradient-based personalization, also without fairness. Our protocol adds encryption and a fairness term to the CTT-style setting.

Research Program

The first component is the protocol: canonical polyadic and tensor-train variants, CKKS parameters chosen so depth two fits without bootstrapping, and packing of the $p\times p$ statistics into slots. Since $p = I_n R$, a rank of 8 on a mode of size 140 gives $p=1120$. We will measure whether that fits comfortably, or whether block-diagonal or sketched statistics in the spirit of SPALS are needed.

The second component extends fairness beyond one binary attribute. Several groups give a sum of rank-one terms. Equal-opportunity variants restrict the sums to positives. Classification is handled with iteratively reweighted least squares, with weights computed locally from the broadcast model.

The third component is a leakage analysis of what the decrypted combined system reveals. It is a single $p\times p$ matrix per step, summed over all clients. We will also test an optional arm that adds DP noise once to this aggregate instead of to per-client gradients. Our hypothesis is that one aggregate perturbation hurts small groups far less than per-update noise, and the experiments test this directly.

Baselines

The naive reference points are plaintext federated ALS with no fairness term and no encryption, and FedAvg on an equivalent flat model. These anchor accuracy and fairness ceilings.

The strongest existing method on the privacy-fairness question is encrypted aggregation of flat gradients with fairness-aware optimizers, as in Wasif et al.. They report fairness within 5% of non-private and accuracy disparity below $10^{-4}$ on Alzheimer's MRI, at 2–3× DP's compute. We run q-FedAvg and Ditto under the same CKKS library, client count and data splits. We beat it if we match its group-fairness metrics at equal accuracy while sending at least an order of magnitude fewer ciphertext bytes and spending less wall-clock time per training run.

For group fairness, the comparison points are AgnosticFair, which reports a risk difference of 0.0196 on Adult under shift versus 0.1477 for standard FL, and FairDP, which reports over 45% fairness gain on Adult relative to DP-IS-SGD with under 2.64% utility drop. We rerun both on our partitions with equal tuning budgets, a fixed grid over the fairness weight with five seeds each. We compare full accuracy–fairness curves, not single points. FedMinMax is run in its partial-access setting; no reported result was found on Lacuna for its worst-group risk numbers. For tensor data, CTT in plaintext is the efficiency reference, at 2 rounds on ECG and Diabetes.

Three ablations isolate the key ingredients. The first is the same protocol with pairwise-mask secure aggregation instead of encryption, which reveals per-group sums. The second is the same factorized model trained by encrypted gradient descent instead of ALS, which isolates the closed-form alternating step. The third is our method with $\lambda=0$, which isolates the fairness term.

Why not just…?

Why not just use mask-based secure aggregation, since the protocol only needs sums? This is the most serious threat. If revealing per-group aggregate sums is acceptable, masking is cheaper and gives the same exact update. Encryption earns its place only by computing $v v^\top$ before decryption, so that only the combined system is revealed. We settle this with an attribute-inference experiment. An adversary given the masked-aggregation transcript tries to recover group base rates and group-conditional feature means, per client, by differencing across rounds and client subsets. The same adversary is then given our transcript. If the two leak comparably, we will report that masking suffices and recast the contribution as fair tensor ALS over secure sums.

Why not just use DP-SGD with a fairness regularizer? Chen et al. and Wasif et al. show that per-update noise disproportionately harms minority groups and that fairness tuning raises leakage. Our DP-FedAvg baseline, run at matched $\epsilon$, measures this gap on our data. The optional aggregate-DP arm tests whether noise placed once on the decrypted system avoids it.

Why not just encrypt ordinary FedAvg updates, or run encrypted gradient descent on the factorized model? Flat encrypted updates scale with parameter count, and encrypted training is four to five orders of magnitude slower than plaintext (Towards Deep Neural Network Training on Encrypted Data). Gradient descent on factors shrinks the payload but needs many rounds, each with fresh encryption and decryption. The gradient-descent ablation reports rounds and bytes to reach a fixed fairness–accuracy point, against ALS sweeps.

Proposed Experiments

The tabular fairness benchmarks are Adult (sex, race) and COMPAS (race), each split across 10–50 clients with label skew and group-proportion skew, including a partial-access split where some clients contain no minority members. For tabular data the model is a CP-parameterized multilinear model over grouped feature blocks. The multi-way benchmarks are the CDC Diabetes tensor (1000×20×24), using available demographic indicators as the sensitive attribute, and the ECG tensor (1000×110×140), where fairness is measured only if a usable demographic field exists. We also include synthetic third- and fourth-order tensors with planted group-dependent structure, where ground truth is known.

The metrics are accuracy, demographic-parity and equal-opportunity gaps, worst-group risk, ciphertext bytes per sweep, wall-clock time, and maximum multiplicative depth used. Privacy is measured with membership-inference success, differential leakage rate, and FD-MIA from Tian et al..

Four checks decide the outcome. First, the encrypted protocol must reproduce plaintext fair-ALS factors to within CKKS precision at depth at most two with no bootstrapping. Second, on Adult, its accuracy–fairness curve must reach the region AgnosticFair reports, a risk difference below 0.05, at lower cost than the encrypted flat-gradient baseline. Third, ciphertext volume must grow with $I_nR$ and stay flat as client sample counts grow. Fourth, the attribute-inference comparison against mask-based aggregation must show measurably less group-statistic leakage; if it does not, the encryption component is not justified. A negative result on the third check would also be informative. It would show that $p^2$-sized statistics are too large at practical ranks and that sketching is required before the approach is usable.