Systems and Methods for Evaluating a Loss Function or a Gradient of a Loss Function via Dual Decomposition

A computer-implemented method for evaluating a loss function or a gradient of the loss function, the method comprising:

• partitioning, by a computing system that includes one or more computing devices, a weight matrix into a plurality of blocks, the weight matrix corresponding to a scoring function;
• identifying, by the computing system, a first set of labels for each of the plurality of blocks, the first set of labels being associated with a score greater than a first threshold;
• constructing, by the computing system, a sparse approximation of a scoring vector for each of the plurality of blocks based at least in part on the first set of labels;
• determining, by the computing system, a correction value for each sparse approximation of the scoring vector for each of the plurality of blocks;
• and
• determining, by the computing system, an approximation of a loss or a gradient of a loss associated with the scoring function by evaluating a decomposed loss function or a gradient of the decomposed loss function based at least in part on the sparse approximation of the scoring vector for each of the plurality of blocks and the correction value associated with the sparse approximation of the scoring vector.