Patent Document ID: 7870082
Application ID: 11759505
Patent Flag: 1

Claim One:
1. A data processing system for iteratively improving a chosen solution to an online convex optimization problem, the data processing system executing on one or more processors procedures for: establishing a metric space having a diameter W as a subset of a d-dimensional Euclidean space ( ⊂ R d ), wherein calculating a distance between any two members of the metric space is determined as a Euclidean distance function; collecting information known by a decision maker at time T, the collection of known information comprising a set of past decisions x 1 ,. .. , x t−1 , made by a decision maker prior to time T, a set of state vectors k 1 ,. .. , k t , 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 k t is a member of the metric space (k t ε ) 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 k t from among all state vectors k 1 ,. .. , k t and is less than a threshold value E determined as: 
 ε= W ( D/L ) 2/(d+2) T −1/(d+2) ; determining a cost associated with the state vector {tilde over (k)} t ; determining, in the one or more processors, 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 from the data processing system via an input/output device said regret function to a user.