Working on a test case to confirm an idea would improve the performance of the RPM paper and reduce round complexity – it also has a neat side effect that it also enables massive parallel gradient descent compute for secure ML in a completely MPC context

BDFL of Quilibrium, Eng @ Farcaster, ex-Coinbase, always opinionated, never hydrated

/quilibrium

In the spirit of building in public, I'll share the approach I'm evaluating – the RPM paper referenced the SecureML paper, which suggested the use of Beaver triples to keep the polynomial degree bounded to the shares of matrices when computing dot products. This works great under 2PC but requires log(n) rounds...

Cue a paper from 1989, where Bar-Ilan and Beaver produced an approach for multiplying an arbitrary number of square matrices of equal dimension: https://dl.acm.org/doi/pdf/10.1145/72981.72995

The TL;DR version is, instead of computing triples, you instead compute n+1 fully random matrices, _and their inverse_. When secret sharing those, each party can multiply the share of the random matrix by the share of the intended matrix to multiply, then multiply that by the _next_ random matrix's inverse.

Recombining those, you get a series of n recombined matrices that are indistinguishable from random, which you can then multiply together. Finally, you multiply the share of the first inverse matrix by that resulting product, and then that with the final random matrix share.

This, when recombined, gets you the resulting dot product of all the intended matrices, and only requires a complexity of four rounds (constant, which is a much better improvement over log(n)).

So why does this apply to ML? This comes back around to the SecureML paper, which explicitly was focusing on 2PC. Using this approach, you can augment their protocols as well, enabling MPC versions of SGD that are still very efficient.

when you increase the number of participants in the protocol. I had tuned Quilibrium to be relatively lower bounded on this so it wasn't a super painful issue, but in the spirit of research and downtime waiting between flights, I kept thinking... https://i.imgur.com/eA7rNCI.gif