  This paper considers the online scenario using the Barzilai-Borwein
Quasi-Newton Method. In an online optimization problem, an online agent uses a
certain algorithm to decide on an objective at each time step after which a
possible loss is encountered. Even though the online player will ideally try to
make the best decisions possible at each time step, there is a notion of regret
associated with the player's decisions. This study examines the regret of an
online player using optimization methods like the Quasi-Newton methods, due to
their fast convergent properties. The Barzilai-Borwein (BB) gradient method is
chosen in this paper over other Quasi-Newton methods such as the
Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm because of its less
computational complexities. In addition, the BB gradient method is suitable for
large-scale optimization problems including the online optimization scenario
presented in this paper. To corroborate the effectiveness of the
Barzilai-Borwein (BB) gradient algorithm, a greedy online gradient algorithm is
used in this study based on the two BB step sizes. Through a rigorous regret
analysis on the BB step sizes, it is established that the regret obtained from
the BB algorithm is sublinear in time. Moreover, this paper shows that the
average regret using the online BB algorithm approaches zero without assuming
strong convexity on the cost function to be minimized.
