{
  "id": "2202.04545",
  "version": "v1",
  "published": "2022-02-09T16:16:07.000Z",
  "updated": "2022-02-09T16:16:07.000Z",
  "title": "Lower Complexity Bounds for Minimizing Regularized Functions",
  "authors": [
    "Nikita Doikov"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "In this paper, we establish lower bounds for the oracle complexity of the first-order methods minimizing regularized convex functions. We consider the composite representation of the objective. The smooth part has H\\\"older continuous gradient of degree $\\nu \\in [0, 1]$ and is accessible by a black-box local oracle. The composite part is a power of a norm. We prove that the best possible rate for the first-order methods in the large-scale setting for Euclidean norms is of the order $O(k^{- p(1 + 3\\nu) / (2(p - 1 - \\nu))})$ for the functional residual, where $k$ is the iteration counter and $p$ is the power of regularization. Our formulation covers several cases, including computation of the Cubically regularized Newton step by the first-order gradient methods, in which case the rate becomes $O(k^{-6})$. It can be achieved by the Fast Gradient Method. Thus, our result proves the latter rate to be optimal. We also discover lower complexity bounds for non-Euclidean norms.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-02-09T16:16:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lower complexity bounds",
      "minimizing regularized functions",
      "first-order methods",
      "methods minimizing regularized convex functions",
      "fast gradient method"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}