{
  "abstract": "We study the Sampled-Max Subgradient Method (SMax-SGM) for large convex finite-max problems. Each iteration maximizes over a fresh random subset of the $N$ components and takes one subgradient of the sampled maximizer. The method is therefore stochastic subgradient descent on a sampled-max surrogate. We bound the surrogate error by an average-top-$k$ gap plus the probability of missing all top-$k$ components. A localization argument requires these quantities only on a near-optimal sublevel set. Under a bounded subgradient-moment assumption, this yields $O(\\varepsilon^{-2})$ subgradient queries and, when $k$ components remain nearly active in that set, $\\widetilde O((N/k)\\varepsilon^{-2})$ component-value queries, capped by the full-scan cost. Conversely, a one-dimensional affine construction shows that $Ω(N/k)$ component-value queries can be necessary even when the average-top-$k$ gap vanishes everywhere and subgradient queries are unlimited. A tensor-grid specialization explains when the subset size can become independent of grid cardinality. Experiments on finite maxima with $2\\times10^5$ and $5\\times10^6$ components show that, under the reported protocols, SMax-SGM reaches a 5% numerical-reference gap with fewer component-value queries and lower optimizer time than each comparison method that reaches the target.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.32872",
  "author_total": 3,
  "authors": [
    {
      "name": "Egor Gladin"
    },
    {
      "name": "Anna Popova"
    },
    {
      "name": "Georgii Babinskii"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/dtp6tgh55ds73.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.32872",
  "fulltext_url": null,
  "id": "dtp6tgh55ds73",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.32872",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.OC"
    ],
    [
      "openalex",
      "1702|Stochastic Gradient Optimization Techniques"
    ]
  ],
  "openalex": "W7214732083",
  "pdf_url": "https://arxiv.org/pdf/2609.32872",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-26",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/dtp6tgh55ds73.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:25:17Z",
      "native_id": "2609.32872",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.32872"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "Sampled-Max Subgradient Method for Convex Finite-Max Optimization",
  "title_text": "Sampled-Max Subgradient Method for Convex Finite-Max Optimization",
  "type": "preprint",
  "updated_at": "2026-10-30T12:25:17Z",
  "url": "https://research.draconitic.com/paper/dtp6tgh55ds73",
  "venue": "arXiv",
  "versions": []
}