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

Claim 0:
1. A system comprising:
a network of computers comprising
a master computer, and
two or more slave computers,

wherein for a machine learning problem that is partitioned into a number of correlated NP hard non-convex optimization sub-problems, the machine learning problem comprising 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, the master computer being configured to store tasks associated with the machine learning problem, and each of the slave computers being assigned one of the NP hard non-convex optimization sub-problems and being configured to:
store variables or parameters or both associated with the assigned NP hard non-convex optimization sub-problem;
query information about one or more tasks stored by the master computer without causing conflict with other slave computers with regard to the information; and
solve 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 current number of iterations.