  Sample average approximation (SAA), a popular method for tractably solving
stochastic optimization problems, enjoys strong asymptotic performance
guarantees in settings with independent training samples. However, these
guarantees are not known to hold generally with dependent samples, such as in
online learning with time series data or distributed computing with Markovian
training samples. In this paper, we show that SAA remains tractable when the
distribution of unknown parameters is only observable through dependent
instances and still enjoys asymptotic consistency and finite sample guarantees.
Specifically, we provide a rigorous probability error analysis to derive $1 -
\beta$ confidence bounds for the out-of-sample performance of SAA estimators
and show that these estimators are asymptotically consistent. We then, using
monotone operator theory, study the performance of a class of stochastic
first-order algorithms trained on a dependent source of data. We show that
approximation error for these algorithms is bounded and concentrates around
zero, and establish deviation bounds for iterates when the underlying
stochastic process is $\phi$-mixing. The algorithms presented can be used to
handle numerically inconvenient loss functions such as the sum of a smooth and
non-smooth function or of non-smooth functions with constraints. To illustrate
the usefulness of our results, we present several stochastic versions of
popular algorithms such as stochastic proximal gradient descent (S-PGD),
stochastic relaxed Peaceman--Rachford splitting algorithms (S-rPRS), and
numerical experiment.
