High-performance block coordinate based on L1 regularized random binning

Patent metadata

Field	Value
Publication number	US-10817294-B2
Application number	US-201715457526-A
Country	US
Kind code	B2
Filing date	Mar 13, 2017
Priority date	Mar 13, 2017
Publication date	Oct 27, 2020
Grant date	Oct 27, 2020

Abstract

A block coordinate descent method, system, and computer program product for partitioning a global feature matrix into blocks, each node of the nodes of the blocks having a block size of a number of the blocks over a number of the nodes, selecting, at each node, a subset of the blocks from the blocks, and in one of the nodes, launching a thread to simultaneously update a closed-form solution by minimizing a single coordinate in one of the blocks.

First claim

What is claimed is:

1. A computer-implemented block coordinate descent (BCD) method for accelerating a large-scale kernel machine with L1-regularized random binning on one or more multicore systems, the method comprising:
providing a high-performance BCD using a hybrid approach including two-level parallelism by fully exploiting sparse structure patterns of a random binning (RB) feature matrix by:
partitioning a global feature matrix into blocks, each node of a plurality of nodes of the blocks having a block size represented by a number of the blocks divided by a number of the nodes, where the plurality of nodes are on the one or more multicore systems;
selecting, at each node, a subset of the blocks from the blocks; and
in one of the nodes, launching a thread to simultaneously update a closed-form solution by minimizing a single coordinate in one block of the blocks such that the large-scale kernel machine is accelerated with L1-regularized random binning,

wherein the launching the thread includes using a function to update a prediction vector for a difference with respect to the closed-form solution.

2. The computer-implemented method of claim 1 , wherein the launching launches a plurality of threads to concurrently compute all coordinates in one of the blocks while considering conflict due to separable sparse structuring.

3. The computer-implemented method of claim 1 , further comprising searching for a step size for the closed-form solution using a line search method.

4. The computer-implemented method of claim 3 , further comprising iteratively updating model parameters and the prediction vector.

5. The computer-implemented method of claim 3 , further comprising iteratively updating model parameters and the prediction vector by performing the selecting continuously until the closed-form solution converges.

6. The computer-implemented method of claim 1 , embodied in a cloud-computing environment.

7. A computer program product for block coordinate descent (BCD) for accelerating a large-scale kernel machine with L1-regularized random binning on one or more multicore systems, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform:
providing a high-performance BCD using a hybrid approach including two-level parallelism by fully exploiting sparse structure patterns of a random binning (RB) feature matrix by:
partitioning a global feature matrix into blocks, each node of a plurality of nodes of the blocks having a block size represented by a number of the blocks divided by a number of the nodes, where the plurality of nodes are on the one or more multicore systems;
selecting, at each node, a subset of the blocks from the blocks; and
in one of the nodes, launching a thread to simultaneously update a closed-form solution by minimizing a single coordinate in one block of the blocks such that the large-scale kernel machine is accelerated with L1-regularized random binning,

wherein the launching the thread includes using a function to update a prediction vector for a difference with respect to the closed-form solution.

8. The computer program product of claim 7 , wherein the launching launches a plurality of threads to concurrently compute all coordinates in one of the blocks while considering conflict due to separable sparse structuring.

9. The computer program product of claim 7 , further comprising searching for a step size for the closed-form solution using a line search method.

10. The computer program product of claim 9 , further comprising iteratively updating model parameters and the prediction vector.

11. The computer program product of claim 9 , further comprising iteratively updating model parameters and the prediction vector by performing the selecting continuously until the closed-form solution converges.

12. A block coordinate descent (BCD) system for accelerating a large-scale kernel machine with L1-regularized random binning on one or more multicore systems, said system comprising:
a processor; and
a memory, the memory storing instructions to cause the processor to providing a high-performance BCD using a hybrid approach including two-level parallelism by fully exploiting sparse structure patterns of a random binning (RB) feature matrix by: performing:
partitioning a global feature matrix into blocks, each node of a plurality of nodes of the blocks having a block size represented by a number of the blocks divided by a number of the nodes, where the plurality of nodes are on the one or more multicore systems;
selecting, at each node, a subset of the blocks from the blocks; and
in one of the nodes, launching a thread to simultaneously update a closed-faun solution by minimizing a single coordinate in one block of the blocks such that the large-scale kernel machine is accelerated with L1-regularized random binning,

wherein the launching the thread includes using a function to update a prediction vector for a difference with respect to the closed-form solution.

13. The system of claim 12 , wherein the launching launches a plurality of threads to concurrently compute all coordinates in one of the blocks while considering conflict due to separable sparse structuring.

14. The system of claim 12 , further comprising searching for a step size for the closed-form solution using a line search method.

15. The system of claim 12 , embodied in a cloud-computing environment.

16. The computer-implemented method of claim 1 , wherein the hybrid two-level parallelism comprises distributed computing and shared-memory computing.

Assignees

• IBM

Inventors

• Fong Liana Liyow
• Tan Wei
• Witbrock Michael
• Wu Lingfei

Classifications

• G06F9/30036

  Instructions to perform operations on packed data, e.g. vector, tile or matrix operations · CPC title

• G06N20/10 Primary

  using kernel methods, e.g. support vector machines [SVM] · CPC title

• G06V10/94

  Hardware or software architectures specially adapted for image or video understanding · CPC title

• G06N20/00

  Machine learning · CPC title

• G06F9/4843

  by program, e.g. task dispatcher, supervisor, operating system · CPC title