{
  "id": "2506.20630",
  "version": "v1",
  "published": "2025-06-25T17:26:02.000Z",
  "updated": "2025-06-25T17:26:02.000Z",
  "title": "First-order methods for stochastic and finite-sum convex optimization with deterministic constraints",
  "authors": [
    "Zhaosong Lu",
    "Yifeng Xiao"
  ],
  "comment": "41 pages",
  "categories": [
    "math.OC",
    "cs.LG",
    "cs.NA",
    "math.NA"
  ],
  "abstract": "In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an $\\epsilon$-$expectedly\\ feasible\\ stochastic\\ optimal$ solution, in which the expected constraint violation and expected optimality gap are both within a prescribed tolerance $\\epsilon$. However, in many practical applications, constraints must be nearly satisfied with certainty, rendering such solutions potentially unsuitable due to the risk of substantial violations. To address this issue, we propose stochastic first-order methods for finding an $\\epsilon$-$surely\\ feasible\\ stochastic\\ optimal$ ($\\epsilon$-SFSO) solution, where the constraint violation is deterministically bounded by $\\epsilon$ and the expected optimality gap is at most $\\epsilon$. Our methods apply an accelerated stochastic gradient (ASG) scheme or a modified variance-reduced ASG scheme $only\\ once$ to a sequence of quadratic penalty subproblems with appropriately chosen penalty parameters. We establish first-order oracle complexity bounds for the proposed methods in computing an $\\epsilon$-SFSO solution. As a byproduct, we also derive first-order oracle complexity results for sample average approximation method in computing an $\\epsilon$-SFSO solution of the stochastic optimization problem using our proposed methods to solve the sample average problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-06-25T17:26:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "first-order methods",
      "deterministic constraints",
      "first-order oracle complexity bounds",
      "stochastic",
      "first-order oracle complexity results"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 41,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}