Method for machine learning with state information
AssigneeInternational Business Machines Corporation
InventorsElad Eliezer Hazan, Nimrod Megiddo
Life of this patent
Estimating the term…
Abstract
Methods, systems, and computer program products are provided for the online convex optimization problem, in which the decision maker has knowledge of the all past states and resulting cost functions for his previous choices and attempts to make a new choice that results in minimum regret. The method does not rely upon the structure of the cost function or the characterization of the states and takes advantage of the similarity between successive states to enable the method to converge to a reasonably optimal result.
Claims4
-14. (canceled)
A system for iteratively improving a chosen solution to an online convex optimization problem, the system executing procedures for:
- establishing a metric space having a diameter W as a subset of a d-dimensional Euclidean space (⊂Rd), wherein calculating a distance between any two members of the metric space is determined as a Euclidean distance function;
- collecting known information known by a decision maker at time T, the collection of known information comprising a set of past decisions x1, . . . , xt−1 made by a decision maker prior to time T, a set of state vectors k1, . . . , kt, and a sequence of T-1 convex functions of the form ƒt, each convex function mapping a convex set into a set R of real numbers (ƒt:
- →R) for t=1,2, . . . , T−1, wherein each state vector kt is a member of the metric space (kt∈) and D is a diameter of
- choosing a Lipschitz constant L for the metric space , wherein a worst case value of L-regret is at most
- O
- (
- WGL
- (
- 1
- +
- 2
- d
- +
- 2
- )
-
- D
- (
- 2
- d
- +
- 2
- )
-
- T
- 1
- -
- 1
- d
- +
- 2
- )
- ;
- selecting a state vector {tilde over (k)}t from said plurality of state vectors for which a distance between the selected state vector and each state vector from the plurality of state vectors is chosen to be closest to each state vector kt from among all state vectors k1, . . . , kt and is less than a threshold value determined as:
- ε=W(D/L)d+2)T−1/d+2);
- determining a cost associated with the state vector {tilde over (k)}t;
- determining a regret function as a difference between the cost associated with the state vector {tilde over (k)}t and a prior minimum cost function;
- and
- providing said regret function to a user.
A method for choosing a solution xt at time t(t=1,2, . . .) to an online convex optimization problem ,the method accepting εt−1, xt−1, the current state vector kt∈, and all previous state vectors k1, . . . , kt−1, wherein kt∈[0,1]d, wherein is a metric space having a distance function and a diameter W, the metric space being a subset of d-dimensional Euclidean space (⊂Rd), and wherein is a convex set with diameter D with the vectors xt∈ for t=1,2, . . . , T, the method comprising the steps of:
- choosing a Lipschitz-constant L for the metric space ;
- choosing a threshold value ε;
- setting =φ, wherein is a subset of ;
- setting xo to an arbitrary value for t=0;
- initializing an iteration value t equal to 1;
- and
- while t≦T executing the steps of:
- choosing the state {tilde over (k)}t that is closest to kt among all state vectors in by setting {tilde over (k)}t=arg min {∥k−kt∥:
- k∈};
- setting xt←({tilde over (k)}t) for t≠0;
- setting
- y
- ←
- ∏
- P
-
- (
- M
-
- (
- k
- ~
- t
- )
- -
- 1
- T
-
- ∇
- f
- t
-
- (
- M
-
- (
- k
- ~
- t
- )
- )
- )
- ,
- where
- Π92 denotes the projection operator into the convex set
- updating ({tilde over (k)}t)←y if ∥kt−kt∥≦ε,
- adding kt to the set and setting (kt)←y if ∥{tilde over (k)}t−kt>ε, and
- incrementing t by 1, wherein the worst case value of L-regret is at most
- O
- (
- WGL
- (
- 1
- +
- 2
- d
- +
- 2
- )
-
- D
- (
- 2
- d
- +
- 2
- )
-
- T
- 1
- -
- 1
- d
- +
- 2
- )
- ;
- and the threshold value is chosen to be the value ε=W(D/L)2/(d+2)T1/(d+2).
A computer program product comprising a computer useable medium having a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:
- define a metric space having a diameter D;
- define a set , wherein ⊂;
- define a convex compact set ⊂Rn having a diameter W, wherein the set is a feasible domain for solutions to an online convex optimization problem;
- define a mapping ut that maps every point in the set to a point in decision space ,
- accept as input Lipschitz-constant L for a metric space ;
- a time period T;
- a cost function ƒt−1;
- a current state vector kt∈, all previous state vectors k1, . . . , kt−1;
- and a threshold value , wherein kt∈[0,1]d;
- set as an initial condition xt←({tilde over (k)}t) for t≠0;
- set xo arbitrarily for t=0;
- calculate a state vector {tilde over (k)}t chosen to be closest to each state vector kt from among all state vectors in , wherein the state vector {tilde over (k)}t chosen to be closest to each state vector kt from among all state vectors in is calculated as {tilde over (k)}t=arg min{∥k−kt∥:k∈N};
- choose a vector y according to the criterion
- y
- ←
- ∏
- P
-
- (
- M
-
- (
- k
- ~
- t
- )
- -
- 1
- T
-
- ∇
- f
- t
-
- (
- M
-
- (
- k
- ~
- t
- )
- )
- )
- ,
- where Πρ is a projection operator into the convex set ,
- update ({tilde over (k)}t)←y if ∥{tilde over (k)}t−kt∥≦ε;
- and
- add kt to the set and setting (kt)←y if ∥{tilde over (k)}t−kt∥>ε;
- wherein the value of ε is ε=W(D/L)2/(d+2)T1/(d+2).
Dependencies are inferred from the claim text.