eduzhai > Applied Sciences > Engineering >

Sublinear Regret with Barzilai-Borwein Step Sizes

  • king
  • (0) Download
  • 20210506
  • Save

... pages left unread,continue reading

Document pages: 8 pages

Abstract: This paper considers the online scenario using the Barzilai-BorweinQuasi-Newton Method. In an online optimization problem, an online agent uses acertain algorithm to decide on an objective at each time step after which apossible loss is encountered. Even though the online player will ideally try tomake the best decisions possible at each time step, there is a notion of regretassociated with the player s decisions. This study examines the regret of anonline player using optimization methods like the Quasi-Newton methods, due totheir fast convergent properties. The Barzilai-Borwein (BB) gradient method ischosen in this paper over other Quasi-Newton methods such as theBroyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm because of its lesscomputational complexities. In addition, the BB gradient method is suitable forlarge-scale optimization problems including the online optimization scenariopresented in this paper. To corroborate the effectiveness of theBarzilai-Borwein (BB) gradient algorithm, a greedy online gradient algorithm isused in this study based on the two BB step sizes. Through a rigorous regretanalysis on the BB step sizes, it is established that the regret obtained fromthe BB algorithm is sublinear in time. Moreover, this paper shows that theaverage regret using the online BB algorithm approaches zero without assumingstrong convexity on the cost function to be minimized.

Please select stars to rate!

         

0 comments Sign in to leave a comment.

    Data loading, please wait...
×