Timezone: »

 
Poster
Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data
Abhishek Roy · Krishnakumar Balasubramanian · Saeed Ghadimi

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #540
in Poster Session 1 »
We study stochastic optimization algorithms 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 study both projection-based and projection-free algorithms. In both cases, we establish that the number of calls to the stochastic first-order oracle to obtain an appropriately defined $\epsilon$-stationary point is of the order $\mathcal{O}(1/\epsilon^{2.5})$. In the projection-free setting we additionally establish that the number of calls to the linear minimization oracle is of order $\mathcal{O}(1/\epsilon^{5.5})$. We also empirically demonstrate the performance of our algorithm on the problem of strategic classification with neural networks.
Keywords: constrained optimization · nonconvex optimization · Dependent Data · State-dependent Markov Data · Projection-free Algorithm
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Abhishek Roy (University of California, San Diego)
Krishnakumar Balasubramanian (University of California, Davis)
Saeed Ghadimi (University of Waterloo)

More from the Same Authors