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

Claim 7:
8. 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 solution to an objective function problem, min
    
     A
     ,
     B
    
   
   
    F
    ⁡
    (
    
     A
     ,
     B
    
    )
   
  
  =
  
   
    
     ∑
     
      i
      ,
      
       j
        
       ∈
        
       I
      
     
    
    
     
      (
      
       
        x
        ij
       
       -
       
        
         A
         i
        
        ⁢
        
         B
         j
        
       
      
      )
     
     2
    
   
   +
   
    
     ∑
     i
    
    
     λ
     ⁢
     
      
       
       
        A
        i
       
       
      
      2
     
    
   
   +
   
    
     ∑
     i
    
    
     λ
     ⁢
     
      
       
       
        B
        j
       
       
      
      2, for completing an incomplete data matrix X having N×D dimensions, where X is approximated by a product of matrices A and B, and where Ai represents a sub-matrix of the matrix A that has the same number of columns as the matrix A, and Bj represents a sub-matrix of the matrix B that has the same number or rows as the matrix B:
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 the computations comprises updating Ai and Bj in iterations by a slave computer based on the following equation:, (
   
    
     A
     i
     t
    
    ,
    
     B
     j
     t
    
   
   )
  
  =
  
   
    
     arg
     ⁢
     min
    
    
     
      A
      i
     
     ,
     
      B
      j
     
    
   
   ⁢
   
    {
    
     
      
       (
       
        
         x
         ij
        
        -
        
         
          A
          i
         
         ⁢
         
          B
          j
         
        
       
       )
      
      2
     
     +
     
      
       λ
       t
      
      ⁢
      
       
        
        
         
          A
          i
         
         -
         
          A
          i
          
           t
           -
           1
          
         
        
        
       
       2
      
     
     +
     
      
       λ
       t
      
      ⁢
      
       
        
        
         
          B
          j
         
         -
         
          B
          j
          
           t
           -
           1
          
         
        
        
       
       2
      
     
    
    }, where λt is a sequence of step sizes, and t is a current number of iterations.