A.1 Secret Sharing CRYPTEN uses two different types of secret sharing: (1) arithmetic secret sharing [9] and (2) binary secret sharing [11]. Below, we describe the secret sharing methods for single values xbut they can trivially be extended to real-valued vectors x. A.1.1 Arithmetic Secret Sharing CRYPTEN uses arithmetic secret sharing to perform most MPC computations. In arithmetic secret sharing, a scalar value x Z/QZ (where Z/QZ denotes a ring with Qelements) is shared across |P| parties in such a way that the sum of the shares reconstructs the original value x. We denote the sharing of x by [x] = {[x]p}p P, where [x]p Z/QZ indicates party p's share of x. The representation has the property that P p P[x]p mod Q=x. We use a fixed-point encoding to obtain xfrom a floating-point value xR. To do so, we multiply xR with a large scaling factor B and round to the nearest integer: x = bBxRe, where B = 2L for some precision parameter, L. To decode a value, x, we compute xR x/B. Encoding real-valued numbers this way incurs a precision loss that is inversely proportional to L. Since we scale by a factor B to encode numbers, we must scale down by a factor B after every multiplication.

Secure multi-party computation (MPC) allows parties to perform computations on data while keeping that data private. This capability has great potential for machine-learning applications: it facilitates training of machine-learning models on private data sets owned by different parties, evaluation of one party's private model using another party's private data, etc. Although a range of studies implement machine-learning models via secure MPC, such implementations are not yet mainstream. Adoption of secure MPC is hampered by the absence of flexible software frameworks that "speak the language" of machine-learning researchers and engineers. To foster adoption of secure MPC in machine learning, we present CRYPTEN: a software framework that exposes popular secure MPC primitives via abstractions that are common in modern machine-learning frameworks, such as tensor computations, automatic differentiation, and modular neural networks. This paper describes the design of CRYPTEN and measure its performance on state-ofthe-art models for text classification, speech recognition, and image classification. Our benchmarks show that CRYPTEN's GPU support and high-performance communication between (an arbitrary number of) parties allows it to perform efficient private evaluation of modern machine-learning models under a semi-honest threat model. For example, two parties using CRYPTEN can securely predict phonemes in speech recordings using Wav2Letter [17] faster than real-time. We hope that CRYPTEN will spur adoption of secure MPC in the machine-learning community.

For all authors... (a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [No] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?

Decentralized optimization are playing an important role in applications such as training large machine learning models, among others. Despite its superior practical performance, there has been some lack of fundamental understanding about its theoretical properties. In this work, we address the following open research question: To train an overparameterized model over a set of distributed nodes, what is the minimum communication overhead (in terms of the bits got exchanged) that the system needs to sustain, while still achieving (near) zero training loss? We show that for a class of overparameterized models where the number of parameters D is much larger than the total data samples N, the best possible communication complexity is (N), which is independent of the problem dimension D. Further, for a few specific overparameterized models (i.e., the linear regression, and certain multi-layer neural network with one wide layer), we develop a set of algorithms which uses certain linear compression followed by adaptive quantization, and show that they achieve dimension independent, near-optimal communication complexity. To our knowledge, this is the first time that dimension independent communication complexity has been shown for distributed optimization.

Existing analyses of optimization in deep learning are either continuous, focusing on (variants of) gradient flow, or discrete, directly treating (variants of) gradient descent. Gradient flow is amenable to theoretical analysis, but is stylized and disregards computational efficiency. The extent to which it represents gradient descent is an open question in the theory of deep learning.