Poster
New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming
Hongcheng Liu · Jindong Tong
[
Abstract
]
Abstract:
This paper studies the sample average approximation (SAA) and its simple regularized variation in solving convex or strongly convex stochastic programming problems. Under heavy-tailed assumptions and comparable regularity conditions as in the typical SAA literature, we show --- perhaps for the first time --- that the sample complexity can be completely free from any complexity measure (e.g., logarithm of the covering number) of the feasible region. As a result, our new bounds can be more advantageous than the state-of-the-art in terms of the dependence on the problem dimensionality.
Live content is unavailable. Log in and register to view live content