Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data
Authors: Abhishek Roy
Krishna Balasubramanian
Saeed Ghadimi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Constrained Optimization
Nonconvex Optimization
Projection-free Algorithm
Dependent Data
State-dependent Markov Data

Abstract: 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.

Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data
Abhishek Roy*
Krishnakumar Balasubramanian"
Saeed Ghadimi
Abstract
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 statedeependett Such stochas- tic optimization problems arise in various machine learning problems including strategic classification and reinforcement learning. For this problem, we study both projection-basee -hasedd and projection-free algorithms. In both cases, we establish that the number of calls the stochastic first-order oracle obtain an appropriately defined c-stationary point is of the order O(1 2225). In the projection-free setting we additionally establish that the number of calls the linear minimization oracle is of order (15)) We also empirically demonstrate the performance of our algorithm on the problem of strategic classification with neural networks.
Introduction
We consider the following stochastic optimization problem
argmin (0) argmin E [F(0;=)), 0Ee
OEE
where (i) the expectation is taken the stationary distribution, Ta, of the random vector x, (ii) F (and hence f) a potentially non-convex function 8 and (iii) θ is a compact and convex constraint set. Stochastic approximation algorithms for solving problem (1), given an independent and identically distributed (iid) data stream {*x JA drawn from x, are well-studied. Such iid assumptions are commonly made in various machine learning and statistical problems including empirical risk minimization [SSBD14], sparse recovery [BJMO12] and compressed sensing [FR13, 13, Lan20]. We refer [MB ABRW12, RSS12, GL13, SZ13, LZ16, ACD* 19] for a partial list of non-asymptotic upper and lower bounds on the oracle complexity of widely-used stochastic approximation algorithms like the Stochastic Gradient Descent (SGD) and the Stochastic Conditional Gradient Algorithm.
Our focus in this work is on the case when the data sequence {Ix 1 is drawn from a Markov chain with stateddependent transition kernel Pg. Such setting arises in several machine learning applications including but not limited to strategic classification [HMPW16 16, CDP15, MDPZH20, LW22] and reinforcement learning [Bar92, GSK13, ZJM21, KMMW19 19, QW20J. Despite their prevalence in practice, deeper understanding of the non-asymprotic oracle complexity of stochastic approximation for Markovian data is only now starting to emerge. We establish non-asymptotic
"abroy@ucdavis.edd edu. Halıcroğlu Data Science Institute, University of California, San Diego Work done while being affiliated with the Department of Statistics, UC Davis. Research of this author was supported by National Science Foundation (NSF) grant CCF-1934568.
"kbala@ucdavia edu. Department of Statistics, University of California, Davis. Research of this author was supported in part by UC Davis CeDAR (Center for Data Science and Artificial Intelligence Research) Innovative Data Science Seed Funding Program and NSF Grant DMS-2053918.
"sghadimi @uwaterloo. this author was supported by NSERC Discovery Grant.
Department of Management Sciences, University of Waterloo. Research of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

oracle complexity results for the stochastic conditional gradient algorithm for non-convex constrained stochastic optimization with Markovian data. To establish our results, from a methodological point-of-view, we leverage the moving-average stochastic gradient estimation technique recently used in 20, 20, XBG22] in the context of constrained optimization with iid data. This technique avoids having to a use a mini-batch of samples in each iteration, which turns out to be crucial in the non-iid setup we consider. From a theoretical point-of-view, we assume the so-called drift conditions, classical assumption in Markov Chain literature [AMP05]. This ensures the existence of solution to the Poisson equation associated with the underlying Markov chain [DMPS18] which enables one decompose the noise present in the stochastic gradient into three components: martingale difference sequence, a time-decaying sequence, and a telescopic sum type sequence. The key idea of our paper is to use this decomposition to construct auxiliary sequence of iterates with time-decaying noise-variane and show that these sequence of iterates are close to the iterates of the original sequence produced by our algorithm. This novel technique in then used in combination with a merit-function based analysis to establish the oracle complexity results.
1.1 Motivating Example
Problems of the form in (1) arise in various important applications, e.g., strategic classification, and reinforcement learning as mentioned above. Below we illustrate the motivation of this work through the example of strategic classification with adapted best response [LW22]. In strategic classification, there is a learner whose task is to classify a given dataset which is collected from a set of agents. Given the knowledge of the classifier, the agents can distort some of their personal features, in order to get classified in a predetermined target class. This scenario arises in various applications, e.g., spam email filtering, and credit score classification. Optimizing the classifier classify such strategically modified data where the agents modify the data iteratively can be formulated as problem (1).
Formally, let the classifier be h(z, 0) where x Rd is the feature and 0 is the parameter to be optimized. h(x;;) )) + R is potentially nonconvex. Let the loss function be logistic loss which for sample (z, y), where y E { (-1,1) 1} denotes the corresponding class, is given by,
L (00; xr y) = log (1 exp (-h(1; 0))) + (1 y)x(2;0)/22
We use zs, and x-s to denote the subset of feature which respectively strategically modifiable, and non-modifiable by the agents. Then the modified feature (the best response) z's reported by the agent is the solution to the following optimization problem:
r's argmax (h(z: 0) c(zs,r's),
(3)
ag
where c(x; x²) the cost of modifying wy to x's. Let the agents iteratively learn r's similar to [LW22]. Note that unlike [LW22], where the authors deploy logistic regression classifier and the closed form solution of the best response is readily known to the agents, it may not be the case in general. In that case the agents have to possibly learn the best response x's using some iterative optimization algorithm. For example, if the agents use Gradient Ascent then, at every iteration k, a set I4 of nı S . randomly chosen agents out of M agents modify their features
S.S + (V 0x) Ve(x 1 ..B.i) k-1
i i I
SSS
(4)
i i Is
S,
where a the stepsize. With little abuse of notation, we use Vh(x5, in (4) to denote the fact that the gradient is with respect to 2/,7" while s= remains unchanged. This introduces the state-dependent Markov chain dynamics in the training data. The objective function, analogous to f() in (I), is
minF.., [L(f;: x. v)], AE
where ne is the stationary joint distribution of (x. y), and θ is a convex and compact set, e.g., sparsity inducing constraint ||0]], < R from some R > 0. The loss evaluated at a single data point (r, y). L(O; ar, y). is analogous to ((;:)) in (1). [DX20], and [LW22] study this problem theoretically and empirically respectively in an unconstrained strongly convex setting. Our results takes a step towards analyzing this problem in constrained nonconvex setting. We empirically show the performance of the stochastic conditional gradient algorithm on strategic classification problem in Section 4.1.

---

1.2 Preliminaries and Main Contributions
Before we present our main contributions, we introduce our convergence criterion. In constrained optimization literature, most commonly used convergence criteria are: (i) Gradient Mapping (GM), and (ii) Frank- Frank-Wolfe Gap (FW-gap). The Gradient Mapping at point 0 E θ is defined as
Ge V)()) = (0 Ill ( -0-
- (-11(())
(5)
B
where (z) denotes the orthogonal projection of the vector x onto the set θ i.e.
Ile 0 1 TV)@) = argmin MEE
8
(V.(0), 0) ly 01
We will use (8, ()),) 3) to denote He (0- ( when there is no confusion. Note that vf(O). In other words, for constrained optimization gradient mapping plays an analogous role of the gradient for unconstrained optimization. The gradient mapping is a frequently used measure in the literature as convergence criterion for nonconvex constrained optimization [Nes18]. We should emphasize here that although the gradient mapping cannot be computed in the stochastic setting, one still use it convergence measure.
when θ = _d we have (0, V (f
[BG22] shows that the above notion of convergence criterion is closely related to the so-called Frank- Wolfe Gap. The FW-gap is defined as
ge (8, V f())
max (V -)) MEB
The following proposition from [BG22] establishes the relation between the gradient mapping criterion and the Frank- Wolfe gap:
Proposition 1.1 [BG22] Let ge(.) be the Trank-Wolfe gap defined in (6) and Ge(-) be the gradient mapping defined in (5). Then, we have
[| V f(). 9)1 S g0, vf))).
VO e.
Moreover, under standard regularity assumption smooth optimization (specifically, Assumption 2.1, and 2.2), we have
(0, ff))) L (0, vf(0),
(7)
In this work we use suboptimality measure, closely related both GM and the FW-gap. At point i E O we define the suboptimality measure V(0, =) IRd R + R as [GRW20]
v(0,2) 2) == Ille (0 9/ 0| + +||= [[
(8)
where 2, formally defined in Algorithm 1, is the moving-averra average estimate of f(). We show the relation among V VO,, 2). and GM (0
z, 3) in the following proposition.
Proposition 1.2 Let {2x} be the sequence generated in Algorithm 1. Then, for k: = 1, we have [0 =u. B)113 < max 232) (0x, zu).
The proof is provided in Appendix A. The main objective of this work is to find an e-stationary solution to (1), where an c-stationary solution is defined follows:
Definition 1 A point is said to be an e-stationary solution to (1), E (V( S where the expectation is taken over all the randomness involved in the problem.
For stochastic Frank- Frank-Wolfe-typa Wolfe-type algorithms. the oracle complexity is measured in terms of number of calls to the Stochastic First-order Oracle (SFO) and the Linear Minimization Oracle (LMO) used to the solve the sub-pree cuob-rrolemss of the algorithm which involves minimizing a linear function over the convex constraint set. Formally, we have the following definition.
Definition For a given point 0 E O, SFO returns the stochastic gradient F(,, Given a vector LMO returns a vector == argminggel (z, v)-
3

---

non-iid
1id
State-independent MC
State- deteedeenndett MC
Algorihm
Criterion
SFO
LMO
SFO
LMO
SFO
LMO
I-SFW [7SM 201
FW-gap
( "
(
x
X
x
(ASA+ICG) [XBG22]
GM
0
X
x
X
X
(ASA+ICG) |This paper]
GM
0
O
O (c
Table Oracle complexity of projection-free one-sample stochastic conditional gradient algorithms for constrained non-convex optimization, to find an e-stationary point.
Hence, in this work, the oracle complexity is measured in terms of the number of calls to SFO and LMO required by the proposed algorithm to obtain an c-stationary solution as in Definition 1. With the above preliminaries, we now list our main contributions:
In Theorem 3.1, we show that the number of calls to the SFO and LMO required by the stochastic conditional gradient-type method in Algorithm I, with state-dependen Markovian data, is of order ( (c-55) and (ce-5.5) respectively. To the best of our knowledge, these are the first oracle complexity results for projection-free one-sample stochastic optimization algorithm for constrained nonconvex optimization in the Markovian setting.
In Theorem 3.2. for the sake of completion, we also show that the number of calls to the SFO and LMO required for the case of state-independen Markovian data is of the order (c- and Ō(c²²) respectively. In particular, this turns out to be of the same order as that of iid data ignoring the logarithmic factors.
A summary of the our contributions is provided in Table 1. We also empirically evaluate our algorithm on a strategic classification problem with 2-layer neural network classifier and show that the proposed method obtains encouraging results. We provide an experiment on single-index model regression with sparsity-inducinn nuclear-norm ball constraint Appendix 4.2.
1.3 Related Work
Stochastic Optimization with Dependent Data. Understanding stochastic approximation algorithms like SGD with dependent data in the asymptotic setting has been well-explored in the optimization literature. We refer to YO3,3, Bor09, BMP12] for text-book introduction to such classical results. few recent results include [AMP05, TD17J. In the unconstrained non-asymptotic setting, [DAJJ12] studies convex optimization with ergodic data sequence. [DL22] uses multi-level gradient estimator and analyze AdaGrad for nonconvex optimization with Markovian Data. Block coordinate descent with homogeneous Markov chain has been analyzed in [SSXY20] for nonconvex unconstrained optimization. [DX20] studies stochastic optimization with decissin-deeenneee data distribution for strongly convex functions in the context of strategic classification.
Sample-average approximation algorithms for constrained convex optimization with d-mixing data was considered in [WPT*2]] 21]. [SSY18], and [AL22] analyze projected SGD for constrained non- convex optimization with homoooooggneuuss Markov chain. None of these works consider state- dependent data distribution except [DX20]. But unlike [DX20], we consider constrained nonconvex optimization. There also exists work in the reinforcement learning literature on understanding stochas- tic optimization with Markovian data; see, for example [XXLZ20, BRS18, DNPR20). However, such works are invariably focused on specific objective functions arising in the reinforcement learning setup, while our focus is on obtaining results for a general class of functions.
Conditional Gradient-Tyne Type Method. There has been significant recent advancements in the conditional gradient algorithm literature although it was developed long back [FW56, LP66]; see [Mig94, 13, LJJ15, LJJ15, HJN15, GKS21, BS17], for non-cxhaustive list recent works. [HK12, 16 provided expected oracle complexity results for stochastic conditional gradient algo- rithm in the stochastic convex setup. Better rates were provided by a sliding procedure in [LZ16]. In the non-convex setting, [RSPS16. 16. YSC19, HL16] considered variance reduced stochastic conditional gradient algorithms, and provided expected oracle complexities. [QLX18] analyzed the sliding algorithm in the non-convex setting and provided results for the gradient mapping criterion. All of the above works use increasing orders of mini-batch based gradient-estimate.
To avoid mini-batches, a moving-average gradient estimator based on only one-sample in each itera- tion for stochastic conditional gradient-type algorithm was proposed in [MHK20] and [ZSM+20] for the convex and non-convex setting. However, several restrictive assumptions have been made in

---

[MHK20] and [ZSM* 20). Specifically, [ZSM* 20] requires that the stochastic gradient G1 (z, {1) has uniformly bounded function value. nram,ent-norm, and Hessian spectral -oom, and the distribution of the random vector & has an absolutely continuous density p such that the norm of the gradient of log p and spectral norm of the Hessian of log p has finite fourth and second-moments respectively. In contrasts, we do not require such stringent assumptions.
2 Assumptions
We now introduce the precise assumptions we make in this work. Let Fú be the filtration generated by (on.... , 0zz 20.... Ak; 21, ... .4k For any mapping g : .Rd + Rd define the following norm with respect to a function V IRd + [1, oc): 1lllv sup /V(x)), and let Ly = {g zE
R - Rd supRe o Il9lly < oo).
Assumption 2.1 (Constraint set) The set O C Rd is convex and closed with max ||x - ullz S De.
z.yE6
form some De > O.
Assumption 2.2 Let f be a continuously differentiable function.
Assumption 2.3 Let Ex+1 (Ok, Ik+1) = VF(0e, - v.(x)). Then,
E [|EK+1 JK- 112 Fk S o
E (VF((0, [F S 5
0² = max oz).
Assumption 2.4 Let { be a Markov chain with transition kernel Po. For any 0 E O Po is irreducible and aperiodic. Additionally, there exists a function V Rdd [1, 0o) and constant a 2 2 such that for any compact set e' C.
(a) There exist set C' c. Rd, an integer I, constants 0 < A < 1. b. K. 6 > 0. and probability measure v such that,
sup Plya (x) & (z) + ([ Vr YE
sup Pol S (z) E RA
(10)
inf
Pa A) 2 5v(A) V. Bud
(11)
ge
where Bg is the Borel o-algebra over Rd
(b) There exists a constant e >> 0, such that, for all x E R2d and for all 0, 0' O',
sup || [VF(0x))) x)) Sc, 0ee'
(12)
((),)) - VF(O', x)1y S e el 0112-
(13)
(c) There exists a constant e > 0, such that, for all (0, 0') E O' x O¹,
PPg go v S /اوو|y 1|e - 8'112 Ag E Lv
(14)
Pag Pa I c 1ل ||0 0'112 Vg E Lyn.
(15)
Some comments regarding the assumptions are in order. Assumption 2.1, and Assumption 2.2 are common for constrained optimization [GRW20, XBG22, AL22, ZSM 20]. Assumption 2.1, and Assumption 2.2 together imply the Lipschitz continuity of /(-), there is a constant L > 0 such that for any 0,, O2 E O, we have (f(0,) s(02) < L |10, 02112- Assumption 2.3 is common in stochastic optimization literature. Assumption 2.4(a) is frequently used assumption in Markov chain literature. It implics that for every 0 θ there exists a stationary distribution TT(I), and the chain is you -nnifformlly ergodic [AMPO5]] Assumption 2.4(c) provides smoothness guarantee on the function f()). More formally, we have the following proposition.
Proposition 2.1 (Lipschitz continuous gradient [AMPO5]) Let Assumption 2.4 be true. Then f(- has Lipschitz continuous gradient, i.e., there is a constant L.g > 0 such that for any Og 02 E O
| f(0)) v (02))1 < LG 1|0 02112.
(16)
5

---

Finally, the most important implication of Assumption 2.4 is that it ensures the existence and regularity of solution u(O. z) Poisson equation the transition kernel Po given by u(0, .)) Pou(0, z) (F(0, x (0)). Solution of Poisson equation has been crucial in analyzing additive functionals of Markov chain (see [AMP05] for details). In this work, the Poisson equation solution facilitates decomposition of the noise as presented in Lemma 3.1 which is a key component of our analysis.
Main Result
In this section we present our main result on the oracle complexity to establish a bound on (0,, =+)]. In order to do so we use Algorithm and similar [XBG22). If an exact
Algorithm Inexact Averaged Stochastic Approximation (I-ASA)
Input: 2o. Bu E R 7h = (N + k) 1/2 < a < 1, B.
for 1,2, ... N do
min
(Zx y 0x) + + 11y- 1ly-0All 0m123
(Projection)
yk
ICG( 2k. 0k. 3, w)
(No Projection)
0.41
O2 7]+++1 (ylk 0k)
26-11 (1 17 1kk + T V FO Tx+1)
end for
Output: On where P(R i) Σソ for i 1,2,
Algorithm 2 Inexact Conditional Gradient (ICG)
Input: 2, 3, b,W. Set w/ 0 for = 1, ... .., do
Find e; such that
(Us, z + B(w: 0)) S argmin (v, + 3(w; 0)) + BwDD f +2) wEE
wi+11 = (1 ps)w, + paat where μl; 742
2
end for
Output: wt
minimizer of the following subproblem, which is the projection of 0g zx/B O available, then Algorithm is same as ASA algorithm introduced in [GRW20].
(#x, - 0x) + 3
min E
|1 0g 1
(17)
When projection operator is unavailable computationally costly, solve (17). At iteration k Algorithm finds an approximate solution to (17) based on the conditional gradient algorithm. Algorithm needs access to LMO which is often much cheaper and simpler to compute than projection operator. We should emphasize that our results are not limited to ICG method but are valid for any method which can solve (17) within an error of the order of {m)..
Algorithm 2 instead to
Theorem 3.1 Let Assumption 2.1-2.4 be true. Then, for Algorithm 1,
(a) when projection operator is available, choosing
T7k (N+ 33/5
9 =
(18)
for 1,2, we have
E (V 2R) = (N- (N-#).
(b) when Algorithm& is used to solve (17), choosing
T (N k) 3/5
B = 1, =1 to m1
= 2/
(19)

---

for k = 1,2, ... .N we have
E (V 2R]] = (N-
where the expectations are taken with respect to all the randomness of the algorithm, and an independent integer random variable R E (1,2,-..,A)) ,N with probability mass function,
N
P(R= = TT/
E 11,2,... NN..
k=1
Remark 1 Note that total number of LMO calls are Ek= 4 =
((N1155), In other words, to achieve (0R, f(0R), 3)11 SE ZR] S SFO and LMO complexities are respectively -2.5, and - Note that the SFO complexity will be -2.5 as long as one has an approximation of the projection operator with approximation error O(T²))
Remark In Theorem 3.1, one obtains sublinear rate max (Na-1, , NN2-19) with v/ (N + k)
for 1/2 < a < 1. Choosing
3/5 provides the fastest rale of convergence.
Before sketching the outline of the proof, we present the following lemma which provides decom- position of the noise ( The lemma and its proof are almost same Lemma A.5 in [Lial0] with the only difference that unlike [Lia10], where the iterates are of SGD, we need to prove it for the iterates of Algorithm I. We provide the proof in Appendix A.
TT)
one of the key result used in the proof the main theorem.
Lemma 3.1 Let Assumption 2.1-2.4 be true. Then the following decomposition takes place:
Ex (0 xx) = Cg + V/ + Çk=
where, {er} is martingale difference sequence, E [ I Te- and &.- = (5x -
(GGk-(( / where
[|calla] 1 77--
Outline of the proof of Theorem 3.1: A key step in the analysis of Algorithm involves controlling the expectation of interaction with noise of the form (Vf(Ok) V (((1 xk+1)). For iid or martingale difference data it is easy to control because (0,,
= O. But this is no longer true for Markov chain data. To resolve the issue, first notice that under our assumptions, the noise sequence & can be decomposed into the sum of a martingale difference sequence } and some residual terms (2%) }, and { as shown in Lemma 3.1. Then the key step is to introduce a different sequence of hypothetical
E ((())(0))
iterates (02. Tk, z for which the noise is small enough so that we can bound (Vx =x) and then show that these hypothetical iterates and the original sequence generated by Algorithm are close enough so that E (Ox, =+] is of the same order as IE V V(2,, 2x) This step is the main novelty of the proof.
Specifically, consider the following sequence:
0 = 0g 7 20
(20)
{ (zkyy - 0b) + 2 8all2)
8
Uk argmin NEE
(21)
α 02 + mk+1 (it 0z)
(22)
Ex+1 = sh+1 + Ek+2
(23)
This also means,
k++ (1 - 1)) + a77 (V)(Ox) + Ex+1),
(24)
where, & ex + 2/h E.- Note that by Lemma 3.1, E [ex] and E u/ + Ex
1 mk- First
show that by choosing 7 = (N k) 1/2 < a < 1, and t2 = 1 1/n one has E
| 0% 1
O (N)-49), and E (Vx... ] < 2E (0k.. 2+) + (N2-49) Then we establish the bound on V(O,, ε.). Combining the above two facts proves Theorem 3.1. We defer the detailed proof to Appendix A.I.
7

---

3.1 State-independent Markov Chain
While our main goal in this work is to analyze Algorithm for constrained noneonvex optimization with state-dependent Markov chain data, we provide the following result on the complexity of Algorithm 1 for Markov chain data with state-independent transition kernel for the sake of completion. Here we use P to denote the transition kernel (as opposed to Po for state-dependent kernel). Note that under Assumption 2.4(a), for each 0, the chain is V-uniformly ergodie, and hence, exponentially mixing [MT12] in the following sense:
Definition 3 A Markov chain is said to be exponentially mixing, if there exists C,r such that, for any initial state æ,
(s," - +llv S Cexp(-rr)), where pm(x,)) :) is the distribution of X,, with initial state Xo = d.
(25)
Now we present our result on the complexity of Algorithm I to find an e-stationary solution to (1) for exponentially-mixee Markov chain data with state-independent transition kernel.
Theorem 3.2 Let Assumption 2.1-2.3 be true. Let Assumption 2.4(a)-(b) be true with Pa replaced by P. Then, for Algorithm 1,
(a) when the projection operator available, choosing
Mi = 1/VN, B 8=1
(26)
for k 1,2, ... , we have
E [V = =0 (10g.//VN)
(b) when Algorithm 2 is used, choosing
Ti = 1/VNN, t = [V]], B B=1, = 14 1= 2/(++)
(27)
for 1,2, we have
[0) (
where the expectation taken with respect to all the randomness of the algorithm, and an independent integer random variable R E 21,2,-.. NN whose probability mass function is given by.
P PR k) Tpp Σ Th KE 11.2....... .N..
We defer the proof the Appendix.
Remark 3 To find e-stationary point, the total number of calls SFO and LMO are Ô (E- and Ô ()), where Ö(-) denotes the order ignoring logarithmic factors.
Remark The authors of [AL22] obtain the same rate as in Theorem 3.2 for constrained (but projection- based) noncorvex optimization with state state-inde -nteeeddeeendent exponentially mixing data. In the sepeedde case, since the transition kernel of the Markov chain is controlled by 6g, and the transition kernel is assumed to be only Lipschitz smooth in 9 (15), the chain does not necessarily exponentially mix. In the intteiindependent case, since the chain mixes exponentially we obtain the same rate as well. While their results are for projection- algorithms, we analyze a projection- free LMO-based algorithm since LMO is often computationally cheaper than projection.
Experimental Evaluation
4.1 Strategic Classification
In this section we illustrate our algorithm on the strategic classification problem as described in Section 1.1 with the CiveMeSomeCredit" dataset. The main task is a credit score classification
Available https: //www//wwwww/c kaggle.

---

Projection IDG
logViBuua
Teut Accuracy
3.7
Projection
Figure 1: Strategic Classification: (Left): Performance of Algorithm with and without the projection operator. (Right): Test Accuracy with Algorithm with and without the projection operator.
problem where the bank (learerr) has to decide whether a loan should be granted to a client. Given the knowledge of the classifier the clients (agents) can distort some of their personal traits in order to get approved for a loan. Here we use a 2-layer neural network with width m as the classifier, given by
h(2; W. A.B)
E A B.),
where v--)) is the activation function, W: Rd W Wy Wa] 1m A (A1. A2. ,mm) E I=. == (B1, 13 22.... Bm mm) Rm. We will use 0 to collectively denote (W,A, AVAA,B) BB.. We impose the constraint of sparsity on the classifier given by |00]] R for some As loss function we consider logistic loss as shown in (2). We consider quadratic cost given by c(x,x') | =' (2A) where À is the sensitivity of the underlying distribution on 0. We assume that the agents iteratively learn a'g similar [LW22]. Note that unlike [LW22], the closed form of best response is not known here. So assume that the agents Gradient Ascent (GA) to learn the best response. For |0]| I constraint, the LMO in Algorithm at iteration À given by - -Rsign (g:), where i argmax, 1.... 191. == + f(w,, 0), and qj is the j-th coordinate of g. We select a subset of randomly chosen M 2000 samples (agents) such that the dataset is balanced. Each agent has 10 features. Note that since Algorithm 1 computes the gradient
sample at every iterate, the computation time independent of the total number of agents. We assume that the agents can modify Revolving Utilization, Number of Open Credit Lines, and Number of Real Estate Loans or Lines. In this experiment we set nı 200. Similar to [LW22], we set a = 0.5A, and X 0.01. For the classifier, the activation function chosen sigmoidal, and set N = 20000, and R = 4000. All the parameters of Algorithm are chosen as described in (19). Figure 4.1 shows that Algorithm 1 finds an e-stationary point of the strategic classification problem. We show that Algorithm performs comparably with Averaged Stochastic Approximation with the projection operator. Each curve in Figure 4.1 is an average of 50 repetitions.
400. We
4.2 Single Index Model with Trace-norm Ball Constraint
In this section we illustrate our algorithm on a synthetic example of single-index model regression with a nuclear-norm constraint on the model parameter. Let ||-I1. denote the nuclear norm. The features (ru)a R&d xd2 are matrix-valued time-series given by,
26 Ar + Ex + WAU0k,
where E Rdixds matrix with spectral radius less than 1, F& E Rddxxe Xd2 is the noise matrix with each entry of Eg is iid NO0, 1) random variable, We is (ernoulli(0.5) random variable, and
E R. For a fixed 02 = 0, {xx has a stationary distribution as shown in Proposition of [CXY21]. }E and [W of Assumption 2.4 since the evolution of x& only involves linear terms in Og. The responses (3n )x generated according the following single index model,
iid sequence. This Markov chain follows conditions (b) and (c)
yk g x 0*) Es,,
where }e is an iid sequence of standard normal random variables, Rdi xda matrix with ||0"1, < 1, and g(-) IR + F is the link function. For this experiment choose g(x) 3x

---

4e-05
respectively, which matches the Without Projection Win Projection
Without Projection
With Projection
1.2
Without Projection With Projection
1.0
3e+05
V(0,2)
Test MSE
-F
0.8
20-05
0.6
1e-05
0.4
0e+00
0.2
500
1500
2000
1000
2000
500
1500
2000
Iteration
Iteration
lteration
Single-index model with nuclear-norm constraint: (Left): Performance of Algorithm I with and without the projection operator. (Middle): Test Mean Squared Error (MSE) with Algorithm I with and without the projection operator. (Right): ||0 - lr with Algorithm with and without the projection operator.
Figure 2:
sin(x).. Since ys only depends on Ty. and g a Lipschitz continuous function of Assumption 2.4 holds for (æa, v1.). It is easy to see that Assumptions 2.1 2.3 holds for this example. The constraint set is given by [|0]|, S 1, i.e., we assume that 6* has a low-rank structure. The goal is to minimize the expected squared loss with the constraint |0|1_ S 1, i.e.,
min E [01l_1
[(y - g(x: 0))²].
(28)
The advantages of conditional-gradien based method for nuclear-norm ball constrained problems have been studied extensively [J, Jag 13, HJN15]. The main advantage of ICG-based method is that calculating the LMO in this case requires computation of the leading singular vector of gradient matrix whereas to calculate the projection on the trace-norm ball one needs to compute the complete singular value decomposition. Let U1, 21 are the leading left and right singular vectors of the noisy gradient matrix evaluated (0; x. y). 22g g(x 0))g (xx 0)x. Then the LMO is given by _u1v]
For this experiment we choose d1 = 10, d2 = 20, v = 0.1, and N = 2000. Rest of the parameters of Algorithm 1 are chosen according Theorem 3.1. In Figure 2, we compare the projection- -baed and ICG based version of Algorithm with respect to V(Ok, 24 test Mean Squared Error (MSE), and ||0, 0*II F where ||-I|F the Fröbenius norm. Figure 2 shows that the performance of projection- based and the ICG-based versions of Algorithm I are almost same. Each plot in Figure 2 is the average of 50 repetitions.
5 Discussion
In this work we provide oracle complexity results for the stochastic conditional gradient algorithm to find an e-stationary point of a constrained nonconvex optimization problem with -ate-depnnd Markovian data. In Theorem 3.1, we show that the number of calls to the SFO and LMO required by the stochastic conditional gradient-type method in Algorithm 1, with state-dependent Markovian data, O(E 2.5) and O 5.5) respectively. To the best of our knowledge. these are the first oracle complexity results in this setting. In Theorem 3.2, we show that SFO and LMO complexity in the case of state- inteeennddeendent Markovian data is Ō and Ö(E corresponding results in the iid setting.
There are various avenues for further extensions. Establishing lower bounds on the oracle complexity of projection-fres algorithms in the Markovian data setting is extremely interesting. It is also intriguing to establish upper and lower bounds on the oracle complexity for more general types of dependent data sequences arising applications, including á and a mixing sequences. Yet another exciting direction is that of designing algorithms adaptive to the dependency in the data that achieve potentially better oracle complexity bounds.
10

---

References
[ABRW12] Alekh Agarwal, Peter Bartlett, Pradeep Ravikumar, and Martin Wainwright. Infornation-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58(5):3335-3249, 2012. (Cited on page 1.)
[ACD*19] 19] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprins arXiv:1912.02365. 2019, (Cited page I.)
[AL22] Ahmet Alacaoglu and Hanbaek Lyu. Convergence and complexity of stochastic subgradient methods with dependent data for nonconvex optimization. arXiv preprint arXiv:2203. 15797, 2022. (Cited on pages 4, 5, and 8.)
[AMP05] Christophe Andrieu, Éric Moulines, and Pierre Priouret. Stability of stochastic ap- proximation under verifiable conditions. SIAM Journal on control and optimization. 44(1):283-312 2005. (Cited on pages 2, 16, and 25.)
[Bar92] Peter L Bartlett. Learning with a slowly changing distribution. In Proceedings of the fifth annual workshop Computational learning theory, pages 243 143-252, 1992. (Cited on page 1.)
[BG22] Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order nonconvex stochas- tic optimization: Handling constraints, high dimensionality, and saddle points. Foun- dations of Computational Mathematics, 22(1):35 76, 2022. (Cited on page 3.)
[BJMO12] Francis Bach, Rodolphe Jenatton, Julien Mairal, and Guillaume Obozinski. Structured sparsity through convex optimization. Statistical Science, 2744):450-468, 2012. (Cited on page 1.)
[BMP12] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012. (Cited on page 4.)
[Bor09] Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48.
Springer, 2009, (Cited on page 4.)
[BRS18] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pages 1691-1692. PMLR, 2018. (Cited on page 4.)
[BS17] Amir Beck and Shimrit Shtern. Linearly convergent away-step conditional gradient for non-strongly convex functions. Mathematical Programming, 164(1-2):1-21) 2017. (Cited on page 4.)
[CDP15) Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. In Conference on Learning Theory, pages 280-296. PMLR, 2015. (Cited on page 1.)
[CXY21] Rong Chen, Han Xiao, and Dan Yang. Autoregressive models for matrix-valued time series. Journal of Econometrics, 222(1):539-566 2021. (Cited on page 9.)
[DJJ12] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 1544 2012. (Cited on page 4.)
[DI222] Ron Dorfman and Kfir Y Levy. Adapting to mixing time in stochastic optimization with markovian data. arXiv preprint 202442220..04428, 2022. (Cited on page 4.)
[DMPS18] Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier. Markov chains. Springer, 2018. (Cited page 2.)

---

[DNPR20] Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Convergence rates of accelerated markov gradient descent with applications in reinforcement learning. arXiv preprini arXiv:2002.0287. 2020. (Cited on page 4.)
[DX20] Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-dependent distributions. arXiv preprini arXiv:2011.11177 2020. (Cited on pages 2 and 4.)
[FR13] Simon Foucart and Holger Rauhut. An invitation to compressive sensing. In A mathematical introduction to compressive sensing, pages 1-39. Springer, 2013. (Cited on page 1.)
[FW56] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly. 3(1-2):95- -10, 1956. (Cited on page 4.)
[GKS21] Dan Garber, Atara Kaplan, and Shoham Sabach. Improved complexities of condi- tional gradient-type methods with applications to robust matrix recovery problems. Mathematical Programming, 186(1):185-2)) 208. 2021. (Cited on page 4.)
[GL13] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013. (Cited on page 1.)
[GRW20] Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approximation method for nested stochastic optimization. STAM Journal on Optimiza- tion, 30(1):960- 979, 2020. (Cited on pages 2, 3, 5, 6, 22, 23, and 24.)
[GSKI3] Yair Goldberg, Rui Song, and Michael R Kosorok. Adaptive q-learning. In From Prob- ability to Statistics and Back: High--Dimensioal Models and Processes-A Festschrift in Honor of Jon A. Wellner, pages 150-162. Institute of Mathematical Statistics, 2013.
(Cited on page 1.)
[HJN15] Zaid Harchaoui, Anatoli Juditsky, and Arkadi Nemirovski. Conditional gradient algo- rithms for norm-regularized smooth convex optimization. Mathematical Programming, 152(1-2):75-112 12, 2015. (Cited pages 4 and 10.)
[HK12] Elad Hazan and Satyen Kale. Projection-free online learning. In 29th International Conference on Machine Learning, ICML 2012, pages 521-528, 2012. (Cited on page 4.)
[HL16] Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic opti- mization. In International Conference on Machine Learning, pages 1263-1271, 2016. (Cited on page 4.)
[HPW166] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111 111-122 2016. (Cited on page 1.)
[Jag13] Martin Jaggi. Revisiting foank-wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning, pages 427-435. PMLR, 2013, (Cited on pages 4, 10, 17, and 25.)
[JS1O] Martin Jaggi and Marek Sulovský. A simple algorithm for nuclear norm regularized problems, In JCML, 2010. (Cited on page 10.)
[KMMW19] Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In Conference on Learning Theory, pages 1974. PMLR, 2019. (Cited on page 1.)
[KY03] Harold Kushner and George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003. (Cited on page 4.)
[La Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020. (Cited on page 1.)
12

---

[Lial0] Faming Liang. Trajectory averaging for stochastic approximation meme algorithms. The Annals of Statistics, 38(5):2823-2855 2010. (Cited on pages and 16.)
[LJJ15] Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank- Wolfe optimization variants. In Advances in Neural Information Processing Systems, pages 496-504, 2015. (Cited on page 4.)
[LP66] Evgeny Levitin and Boris Polyak. Constrained minimization methods. USSR Compu- tutional mathematics and mathematical physics, 665):1-50, 1966. (Cited on page 4.)
[LW22] Qiang Li and Hoi-To Wai. State dependent performative prediction with stochastic approximation. In International Conference on Artificial Intelligence and Statisties, pages 3164-32 11663186. PMLR, 2022. (Cited on pages 1, 2, and 9.)
[LZ16] Guanghui Lan and Yi Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26(2):1379-1499 2016. (Cited on pages I and 4.)
[MB1]] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances neural information processing systems, 24, 2011. (Cited page 1.)
[MDPZH20] Celestine Mendler-Dünnee Juan Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33:4929-49339 2020. (Cited on page 1.)
[MHK20] Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. Journal of machine learning research, 2020. (Cited on pages 4 and 5.)
[Mig94] Athanasios Migdalas. A regularization of the frank-wolfe method and unification of certain nonlinear programming methods. Mathematical Programming, 65(1):331-345, 1994. (Cited on page 4.)
[MT12] Sean Meyn and Richard I. Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012. (Cited on page 8.)
[Nes18] Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018. (Cited on page 3.)
[QLX18] Chao Qu, Yan Li. and Huan Xu. Non-convex conditional gradient sliding. In Interna- tional Conference on Machine Learning, pages 4208 -208-4417..2 PMLR, 2018. (Cited on page 4.)
[QW20] Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and q-learning. In Conference on Learning Theory, pages 3185-3205. PMLR, 2020. (Cited on page 1.)
[RSPS16] Sashank Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic frank-wolfe methods for nonconvex optimization. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1244-1251. IEEE, 2016. (Cited on page 4.)
[RSS12] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571-1578, 2012. (Cited page 1.)
[SSBD14] Shai Shalev Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. (Cited on page 1.)
[SSXY20] Tao Sun, Yuejiao Sun, Yangyang Xu, and Wotao Yin. Markov chain block coordinate descent. Computational Optimization and Applications, 75(1):35-66) 2020. (Cited on page 4.)
13

---

[SSY18] Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. Advances in neural information processing systems, 31, 2018. (Cited on page 4.)
[SZ13] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimiza- tion: Convergence results and optimal averaging schemes. In International conference on muchine learning, pages 71 71-79. PMLR, 2013. (Cited on page 1.)
[TD17] Vladislav B Tadić and Armaud Doucet. Asymptotic bias of stochastic gradient search. The Annals of Applied Probabiliiy, 27(6):3255-3300 2017. (Cited on page 4.)
[WPT+21] Yafei Wang, Bo Pan, Wei Tu, Peng Liu, Bei Jiang, Chao Gao, Wei Lu, Shangling Jui, and Linglong Kong. Sample average approximation for stochastic optimiza- tion with dependent data: Performance guarantees and tractability. arXiv preprint arXiv:2112.05368, 2021. (Cited on page 4.)
[XBG22] Tesi Xiao, Krishnakumar Balasubramanian, and Saeed Ghadimi. A projection-free algorithm for constrained stochastic multi-level composition optimization. arXiv preprint 22..i::2222.04269. 2022. (Cited on pages 2, 4, 5, and 6.)
[XXLZ20] Huaqing Xiong, Tengyu Xu, Yingbin Liang, and Wei Zhang. Non-asymptotic con- vergence of adam-type reinforcement learning algorithms under markovian sampling. arXiv preprint arXiv:2002.0622 062.000000066..... 2020. (Cited on page 4.)
[YSCI9] Alp Yurtsever, Suvrit Sra, and Volkan Cevher. Conditional gradient methods via stochastic integraee differential estimator. In International Conference on Ma- chine Learning, pages 7282-7291. PMLR, 2019. (Cited on page 4.)
[ZIM21] Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical inference with m-estimators on adaptively collected data. Advances Neural Information Processing Systems, 34, 2021. (Cited page
[ZSM+20] Mingrui Zhang, Zebang Shen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One-sample Stochastic Frank-Wolfe. International Conference on Artificial Intelli- gence and Statistics, pages 4012-4023, PMLR, 2020. (Cited on pages 2, 4, and 5.)
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We report the average of 50 trails
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We did not calculate the exact timings. However, our experiments are fairly small-scale ones run on personal laptop computer, and our main contributions theoretical.
14

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "z3-DGUYQxIr", "reviewer": "Reviewer_cX4H", "summary": "In this work, the authors consider a class of constrained stochastic optimization problems where the data is drawn from a Markov chain. They propose a conditional gradient-type algorithm for solving this class of problems with bounds on the convergence rate. Some numerical experiments are conducted to verify the effectiveness of the algorithm. ", "questions": "1. See weakness points. \n2. Compared with the literature, the main difficulty seems to be the Markovian data. However, by assumption 2.4 and Proposition 2.1, it seems that the problem can be reduced to classical constrained smooth stochastic optimization. Does it mean that assumption 2.4 is too strong? Or is there any other technical difficulty?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Constrained stochastic optimization problems with Markovian data are important in the ML community. \n2. The theoretical results are complete. \n3. The paper is well-written and easy to follow. \n\nWeakness:\n1. The word \"projection-free\" is a bit misleading, as the proposed algorithm still contains a projection step which is solved by the conditional gradient method. And using the conditional gradient method to compute an approximate projection point is well-known in the literature. \n2. The experiment is not meaningful enough. LMO has complexity O(n) on the one-norm ball, and projection has complexity O(nlogn). So there is not much computational gain. From the plot, it seems that projection can actually give more stable results. I think it makes more sense to consider, for example, nuclear norm ball, where the complexity for LMO and projection are very different. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fyYt3sG0lam", "reviewer": "Reviewer_VfkJ", "summary": "The paper studied a stochastic conditional gradient method for nonconvex constrained optimization under the Markovian sampling setting, where the data comes from a Markov chain. They provide the complexity result of stochastic first-order oracle (SFO) and linear minimization oracle (LMO) for such an algorithm for achieving epsilon-stationary point.", "questions": "1. The idea of constructing an auxiliary Markov chain for bounding Markovian sampling error has already been well studied in various unconstrained problems [1] [2] [3]. Hence, it seems to me that the analysis of the proposed algorithm is a (somehow direct) combination of the theory of the conditional gradient method and the technique for dealing with Markovian sampling. \n\n2. The problem setting, stochastic constrained problems with state-dependent Markov chain dynamics in the training data, is not well motivated by the example. [LW22] considers an unconstrained problem, why is it necessary to add a constant like $\\|\\theta\\|_1 \\leq R$?\n\n3. The experiments are tiny. In addition, the author claim that the projection-free algorithm is computationally cheaper than the projection-based algorithms. However, this is not presented in the experiment. The algorithm based on projection indeed enjoys better empirical iteration complexity compared with ICG. I would expect the author to provide a time comparison.\n\n\n[1]  Doan, T. T., Nguyen, L. M., Pham, N. H., & Romberg, J. (2020). Finite-time analysis of stochastic gradient descent under markov randomness. arXiv preprint arXiv:2003.10973.\n\n[2]  Xu, T., Zou, S., & Liang, Y. (2019). Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples. Advances in Neural Information Processing Systems, 32.\n\n[3]  Wu, Y. F., Zhang, W., Xu, P., & Gu, Q. (2020). A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33, 17617-17628.\n", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-Strengths\n\nThe work considers the nonconvex constrained optimization problem under Markovian sampling, and they provide the corresponding complexity results.\n\n-Weakness\n\nSee comments below. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "a26AVW2szEl", "reviewer": "Reviewer_iPV7", "summary": "The paper considers constrained nonconvex optimization under a state-dependent Markov data setting where at each iteration, data samples are generated to a Markov chain that depends on the current parameter. Two algorithms have been analyzed and convergence rates are provided.", "questions": "1. The presentation is not so good. The author prefers to cite without explanation. For example, the author didn’t explain what is $L$ in (7). Before presenting Assumption 2.1 and 2.2, they first cite them in Proposition 1.1. The same issue happens with the introduction of Algorithm 1. In Definition 1, the definition of ϵ-stationary solution replies on another unexplained $z$. All of these make Section 1.2 hard to digest. \n\n2. The condition $\\mathbb{E}\\left[\\left\\|\\nabla F\\left(\\theta_{k}, x_{k+1}\\right)\\right\\|_{2}^{2} \\mid \\mathcal{F}_{k}\\right] \\leq \\sigma_{2}^{2}$ in Assumption 2.3 is a kind of uniformly bounded gradient assumption. Could it be relaxed to a bounded gradient assumption at the optimal point? After all, you have assume (13).\n\n3. Could the author give more explanation on the choice of step sizes in (18)? Typical choice of step sizes should be proportion to $t^{-1/2}$ or $t^{-1}$. The used exponent $-3/5$ is quite strange and no explanation is provided, while in Theorem 3.2, the used exponent follows my knowledge. The step size $t^{-a} (0.5<a<1)$ is often used to derive statistical properties and often has inferior last-iterate convergence (which can be fixed by a simple average). Does it imply the inferior oracle complexity under state-dependent MCs is due to the used step sizes?\n\n4. The paper says the proposed setting includes reinforcement learning (RL) as a special case. So could we use the mentioned methods to find the optimal policy in RL? Notice that the value function of a policy is also a non-convex but smooth function of the policy. What’s more, when we use the greedy policy with respect to the current estimator of value function to do exploration, we also meet a stochastic approximation problem with state-dependent Markov data.\n\n5. Is there any lower bound analysis on the number of LMO oracles under state-dependent Markov data? I am not sure whether the proposed is optimal, though the author says the results match previous results in the case of state-independent Markovian data.", "limitations": "See the above sections.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The key technique is to decompose the stochastic error by using the Poisson equation associated with the underlying Markov chain. The technique is not new and has been used previously in many optimization or statistics papers. The main novelty from my view is to apply the “old” technique in the “new” optimization setting and to fill the blank of theories. \n\nClarity: The paper is overall well-written.  However, some parts are somewhat hard to follow.\n\nQuality: The paper seems to be sound with all theoretical claims supported, though I didn’t check very carefully. But I feel they are correct. The experiment setting is clearly described.\n\nSignificance: The paper fills the blank of theories in optimization under Markovian data. It is related to the ML community and might inspire future work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OpmlpWLiPfZ", "reviewer": "Reviewer_6vHk", "summary": "The paper studies conditional gradient methods for stochastic optimization with state-dependent markovian data, where the expectation is taken over the stationary distribution of the random vector, utilizing a moving average gradient estimator. The paper established non-asymptotic gradient complexity and linear minimization oracle complexity.", "questions": "## Questions:\n1. What is the available data? Is it a sequence of state-dependent Markovian data given at the beginning, or is each sample in the sequence given online? I assume the latter.\n2. What is the relationship between the convergence criteria of gradient mapping, the Frank- Wolfe gap, and the performative prediction criteria used in [DX20]\n\n## Minor Comments:\n1. Lack of space in equation (11)\n", "limitations": "N.A.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. It is the first non-asymptotic result of its kind of conditional gradient method for stochastic optimization with state-dependent markovian data.\n2. The use of a moving average estimator well suits the Markovian data situation and could shed light on other gradient-based methods for state-dependent markovian data. \n\n\n## Weaknesses\n1. Assumption 2.4 is relatively strong as there exists a stationary distribution for any $\\theta$. \n2. The motivation of Algorithm 1 is less explained. Making it hard to extend the algorithmic design idea to other settings. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept