Differentially private stochastic gradient descent using optimized correlation matrices

Abstract

Methods, systems, and apparatuses, including computer programs encoded on computer storage media, for training a neural network using differentially private stochastic gradient descent (DP-SGD) with correlated noise. In some implementations, a system determines a correlation matrix by performing an optimization to improve a utility metric that is dependent on a noise multiplier. The system can then train the neural network using the optimized correlation matrix and a privacy-amplifying batching scheme to produce a neural network with high utility while satisfying a data security criterion.

1 . A method performed by one or more computers for training of a neural network, the method comprising:
 training the neural network on a set of training examples to perform a machine learning task, the training comprising, at each of a plurality of training iterations:
 determining gradients of an objective function with respect to a set of neural network parameters of the neural network; 
 generating a plurality of noise values for modifying the gradients of the objective function, comprising:
 stochastically sampling a plurality of initial noise values from a noise distribution that is parametrized by a noise multiplier; and 
 generating the noise values by applying a correlation matrix to the plurality of initial noise values; 
 
 generating noisy gradients by combining the plurality of noise values with the gradients of the objective function; and 
 updating the set of neural network parameters of the neural network using the noisy gradients; 
   wherein the correlation matrix used during the training of the neural network is determined by performing operations comprising:
 iteratively updating a current correlation matrix over a plurality of optimization iterations to optimize a utility metric, comprising, at each optimization iteration:
 determining a current noise multiplier that, if used in conjunction with the current correlation matrix during the training of the neural network, is predicted to cause the trained neural network to satisfy a data security criterion; 
 determining a current utility metric for the current correlation matrix based at least in part on the current noise multiplier; 
 determining gradients of the current utility metric with respect to the current correlation matrix; and 
 updating the current correlation matrix using the gradients of the current utility metric. 
 
   
     
     
         2 . The method of  claim 1 , wherein the data security criterion is an (ϵ, δ)-differential privacy (DP) criterion, wherein ϵ is a target privacy budget parameter defining a bound on a privacy loss, and δ is a target privacy breach parameter defining a bound on a probability of a privacy loss exceeding the privacy budget parameter ϵ. 
     
     
         3 . The method of  claim 1 , wherein determining a current noise multiplier that, if used in conjunction with the current correlation matrix during the training of the neural network, is predicted to cause the trained neural network to satisfy the data security criterion comprises:
 determining the current noise multiplier using a δ-estimation function that is configured to process an input correlation matrix, an input noise multiplier, and an input privacy budget parameter to generate a Monte Carlo estimate of a corresponding privacy breach parameter.   
     
     
         4 . The method of  claim 3 , wherein the δ-estimation function is configured to generate the Monte Carlo estimate of the corresponding privacy breach parameter as an average of a plurality of stochastic estimates of the privacy breach parameter, wherein each of the plurality of stochastic estimates of the privacy breach parameter is based at least in part on one or more random values that are sampled from one or more probability distributions, wherein the plurality of stochastic estimates of the privacy breach parameter are generated substantially in parallel. 
     
     
         5 . The method of  claim 3 , wherein determining the current noise multiplier using a δ-estimation function comprises selecting the current noise multiplier so that processing the current correlation matrix, the current noise multiplier, and a target privacy budget parameter ϵ using the δ-estimation function causes the δ-estimation function to generate an estimated privacy breach parameter that is within a tolerance threshold of a target privacy breach parameter δ. 
     
     
         6 . The method of  claim 5 , wherein the current noise multiplier is selected using a bisection algorithm. 
     
     
         7 . The method of  claim 1 , wherein determining the current utility metric for the current correlation matrix based at least in part on the current noise multiplier comprises:
 determining the current utility metric for the current correlation matrix as:   
       
         
           
             
               σ 
               · 
               
                 
                   ❘ 
                   "\[LeftBracketingBar]" 
                 
                 
                   
                     A 
                     
                       - 
                       1 
                     
                   
                   ⁢ 
                   C 
                 
                 
                   ❘ 
                   "\[RightBracketingBar]" 
                 
               
             
           
         
       
       wherein σ is the current noise multiplier, A is an all-ones lower-triangular matrix, C is the current correlation matrix, and |·| is a norm operation. 
     
     
         8 . The method of  claim 1 , wherein determining gradients of the current utility metric with respect to the current correlation matrix comprises:
 determining gradients, with respect to the current correlation matrix, of a δ-estimation function that is configured to process an input correlation matrix, an input noise multiplier, and an input privacy budget parameter to generate a Monte Carlo estimate of a corresponding privacy breach parameter; and   determining the gradients of the current utility metric based at least in part on the gradients of the δ-estimation function.   
     
     
         9 . The method of  claim 1 , wherein determining gradients of the current utility metric with respect to the current correlation matrix comprises:
 determining gradients, with respect to the current noise multiplier, of a δ-estimation function that is configured to process an input correlation matrix, an input noise multiplier, and an input privacy budget parameter to generate a Monte Carlo estimate of a corresponding privacy breach parameter; and   determining the gradients of the current utility metric based at least in part on the gradients of the δ-estimation function.   
     
     
         10 . The method of  claim 1 , wherein determining gradients of the current utility metric with respect to the current correlation matrix comprises:
 determining the gradients of the current utility metric as:   
       
         
           
             
               
                 σ 
                 · 
                 
                   
                     ∂ 
                     
                       
                         ❘ 
                         "\[LeftBracketingBar]" 
                       
                       
                         
                           A 
                           
                             - 
                             1 
                           
                         
                         ⁢ 
                         C 
                       
                       
                         ❘ 
                         "\[RightBracketingBar]" 
                       
                     
                   
                   
                     ∂ 
                     C 
                   
                 
               
               - 
               
                 
                   
                     
                       ❘ 
                       "\[LeftBracketingBar]" 
                     
                     
                       
                         A 
                         
                           - 
                           1 
                         
                       
                       ⁢ 
                       C 
                     
                     
                       ❘ 
                       "\[RightBracketingBar]" 
                     
                   
                   ⁢ 
                   
                     ( 
                     
                       
                         ∂ 
                         
                           δ 
                           ˆ 
                         
                       
                       
                         ∂ 
                         C 
                       
                     
                     ) 
                   
                 
                 
                   
                     ∂ 
                     
                       δ 
                       ˆ 
                     
                   
                   
                     ∂ 
                     σ 
                   
                 
               
             
           
         
       
       wherein σ is the current noise multiplier, A is an all-ones lower-triangular matrix, C is the current correlation matrix, |·| is a norm operation, ∝ is a partial derivative operator, and {circumflex over (δ)} is a δ-estimation function. 
     
     
         11 . The method of  claim 1 , wherein during the iterative updates to the current correlation matrix over the plurality of optimization iterations, the current correlation matrix is constrained to remain in a lower-dimensional subspace of a space of possible correlation matrices. 
     
     
         12 . The method of  claim 11 , wherein the lower-dimensional subspace comprises a space of Toeplitz matrices. 
     
     
         13 . The method of  claim 11 , wherein the lower-dimensional subspace comprises a space of block lower triangular matrices. 
     
     
         14 . The method of  claim 11 , wherein the lower-dimensional subspace comprises a space of lower triangular matrices. 
     
     
         15 . The method of  claim 1 , wherein updating the current correlation matrix using the gradients of the current utility metric comprises:
 updating the current correlation matrix using the gradients of the current utility metric using a gradient descent optimization technique.   
     
     
         16 . The method of  claim 1 , wherein the neural network is configured to perform an image processing task comprising processing an input image to generate a prediction characterizing the input image; or
 wherein the neural network is configured to perform an audio processing task comprising processing input audio data to generate a prediction characterizing the input audio data; or   wherein the neural network is configured to perform a video processing task comprising processing input video data to generate a prediction characterizing the input video data.   
     
     
         17 . The method of  claim 1 , further comprising, after training the neural network:
 receiving a network input to the neural network; and   processing the network input using the trained neural network to generate a corresponding network output; and   providing the network output generated by the neural network.   
     
     
         18 . A system comprising:
 one or more computers; and   one or more storage devices communicatively coupled to the one or more computers, wherein the one or more storage devices store instructions that, when executed by the one or more computers, cause the one or more computers to perform operations, the operations comprising:   training the neural network on a set of training examples to perform a machine learning task, the training comprising, at each of a plurality of training iterations:
 determining gradients of an objective function with respect to a set of neural network parameters of the neural network; 
 generating a plurality of noise values for modifying the gradients of the objective function, comprising:
 stochastically sampling a plurality of initial noise values from a noise distribution that is parametrized by a noise multiplier; and 
 generating the noise values by applying a correlation matrix to the plurality of initial noise values; 
 
 generating noisy gradients by combining the plurality of noise values with the gradients of the objective function; and 
 updating the set of neural network parameters of the neural network using the noisy gradients; 
   wherein the correlation matrix used during the training of the neural network is determined by performing operations comprising:
 iteratively updating a current correlation matrix over a plurality of optimization iterations to optimize a utility metric, comprising, at each optimization iteration:
 determining a current noise multiplier that, if used in conjunction with the current correlation matrix during the training of the neural network, is predicted to cause the trained neural network to satisfy a data security criterion; 
 determining a current utility metric for the current correlation matrix based at least in part on the current noise multiplier; 
 determining gradients of the current utility metric with respect to the current correlation matrix; and 
 updating the current correlation matrix using the gradients of the current utility metric. 
 
   
     
     
         19 . One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations, the operations comprising:
 training the neural network on a set of training examples to perform a machine learning task, the training comprising, at each of a plurality of training iterations:
 determining gradients of an objective function with respect to a set of neural network parameters of the neural network; 
 generating a plurality of noise values for modifying the gradients of the objective function, comprising:
 stochastically sampling a plurality of initial noise values from a noise distribution that is parametrized by a noise multiplier; and 
 generating the noise values by applying a correlation matrix to the plurality of initial noise values; 
 
 generating noisy gradients by combining the plurality of noise values with the gradients of the objective function; and 
 updating the set of neural network parameters of the neural network using the noisy gradients; 
   wherein the correlation matrix used during the training of the neural network is determined by performing operations comprising:
 iteratively updating a current correlation matrix over a plurality of optimization iterations to optimize a utility metric, comprising, at each optimization iteration:
 determining a current noise multiplier that, if used in conjunction with the current correlation matrix during the training of the neural network, is predicted to cause the trained neural network to satisfy a data security criterion; 
 determining a current utility metric for the current correlation matrix based at least in part on the current noise multiplier; 
 determining gradients of the current utility metric with respect to the current correlation matrix; and 
 updating the current correlation matrix using the gradients of the current utility metric. 
 
   
     
     
         20 . The one or more non-transitory computer storage media storing instructions of  claim 19 , wherein the data security criterion is an (ϵ, δ)-differential privacy (DP) criterion, wherein ϵ is a target privacy budget parameter defining a bound on a privacy loss, and δ is a target privacy breach parameter defining a bound on a probability of a privacy loss exceeding the privacy budget parameter ϵ.