{
  "id": "2409.19200",
  "version": "v2",
  "published": "2024-09-28T01:21:03.000Z",
  "updated": "2025-02-06T23:24:07.000Z",
  "title": "Faster Acceleration for Steepest Descent",
  "authors": [
    "Site Bai",
    "Brian Bullins"
  ],
  "categories": [
    "math.OC",
    "cs.LG",
    "stat.ML"
  ],
  "abstract": "Recent advances (Sherman, 2017; Sidford and Tian, 2018; Cohen et al., 2021) have overcome the fundamental barrier of dimension dependence in the iteration complexity of solving $\\ell_\\infty$ regression with first-order methods. Yet it remains unclear to what extent such acceleration can be achieved for general $\\ell_p$ smooth functions. In this paper, we propose a new accelerated first-order method for convex optimization under non-Euclidean smoothness assumptions. In contrast to standard acceleration techniques, our approach uses primal-dual iterate sequences taken with respect to $\\textit{differing}$ norms, which are then coupled using an $\\textit{implicitly}$ determined interpolation parameter. For $\\ell_p$ norm smooth problems in $d$ dimensions, our method provides an iteration complexity improvement of up to $O(d^{1-\\frac{2}{p}})$ in terms of calls to a first-order oracle, thereby allowing us to circumvent long-standing barriers in accelerated non-Euclidean steepest descent.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2025-02-06T23:24:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "faster acceleration",
      "primal-dual iterate sequences taken",
      "first-order method",
      "standard acceleration techniques",
      "accelerated non-euclidean steepest descent"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}