Sampled-Max Subgradient Method for Convex Finite-Max Optimization
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.32872
curl -X POST /api/v1/records/arxiv/2609.32872/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.32872/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'