{
  "id": "2110.11721",
  "version": "v2",
  "published": "2021-10-22T11:49:15.000Z",
  "updated": "2022-04-03T07:53:39.000Z",
  "title": "Projection-Free Algorithm for Stochastic Bi-level Optimization",
  "authors": [
    "Zeeshan Akhtar",
    "Amrit Singh Bedi",
    "Srujan Teja Thomdapu",
    "Ketan Rajawat"
  ],
  "comment": "34 Pages",
  "categories": [
    "math.OC",
    "cs.CC",
    "cs.LG"
  ],
  "abstract": "This work presents the first projection-free algorithm to solve stochastic bi-level optimization problems, where the objective function depends on the solution of another stochastic optimization problem. The proposed $\\textbf{S}$tochastic $\\textbf{Bi}$-level $\\textbf{F}$rank-$\\textbf{W}$olfe ($\\textbf{SBFW}$) algorithm can be applied to streaming settings and does not make use of large batches or checkpoints. The sample complexity of SBFW is shown to be $\\mathcal{O}(\\epsilon^{-3})$ for convex objectives and $\\mathcal{O}(\\epsilon^{-4})$ for non-convex objectives. Improved rates are derived for the stochastic compositional problem, which is a special case of the bi-level problem, and entails minimizing the composition of two expected-value functions. The proposed $\\textbf{S}$tochastic $\\textbf{C}$ompositional $\\textbf{F}$rank-$\\textbf{W}$olfe ($\\textbf{SCFW}$) is shown to achieve a sample complexity of $\\mathcal{O}(\\epsilon^{-2})$ for convex objectives and $\\mathcal{O}(\\epsilon^{-3})$ for non-convex objectives, at par with the state-of-the-art sample complexities for projection-free algorithms solving single-level problems. We demonstrate the advantage of the proposed methods by solving the problem of matrix completion with denoising and the problem of policy value evaluation in reinforcement learning.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-04-03T07:53:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sample complexity",
      "stochastic bi-level optimization problems",
      "non-convex objectives",
      "projection-free algorithms solving single-level problems",
      "stochastic optimization problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}