Subgradient Methods for Nonsmooth Sample Average Approximation
Abstract
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 random term. The bound covers convex piecewise linear scenario costs, including two-stage stochastic linear programs with fixed recourse. Moreau smoothing displaces the population solution at first order and changes the limiting distribution of the computed solution. An explicit shift of the residual removes the first-order displacement and improves the expansion remainder. For sparse decisions, restricted increment bounds give convergence, support recovery, and expansions for proximal subgradient descent and iterative hard thresholding.
Related
- Projected Subgradient Methods for a Class of Nonsmooth and Nonconvex Optimization Problems
- Retraction-Free Nonsmooth Optimization on the Stiefel Manifold: Subgradient and Proximal Landing Methods
- Towards Optimal Inventory Control under Censored Demand: A Biased Sample-Average Approximation Approach
- Sample average approximation of multiobjective stochastic optimization problems with application in insurance
- Nonminimizing Attractors of Stochastic Subgradient Methods on Semialgebraic Functions
BibTeX
@misc{chen2026subgradient,
title = {{Subgradient Methods for Nonsmooth Sample Average Approximation}},
author = {Xi Chen and Ouqi Fu and Jiyuan Tu and Yichen Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02534},
eprint = {2611.02534},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02534},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Subgradient Methods for Nonsmooth Sample Average Approximation
AU - Xi Chen
AU - Ouqi Fu
AU - Jiyuan Tu
AU - Yichen Zhang
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02534
UR - https://arxiv.org/abs/2611.02534
AB - 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 random term. The bound covers convex piecewise linear scenario costs, including two-stage stochastic linear programs with fixed recourse. Moreau smoothing displaces the population solution at first order and changes the limiting distribution of the computed solution. An explicit shift of the residual removes the first-order displacement and improves the expansion remainder. For sparse decisions, restricted increment bounds give convergence, support recovery, and expansions for proximal subgradient descent and iterative hard thresholding.
ER -