Research map / Learning theory and algorithms / Sample complexity
Sample Average Approximation for Conditional Stochastic Optimization with Dependent Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes sample average approximation for conditional stochastic optimization under beta-mixing (dependent) data, proving deviation bounds, finite-sample guarantees, asymptotic consistency, and O(d/ε^4) sample complexity.
Problem
Conditional stochastic optimization (CSO) theory and SAA guarantees are established under i.i.d. data, but many applications (time series, control, RL) produce dependent samples.
Approach
Extends SAA guarantees for CSO to beta-mixing data by combining covariance inequalities for beta-mixing sequences with independent block sampling (Yu, 1993) and a Laplace-transform bound on blocks, yielding exponential deviation bounds, consistency, and sample complexity matching the IID case.
Key results
- SAA for CSO retains asymptotic consistency and a finite-sample guarantee under beta-mixing, with sample complexity O(d/ε^4) (ignoring log factors), same order as the IID case.
- With independent inner and outer randomness the sample complexity drops to O(d/ε^2).
- In the P2P robust regression experiment, N=O(T^{1/2}) allocation gives the smallest bias and highest small-ball probability; dependence does not degrade SAA performance in the experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SAA with β-mixing dependent training data | CSO · CSO with dependent data | sample complexity: O(d/ε4) | No clear effect |
| make inner and outer randomness independent | SAA for CSO · CSO with independent inner and outer randomness | sample complexity: O(d/ε4) -> O(d/ε2) | Helped |
| use SAA on β-mixing dependent data | CSO · Numerical experiments | performance | No clear effect |
Surprising findings
- The in-sample risk gap between dependent and independent sampling schemes shrinks as sample size grows.
Limitations
- Bounds include constants that may be impractical without knowledge of Lipschitz parameters.
- Analysis restricted to beta-mixing stationary sequences; other mixing conditions only sketched.
- Effect of the specific mixing coefficient on learning efficiency is not studied empirically.
Experimental setup
Datasets: simulated autoregressive/beta-mixing data for MAML-LQR simulated P2P robust regression data Kenneth R. French Data Library portfolio returns (Feb 2014 to Feb 2022)
Benchmarks: MAML-LQR simulation P2P robust regression simulation risk-averse portfolio allocation on Kenneth French data
Metrics: bias normalized error loss value small ball probability in-sample risk in-sample and out-of-sample return
Baselines: independent-sampling SAA for CSO
Builds on: Hu et al. (2020a) CSO sample complexity Yu (1993) independent block sampling Wang et al. (2022) SAA with dependent data Dai et al. (2017) SBEED
Closest papers by meaning
- How Does Black-Box Impact the Learning Guarantee of Stochastic Compositional Optimization? (NeurIPS 2024 · similarity 0.86)
- The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective (NeurIPS 2025 · similarity 0.85)
- New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming (ICML 2024 · similarity 0.85)
- Efficient Stochastic Approximation of Minimax Excess Risk Optimization (ICML 2024 · similarity 0.85)
- Smart Surrogate Losses for Contextual Stochastic Linear Optimization with Robust Constraints (NeurIPS 2025 · similarity 0.85)
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.