Projection-free Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data
share
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 ϵ-stationary point, are of the order 𝒪(1/ϵ^2.5) and 𝒪(1/ϵ^5.5) respectively. We also empirically demonstrate the performance of our algorithm on the problem of strategic classification with neural networks.
READ FULL TEXT