Subgradient Methods for Nonsmooth Sample Average Approximation

Source: arxiv.org/abs/2611.02534

Xi Chen, Ouqi Fu, Jiyuan Tu, Yichen Zhang

arXivarxiv/2611.02534Nov 2, 2026stat.COscore 0

We study direct subgradient methods for nonsmooth sample average approximation (SAA). Subgradient descent and Nesterov acceleration with constant step sizes attain polynomial and geometric rates matching their smooth counterparts. After $O(\log n)$ full-batch updates, where $n$ is the sample size, the computed solution has the same first-order expansion and limiting distribution as an SAA solution, even when the iterates do not converge. A bound on subgradient increments transfers population regularity to the sample objective, controls the algorithmic trajectory, and identifies the leading…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.02534
curl -X POST /api/v1/records/arxiv/2611.02534/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.02534/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'