{
  "id": "1801.03600",
  "version": "v1",
  "published": "2018-01-11T00:45:49.000Z",
  "updated": "2018-01-11T00:45:49.000Z",
  "title": "Multi-Level Stochastic Gradient Methods for Nested Compositon Optimization",
  "authors": [
    "Shuoguang Yang",
    "Mengdi Wang",
    "Ethan X. Fang"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "Stochastic gradient methods are scalable for solving large-scale optimization problems that involve empirical expectations of loss functions. Existing results mainly apply to optimization problems where the objectives are one- or two-level expectations. In this paper, we consider the multi-level compositional optimization problem that involves compositions of multi-level component functions and nested expectations over a random path. It finds applications in risk-averse optimization and sequential planning. We propose a class of multi-level stochastic gradient methods that are motivated from the method of multi-timescale stochastic approximation. First we propose a basic $T$-level stochastic compositional gradient algorithm, establish its almost sure convergence and obtain an $n$-iteration error bound $\\cO (n^{-1/2^T})$. Then we develop accelerated multi-level stochastic gradient methods by using an extrapolation-interpolation scheme to take advantage of the smoothness of individual component functions. When all component functions are smooth, we show that the convergence rate improves to $\\cO(n^{-4/(7+T)})$ for general objectives and $\\cO (n^{-4/(3+T)})$ for strongly convex objectives. We also provide almost sure convergence and rate of convergence results for nonconvex problems. The proposed methods and theoretical results are validated using numerical experiments.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-11T00:45:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "multi-level stochastic gradient methods",
      "nested compositon optimization",
      "component functions",
      "level stochastic compositional gradient algorithm",
      "multi-level compositional optimization problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}