Author: Alexey Kravatsky (the maintainer of the repo and a participant of m1p)

Co-researcher: Anton Plusnin (sophomore)

Consultant & Expert: Savelii Chezhegov

It will be rigorously formulated only after the completion of the draft abstract.

Modification of Sign-SGD that ensures differential privacy and the proof of its convergence with high probability under heavy-tailed noise.

The algorithm could be implemented into programs such as ChatGPT, with the prospect of making more use of the corrupted user data, which in turn, would improve the accuracy of the LLMs.

MNIST database: 28x28 black-and-white images of hand-written digits. CIFAR-10 dataset: 60,000 32x32 color images in 10 different classes: airplanes, cars, birds, cats, deer, dogs, frogs, horses, ships, and trucks.

The project must meet the following requirements. First, the accuracy and complexity of the algorithm must be on par with existing modifications. Second, a sound proof of correctness of the algorithm and, most importantly, its privacy, must be presented. Increased Byzantine resilience, faster performance, and an absence of parameters to be tuned are also desirable properties of the algorithm.

The main risk is the possibility of flaws in the proofs, although it could be mitigated by rigorous tests (what is false does not tend to work). Another one is the unacceptable complexity of the algorithm. Indeed, no one can guarantee that the algorithm we seek exists. Provided that the mentioned risks are eliminated, the algorithm must be feasible by its design, especially when applied to the tasks of LLMs.

A pipeline will be presented after the experiments are completed and the demo data is published.

We will post a link to the preprint when we finalize the work.