Turning Duplicate Mining Work into Bias Cancellation for Federated Proof of Learning

Proof of Learning blockchains replace the pointless hash puzzles of Bitcoin-style mining with neural network training. They have a waste problem of their own. When many miners race to train the same model and only the winner's result enters the chain, every losing miner's gradient computation is thrown away. This proposal argues that this duplicate work can be redirected rather than eliminated. Suppose the protocol deliberately assigns competing miner groups different step sizes on the same task. It can then combine their models with Richardson–Romberg extrapolation, a classical trick that takes two estimates made at step sizes $\gamma$ and $2\gamma$ and adds them so that the leading error term cancels. The combined model should be more accurate than either miner group could produce alone. Every miner's work then contributes to the block.

The opportunity comes from a result in federated learning theory. Federated averaging (FedAvg), where clients take several local gradient steps and a server averages their models, run with a fixed step size does not converge to the true optimum. It settles into a cloud around a shifted point. Refined Analysis of Constant Step Size Federated Averaging and Federated Richardson-Romberg Extrapolation shows that this shift splits into a heterogeneity part and a gradient-noise part. The shift persists even when all clients hold identical data, as long as the loss is non-quadratic. Running at two step sizes and extrapolating removes the first-order shift, at the price of doubling communication. That doubled cost is exactly what a competitive mining protocol already pays and discards.

Core Claim

Assume three things: miner groups in a federated Proof of Learning round share an initialization, a data order and mini-batch randomness derived from the previous block's hash; they differ only in step size; and they re-synchronize to the extrapolated model at every block. Under those conditions, combining their models as

$$\bar\theta = 2\theta_{\gamma} - \theta_{2\gamma}$$

yields a block model with lower test loss than the same total compute spent on a single FedAvg pool. Here $\theta_\gamma$ is the averaged model a group reaches after one block of local training at step size $\gamma$. The rationale is the first-order expansion $\mathbb{E}\,\theta_\gamma = \theta^\star + \gamma B + O(\gamma^2)$, where $\theta^\star$ is the target and $B$ the bias direction. Doubling $\gamma$ doubles the $B$ term, and the combination above subtracts it out.

The new claim is not the extrapolation itself. It is two things. First, consensus machinery that already exists for anti-cheating reasons, namely binding initialization to the block hash as in Proof of Learning (PoLe), also supplies the shared randomness that keeps two deep-network trajectories close enough to extrapolate. Second, the protocol's short block cadence provides the frequent restarts that keep the first-order expansion accurate on non-convex losses. The Mangold et al. analysis lacks both, being restricted to smooth, strongly convex objectives and stationary behaviour.

Position Relative to Prior Work

The waste problem motivates the proposal. PoLe and the market designs of Amar et al. award the block to the best independently trained model and discard the rest. We keep competition between groups but make the losers' output a necessary ingredient of the block.

Collaborative federated consensus constrains the design, because it is the natural competitor. FedChain organizes miners into latency-aware pools that train jointly with secret-shared ring-allreduce, weights updates by KL divergence, and proves accuracy with zero-knowledge proofs. Proof of Federated Learning verifies pool accuracy with homomorphic encryption and garbled circuits in under 2 seconds on CIFAR-10. Neither addresses the fixed-step-size bias. Both already avoid redundancy by pooling everyone, so our method must beat pooling at equal compute, not merely beat winner-takes-all.

The method comes from the loss-decomposition line. Mangold et al. supply the extrapolation and its bias split. Tackling Data Heterogeneity in Federated Learning via Loss Decomposition (FedLD) splits global loss into local, distribution-shift and aggregation terms. It attacks them with a logit-norm regularizer and SVD-projected aggregation, which is orthogonal and can be stacked with our scheme. Can We Theoretically Quantify the Impacts of Local Updates on the Generalization Performance of Federated Learning? shows that the number of local steps per round has an optimum. That matters here because the block interval fixes this number.

The verification side borrows from Byzantine-Resilient Learning Beyond Gradients, which makes checking cheap by transmitting seeds so verifiers can regenerate work. We apply the same idea to segments of a gradient trajectory whose data order is fixed by the block hash.

Research Program

We will build a simulated federated Proof of Learning protocol. At each block, the previous block hash seeds the model initialization (the last block's extrapolated model), the client mini-batch order, and the assignment of miners into a $\gamma$-group and a $2\gamma$-group. Each group runs FedAvg for $K$ local steps across its clients and commits its averaged model. The block model is the extrapolation, and rewards are split across both groups in proportion to the extrapolated model's validation improvement.

Verification has two parts. Verifiers run a forward pass of the block model on a held-out set. They also re-execute one hash-selected interval of each group's trajectory to catch fabricated commitments. That check is possible only because the data order is deterministic. We will also test a three-step-size variant that cancels second-order terms, and a heterogeneous-group variant in which the two groups see different client subsets. The second variant measures how much of the cancellation survives when the heterogeneity component of the bias differs between groups.

The analysis has two parts. On strongly convex synthetic problems we check that per-block extrapolation with restarts recovers the cancellation Mangold et al. predict. On deep networks we measure empirically the linear-interpolation loss barrier between $\theta_\gamma$ and $\theta_{2\gamma}$ as a function of $K$. This tells us how long coupled trajectories stay in one region where the expansion holds. If the barrier grows quickly with $K$, the protocol's block length must be chosen to bound $K$. That gives a concrete, learning-driven rule for block cadence in place of the arbitrary 20–40 second target of Wu et al..

Baselines

The naive reference is winner-takes-all independent training as in PoLe. Each of $M$ miners trains alone and the best model is kept. This is the waste we claim to remove. It is run with the same total gradient steps per block.

The strongest competitor on the question we pose is single-pool FedAvg using all $M$ miners at one tuned constant step size, which is the FedChain-style collaborative design. It uses all compute and also benefits from the $1/N$ bias reduction with more clients that Mangold et al. report. This is a real threat to the proposal, because our groups each hold half the clients. We will give it the same number of clients, gradient steps, communication rounds and step-size tuning grid. We count a win only if extrapolation achieves lower test loss or higher accuracy at equal compute across seeds, or reaches a fixed accuracy in fewer blocks.

Because the pool is also allowed a decaying step size, which removes stationary bias by a different route, we include FedAvg with a tuned step-size schedule. We also include SCAFFOLD-style control variates, which correct heterogeneity drift but, per Mangold et al., not the noise-induced bias.

On medical heterogeneous data the strongest reported number we know is FedLD at 82.30% accuracy on Retina Split-3, against 81.13% for FedAvg, and 83.87% on COVID-FL (FedLD). We will reproduce FedLD under our client splits and also run FedLD inside each extrapolation group, to test whether the gains add.

For a consensus-native baseline we use directed guiding gradients on CIFAR-10 with ResNet18, where Wu et al. report accuracy rising "from approximately 20% to 60%" over 600 blocks. For FedChain no reported accuracy number was found on Lacuna, so we compare to our reimplementation of its pooled design.

Three ablations isolate the key ingredients. Plain averaging of $\theta_\gamma$ and $\theta_{2\gamma}$ in place of extrapolation separates bias cancellation from mere ensembling. Running the groups with independent seeds isolates the hash coupling. Never re-synchronizing tests whether long uncoupled runs break the expansion.

Why not just…?

Why not just pool every miner into one federated job, as FedChain does? Pooling also removes duplicate work, so the case for extrapolation rests entirely on whether bias cancellation beats the $1/N$ bias shrinkage from doubling the pool. Theory favours extrapolation when bias dominates variance, which happens with large step sizes and strong heterogeneity. That suggests short blocks with aggressive step sizes are the regime where we should win. We do not know in advance whether this regime is the practically relevant one for deep nets. The equal-compute pooled baseline settles it directly, and we will report the regime boundary rather than only favourable points.

Why not just decay the step size? A decaying schedule also removes asymptotic bias. It does so by slowing progress, which fits poorly with a protocol that must deliver a useful model improvement every block. Mangold et al. report an $\epsilon^{2/3}$ communication-complexity improvement of extrapolation over standard FedAvg in the convex case. Whether that improvement survives against a well-tuned schedule on deep nets is an open empirical question. We tune the schedule with the same budget and compare blocks-to-target-accuracy.

Why not just average the competing models, or keep the best one? Averaging two trajectories at different step sizes leaves a bias of $1.5\gamma B$, and picking the best keeps $\gamma B$. Only the signed combination removes it. The averaging ablation tests this. If averaging matches extrapolation on deep nets, our bias-cancellation explanation is wrong and we will say so.

Why not just use Proof of Stake and run federated learning off-chain? This removes energy waste outright, and for ledgers that only need security it is the better choice. Our setting is the one the Proof of Useful Work literature targets, where the goal is a compute market for training (Chenli et al.). There, the question is how to make the purchased compute maximally useful. Our results apply to that setting and make no claim against Proof of Stake.

Proposed Experiments

We begin with synthetic strongly convex federated logistic regression, replicating the Mangold et al. setting. This checks that per-block extrapolation with restarts reproduces the predicted bias reduction and the $1/N$ scaling. Next we run non-IID CIFAR-10 with ResNet18, using label-skew partitions following The Non-IID Data Quagmire of Decentralized Machine Learning, which reports 3% to 74% accuracy loss under skew, with 10 to 100 miners and 600 blocks to match Wu et al. Finally we run Retina Split-3 and COVID-FL to match FedLD.

Metrics are test accuracy and loss per block at equal total gradient steps, blocks to a target accuracy, the interpolation loss barrier between the coupled trajectories, and verification cost per block measured in forward and backward passes.

Three outcomes are decisive. First, on deep non-IID CIFAR-10, extrapolation with hash-coupled, re-synchronized groups must beat the equal-compute single pool and the tuned decaying schedule across at least five seeds. Second, the uncoupled-seed ablation must lose most of that gain; otherwise the consensus coupling is not doing the work we claim. Third, the gain must shrink as $K$ grows in step with the measured barrier, which would confirm that block length is the control knob. If the single pool wins everywhere, the conclusion is that collaborative pooling, not extrapolation, is the right fix for mining waste, and that is still a clear negative result for the field.