89
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Online Learning to Sample

      Preprint
      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Stochastic Gradient Descent (SGD) is one of the most widely used techniques for online optimization in machine learning. In this work, we accelerate SGD by adaptively learning how to sample the most useful training examples at each time step. First, we show that SGD can be used to learn the best possible sampling distribution of an importance sampling estimator. Second, we show that the sampling distribution of an SGD algorithm can be estimated online by incrementally minimizing the variance of the gradient. The resulting algorithm - called Adaptive Weighted SGD (AW-SGD) - maintains a set of parameters to optimize, as well as a set of parameters to sample learning examples. We show that AWSGD yields faster convergence in three different applications: (i) image classification with deep features, where the sampling of images depends on their labels, (ii) matrix factorization, where rows and columns are not sampled uniformly, and (iii) reinforcement learning, where the optimized and exploration policies are estimated at the same time, where our approach corresponds to an off-policy gradient algorithm.

          Related collections

          Author and article information

          Journal
          2015-06-30
          2016-03-15
          Article
          1506.09016
          e08370f2-b2be-406b-bbc8-21824f30d447

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Update: removed convergence theorem and proof as there is an error. Submitted to UAI 2016
          cs.LG cs.CV cs.NA math.OC stat.ML

          Numerical & Computational mathematics,Computer vision & Pattern recognition,Numerical methods,Machine learning,Artificial intelligence

          Comments

          Comment on this article