Projection-free Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data
We study a projection-free conditional gradient-type algorithm for
constrained nonconvex stochastic optimization problems with Markovian data. In
particular, we focus on the case when the transition kernel of the Markov chain
is state-dependent. Such stochastic optimization problems arise in various
machine learning problems including strategic classification and reinforcement
learning. For this problem, we establish that the number of calls to the
stochastic first-order oracle and the linear minimization oracle to obtain an
appropriately defined $\epsilon$-stationary point, are of the order
$\mathcal{O}(1/\epsilon^{2.5})$ and $\mathcal{O}(1/\epsilon^{5.5})$
respectively. We also empirically demonstrate the performance of our algorithm
on the problem of strategic classification with neural networks.