Cut-Certified Subspace Federated Averaging

Integrate this into the server-client synchronization step of a federated optimizer, not into the local minibatch gradient calculation. Let each client hold a flattened parameter vector x_i in R^d. First choose a rank-r shared basis U with orthonormal columns, either by taking the top-r principal components of client parameter updates from a warm-up round or by using a fixed blockwise basis for selected layers. Set A_{ij}=U C_{ij}U^T, where C_{ij} is usually the scalar c_{ij} times the r-by-r identity; c_{ij} can encode bandwidth, trust, or data similarity. A practical discrete update is: (1) clients perform K local AdamW or SGD steps; (2) construct the client graph; (3) for each edge compute delta_{ij}=x_i-x_j; (4) update x_i <- x_i-eta_sync sum_j A_{ij} delta_{ij}; (5) transmit or aggregate only U^T x_i or U^T delta_i, retaining the private residual locally. Pseudocode is shared_i=U.T@x_i; shared_i-=eta_sync*sum(c_ij*(shared_i-shared_j)); x_i=U@shared_i+(I-U@U.T)@x_i. Compute the paper's mathematical criterion for the chosen U and edge matrices; estimate cut coverage empirically by sampling random client subsets S and checking the smallest eigenvalue of sum_crossing_edges U.T@A_ij@U. The first experiment should use 10-client non-IID CIFAR-10 or FEMNIST training with a small CNN, comparing FedAvg, FedProx, and full-parameter graph averaging at equal communication bytes. Sweep r in {1%, 5%, 10%, 25%} of parameter dimension. Success means higher held-out accuracy under the same transmitted bytes, lower client drift in shared coordinates, and a strong correlation between the cut certificate and eventual shared-coordinate disagreement.