According to one embodiment of the present invention, a method for online convex optimization is provided. The method includes performing a step that relies on the selection of x at a time t (xt), where x is a variable involved with the step. A resulting cost (ƒt(xt)) is calculated that results from selecting xt when performing the step, where ƒt is a cost function. A minimum possible cost (ƒt(x*t)) associated with the selection of x* is then found and the difference between the resulting cost (ƒt(xt)) and the minimum possible cost (ƒt(x*t)) is determined. A direction of movement from xt to xt+1 is selected and a subsequent step that relies on the section of xt+1 is then performed.