Online Learning on a Continuum
Walid Krichene

Citation
Walid Krichene. "Online Learning on a Continuum". Talk or presentation, 28, May, 2015.

Abstract
We consider an online learning problem on a continuum. A decision maker is given a compact feasible set S, and chooses, at each iteration, a distribution over S, then discovers a loss function defined on S. This model has applications ranging from player dynamics to portfolio optimization and machine learning. We first review existing methods for learning on a continuum. Then we propose a new method which relaxes the convexity assumptions on the feasible set and the losses. We view the problem as an online optimization problem on L^2(S), the space of Lebesgue-continuous distributions on S. We prove a general regret bound for the dual averaging method on L^2(S), then prove that dual averaging with omega-potentials (a class of regularizers) achieves sublinear regret when S is uniformly fat (a condition weaker than convexity). We give numerical examples to illustrate these results.

Electronic downloads


Internal. This publication has been marked by the author for FORCES-only distribution, so electronic downloads are not available without logging in.
Citation formats  
  • HTML
    Walid Krichene. <a
    href="http://www.cps-forces.org/pubs/64.html"
    ><i>Online Learning on a
    Continuum</i></a>, Talk or presentation,  28,
    May, 2015.
  • Plain text
    Walid Krichene. "Online Learning on a Continuum".
    Talk or presentation,  28, May, 2015.
  • BibTeX
    @presentation{Krichene15_OnlineLearningOnContinuum,
        author = {Walid Krichene},
        title = {Online Learning on a Continuum},
        day = {28},
        month = {May},
        year = {2015},
        abstract = {We consider an online learning problem on a
                  continuum. A decision maker is given a compact
                  feasible set S, and chooses, at each iteration, a
                  distribution over S, then discovers a loss
                  function defined on S. This model has applications
                  ranging from player dynamics to portfolio
                  optimization and machine learning. We first review
                  existing methods for learning on a continuum. Then
                  we propose a new method which relaxes the
                  convexity assumptions on the feasible set and the
                  losses. We view the problem as an online
                  optimization problem on L^2(S), the space of
                  Lebesgue-continuous distributions on S. We prove a
                  general regret bound for the dual averaging method
                  on L^2(S), then prove that dual averaging with
                  omega-potentials (a class of regularizers)
                  achieves sublinear regret when S is uniformly fat
                  (a condition weaker than convexity). We give
                  numerical examples to illustrate these results.},
        URL = {http://cps-forces.org/pubs/64.html}
    }
    

Posted by Carolyn Winter on 10 Jun 2015.
Groups: forces
For additional information, see the Publications FAQ or contact webmaster at cps-forces org.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.