Sampled-Max Subgradient Method for Convex Finite-Max Optimization
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(ε−2) subgradient queries and, when k components remain nearly active in that set, Õ((N/k)ε−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×105 and 5×106 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.
Related
- A Minimax Analysis of the Last Iterate of the SubGradient Method in Finite Dimension
- Stabilized SQP Method for Convex Piecewise Linear-Quadratic Composite Optimization Problems
- A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in p-norm geometry
- An Inexact Augmented Lagrangian Method for (L0, L1)-Smooth Convex Optimization
- Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
BibTeX
@misc{gladin2026sampledmax,
title = {{Sampled-Max Subgradient Method for Convex Finite-Max Optimization}},
author = {Egor Gladin and Anna Popova and Georgii Babinskii},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32872},
eprint = {2609.32872},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32872},
}
RIS
TY - UNPB
TI - Sampled-Max Subgradient Method for Convex Finite-Max Optimization
AU - Egor Gladin
AU - Anna Popova
AU - Georgii Babinskii
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32872
UR - https://arxiv.org/abs/2609.32872
AB - 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(ε^−2) subgradient queries and, when k components remain nearly active in that set, Õ((N/k)ε^−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×10^5 and 5×10^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.
ER -