{"id":"arxiv/2609.32872","url":"https://arxiv.org/abs/2609.32872","tags":["math.OC"],"score":0,"title":"Sampled-Max Subgradient Method for Convex Finite-Max Optimization","domain":"math.OC","source":"arxiv","authors":["Egor Gladin","Anna Popova","Georgii Babinskii"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{}}