Proof-of-learning (PoL) proposes a model owner use machine learning training
checkpoints to establish a proof of having expended the necessary compute for
training. The authors of PoL forego cryptographic approaches and trade rigorous
security guarantees for scalability to deep learning by being applicable to
stochastic gradient descent and adaptive variants. This lack of formal analysis
leaves the possibility that an attacker may be able to spoof a proof for a
model they did not train.

We contribute a formal analysis of why the PoL protocol cannot be formally
(dis)proven to be robust against spoofing adversaries. To do so, we disentangle
the two roles of proof verification in PoL: (a) efficiently determining if a
proof is a valid gradient descent trajectory, and (b) establishing precedence
by making it more expensive to craft a proof after training completes (i.e.,
spoofing). We show that efficient verification results in a tradeoff between
accepting legitimate proofs and rejecting invalid proofs because deep learning
necessarily involves noise. Without a precise analytical model for how this
noise affects training, we cannot formally guarantee if a PoL verification
algorithm is robust. Then, we demonstrate that establishing precedence robustly
also reduces to an open problem in learning theory: spoofing a PoL post hoc
training is akin to finding different trajectories with the same endpoint in
non-convex learning. Yet, we do not rigorously know if priori knowledge of the
final model weights helps discover such trajectories.

We conclude that, until the aforementioned open problems are addressed,
relying more heavily on cryptography is likely needed to formulate a new class
of PoL protocols with formal robustness guarantees. In particular, this will
help with establishing precedence. As a by-product of insights from our
analysis, we also demonstrate two novel attacks against PoL.

By admin