On rates of convergence for sample average approximations without smoothness
Not on the map. Why?
Abstract (arXiv)
Sample average approximation (SAA) replaces an intractable expected objective by an empirical average and is a basic device of modern stochastic optimization. We develop a rate theory for optimal values and empirical varepsilon-minimizers that does not assume continuity, lower semicontinuity, or smooth perturbation structure of the sample objectives. Working on ℓ∞(X) with the Hoffmann--Jorgensen outer-probability formalism, we show that uniform control of the empirical objective process transfers deterministically to convergence rates for optimal values, excess risks of empirical varepsilon-minimizers, and, under a sharp-growth condition, distances to the expected objective solution set. Combined with the directional differentiability of the infimum functional, this yields weak limits for empirical optimal values at the n-1/2 scale. Combined with LILs and maximal inequalities, it yields outer almost-sure and outer-mean rates. The definability, envelope, and VC-subgraph hypotheses are verified for definable discontinuous or non-Lipschitz classes arising in direct 0--1 classification, fixed-architecture neural networks, threshold regression, and non-Lipschitz ℓp-type objectives with rational 0<p<1. Practical sufficient conditions for measurability hypotheses are discussed. Together, the framework extends continuity-based SAA theory to a tame-topological setting.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 28 Apr 2026.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 1.
1 paper.
- 2026Lipschitzian SLLNs for random functionscited by 0
- 2026Lipschitzian SLLNs for random functions22 Jul 2026