A General Framework of Optimal Stochastic Optimization with Dependent Data: Multiple Optimality Guarantee, Sample Complexity, and Tractability

• Author / Creator

  Pan, Bo

• We consider stochastic optimization in settings where the distribution of unknown parameters is observable only through finitely dependent training samples. Using the Sample Averaging Approximation ({SAA}), we specifically study the data-driven procedure in which, instead of receiving samples from the underly probability measure, the samples are taken along a single trajectory of a stochastic process $P$, where $P$ converge to the stationary distribution which we optimize, and construct optimal decisions. In this paper, we leverage measure concentration results and information theory to show that {SAA} retains strong asymptotic consistency and finite-sample performance guarantees provided that the source of randomness is suitably mixing. We moreover establish the optimal asymptotic normality results and shows the sample complexity of the {SAA} is bounded in terms of Empirical Rademacher Complexity. These results are adaptive to a natural class of optimization problems under a variety of structural assumptions. The numerical complexity of objectives, such as optimizing a (possibly constrained) sum of smooth and nonsmooth functions, can be handled efficiently by stochastic operator-splitting schemes under mild conditions. We establish strong convergence guarantees for these schemes. The results of this work have implications for stochastic optimization in linear dynamical systems, peer-to-peer distributed optimization schemes, decision problems with dependent data, and stochastic optimization problems over combinatorial spaces. We present examples with various data-generating processes, including vector-auto regressive process and finite-state Markov Chain, to demonstrate that our approach outperforms other data-driven methods.

• Subjects / Keywords

  • Data-driven optimization
  • Mixing
  • Sample Average Approximation
  • Sample Complexity
  • Stochastic Krasnosel’skiˇi–Mann Algorithm
  • Stochastic Operator-splitting Schemes

• Graduation date

  Spring 2023

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-cf2x-8z75

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.