Sparse variable optimization device, sparse variable optimization method, and sparse variable optimization program

1. A sparse variable optimization device comprising:

a gradient computation unit for computing a gradient of an objective function in a designated value of a variable;

an added variable selection unit for adding one of variables included in a variable set, to a nonzero variable set;

a variable optimization unit for optimizing a value of a variable to be optimized, for each variable included in the nonzero variable set;

a deleted variable selection unit for deleting a variable that, when deleted, causes a smallest increase of the objective function from among variables included in the nonzero variable set, from the nonzero variable set; and

an objective function evaluation unit for computing a value of the objective function for the variable to be optimized,

wherein the gradient computation unit computes the gradient of the objective function in the variable to be optimized, and

wherein the added variable selection unit adds a variable corresponding to a largest absolute value of the computed gradient from among the variables included in the variable set, to the nonzero variable set.

2. The sparse variable optimization device according to claim 1 , wherein the gradient computation unit computes the gradient of the objective function in the variable to be optimized, the objective function representing a logistic regression model, and

wherein the deleted variable selection unit deletes the variable that causes the smallest increase of the objective function, from the nonzero variable set.

3. The sparse variable optimization device according to claim 1 , wherein the gradient computation unit uses a covariance function as the objective function, and computes the gradient of the objective function in an off-diagonal element of a precision matrix which is an inverse of a covariance matrix,

wherein the variable optimization unit optimizes the off-diagonal element of the precision matrix, for each off-diagonal nonzero component of the precision matrix,

wherein the deleted variable selection unit sets a nonzero component that, when deleted, causes the smallest increase of the objective function from among off-diagonal nonzero components of the precision matrix, to zero, and

wherein the objective function evaluation unit computes the value of the objective function for the off-diagonal element of the precision matrix.

4. The sparse variable optimization device according to claim 1 , comprising

an optimality determination unit for determining that the variable to be optimized is optimized, in the case where the largest absolute value of the computed gradient is less than a predetermined threshold.

5. The sparse variable optimization device according to claim 2 , comprising

an optimality determination unit for determining that the variable to be optimized is optimized, in the case where the largest absolute value of the computed gradient is less than a predetermined threshold.

6. The sparse variable optimization device according to claim 3 , comprising

an optimality determination unit for determining that the variable to be optimized is optimized, in the case where the largest absolute value of the computed gradient is less than a predetermined threshold.

7. A sparse variable optimization method comprising:

computing a gradient of an objective function in a designated value of a variable;

adding one of variables included in a variable set, to a nonzero variable set;

optimizing a value of a variable to be optimized, for each variable included in the nonzero variable set;

deleting a variable that, when deleted, causes a smallest increase of the objective function from among variables included in the nonzero variable set, from the nonzero variable set; and

computing a value of the objective function for the variable to be optimized,

wherein when computing the gradient, the gradient of the objective function in the variable to be optimized is computed, and

wherein a variable corresponding to a largest absolute value of the computed gradient from among the variables included in the variable set is added to the nonzero variable set.

8. The sparse variable optimization method according to claim 7 , wherein when computing the gradient, the gradient of the objective function in the variable to be optimized is computed, the objective function representing a logistic regression model, and

wherein the variable that causes the smallest increase of the objective function is deleted from the nonzero variable set.

9. A non-transitory computer readable information recording medium storing a sparse variable optimization program that, when executed by a processor, performs a method for:

computing a gradient of an objective function in a designated value of a variable;

adding one of variables included in a variable set, to a nonzero variable set;

optimizing a value of a variable to be optimized, for each variable included in the nonzero variable set;

deleting a variable that, when deleted, causes a smallest increase of the objective function from among variables included in the nonzero variable set, from the nonzero variable set; and

computing a value of the objective function for the variable to be optimized,

wherein when computing the gradient, the gradient of the objective function in the variable to be optimized is computed, and

wherein a variable corresponding to a largest absolute value of the computed gradient from among the variables included in the variable set is added to the nonzero variable set.

10. The non-transitory computer readable information recording medium according to claim 9 , wherein when computing the gradient, the gradient of the objective function in the variable to be optimized is computed, the objective function representing a logistic regression model, and

wherein the variable that causes the smallest increase of the objective function is deleted from the nonzero variable set.