Patent ID: 11861466
Assignee: GOOGLE LLC
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 11:
12. A computer implemented method comprising:
for a machine learning problem that is partitioned into a number of correlated NP hard non-convex optimization sub-problems, wherein the machine learning problem comprises determining a minimum of an objective function, R
      ⁡
      (
      w
      )
     
     =
     
     
      
       ∑
       
        i
        =
        1
       
       n
      
       
      
       L
       ⁡
       (
       
        〈
        
         
          
           y
           i
          
          ⁢
          
           x
           i
          
         
         ,
         w
        
        〉
       
       )
      
     
    
   
  
  
   
    
     =
     
     
      
       ∑
       
        i
        =
        1
       
       n
      
       
      
       L
       ⁡
       (
       
        
         ∑
         
          j
          =
          1
         
         d
        
         
        
         
          y
          i
         
         ⁢
         
          x
          ij
         
         ⁢
         
          w
          j
         
        
       
       ), for binary classification problem that has a data set, X
   =
   
    
     (
     
      
       
        
         x
         
          1
          ⁢
          1
         
        
       
       
        
         x
         
          1
          ⁢
          2
         
        
       
       
        …
       
       
        
         x
         
          1
          ⁢
          D
         
        
       
      
      
       
        
         x
         
          2
          ⁢
          1
         
        
       
       
        
         x
         
          2
          ⁢
          2
         
        
       
       
        …
       
       
        
         x
         
          2
          ⁢
          D
         
        
       
      
      
       
        ∶
       
       
        ∶
       
       
        …
       
       
        ∶
       
      
      
       
        
         x
         
          N
          ⁢
          1
         
        
       
       
        
         x
         
          N
          ⁢
          2
         
        
       
       
        …
       
       
        
         x
         ND
        
       
      
     
     )
    
    =
    
     (
     
      
       
        
         x
         1
        
       
      
      
       
        
         x
         2
        
       
      
      
       
        ∶
       
      
      
       
        
         x
         N
        
       
      
     
     )
    
   
  
  ,, labels y={y1, . . . , yn}∈{+1, −1}n and parameter w=(w1 w2 . . . wD)T;
storing, by a master computer, tasks associated with the machine learning problem; and
for each of multiple slave computers being assigned a respective NP hard non-convex optimization sub-problem of the correlated NP hard non-convex optimization sub-problems;
storing variables or parameters or both associated with the assigned NP hard non-convex optimization sub-problem;
querying information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; and solving the assigned NP hard non-convex optimization sub-problem, comprising performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned NP hard non-convex optimization sub-problem, wherein performing computations to update i) the queried information about the one or more tasks, and ii) the variables or parameters or both of the assigned correlated NP hard sub-problem comprises updating a sub-group of parameters wsp in iterations by a slave computer according to the following equation:, w
   
    S
    p
   
   t
  
  =
  
   
    
     arg
     ⁢
     min
    
    
     w
     
      S
      p
     
    
   
   ⁢
   
    
     {
     
      
       
        ∑
        
         i
          
         ∈
         
          I
          p
         
        
       
       
        L
        ⁡
        (
        
         
          
           ∑
           
            j
             
            ∈
             
            
             S
             p
            
           
          
          
           
            y
            i
           
           ⁢
           
            x
            ij
           
           ⁢
           
            w
            j
           
          
         
         +
         
          
           ∑
           
            j
             
            ∉
            
             S
             p
            
           
          
          
           
            y
            i
           
           ⁢
           
            x
            ij
           
           ⁢
           
            w
            j
            
             t
             -
             1
            
           
          
         
        
        )
       
      
      +
      
       
        λ
        t
       
       ⁢
       
        
         
         
          
           w
           
            S
            p
           
          
          -
          
           w
           
            S
            p
           
           
            t
            -
            1
           
          
         
         
        
        2
       
      
     
     }
    
    ., where Sp is a sub-group of 1, . . . , D, t is a current iteration, and L is a loss function of the binary classification.