Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: -Strengths

The work considers the nonconvex constrained optimization problem under Markovian sampling, and they provide the corresponding complexity results.

-Weakness

See comments below. 
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. 

2. 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$?

3. 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.


[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.

[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.

[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.

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: ## Strengths
1. It is the first non-asymptotic result of its kind of conditional gradient method for stochastic optimization with state-dependent markovian data.
2. 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. 


## Weaknesses
1. Assumption 2.4 is relatively strong as there exists a stationary distribution for any $\theta$. 
2. The motivation of Algorithm 1 is less explained. Making it hard to extend the algorithmic design idea to other settings. 
questions: ## Questions:
1. 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.
2. What is the relationship between the convergence criteria of gradient mapping, the Frank- Wolfe gap, and the performative prediction criteria used in [DX20]

## Minor Comments:
1. Lack of space in equation (11)

limitations: N.A.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 

Clarity: The paper is overall well-written.  However, some parts are somewhat hard to follow.

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

Significance: The paper fills the blank of theories in optimization under Markovian data. It is related to the ML community and might inspire future work.
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. 

2. 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).

3. 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?

4. 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.

5. 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Strength:
1. Constrained stochastic optimization problems with Markovian data are important in the ML community. 
2. The theoretical results are complete. 
3. The paper is well-written and easy to follow. 

Weakness:
1. 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. 
2. 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. 
questions: 1. See weakness points. 
2. 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
review_title: null

Meta-review: metareview: The paper considers constrained smooth nonconvex problems in a stochastic setting where the data comes from a Markov chain. For this setting, the paper proposes an algorithm that converges to an $\epsilon$-stationary point with stochastic oracle complexity $1/\epsilon^{2.5}$. The paper further shows that in the settings where the projection oracle is expensive to compute (e.g., under nuclear norm constraints), the algorithm can be implemented with $\mathcal{O}(\frac{1}{\epsilon^{5.5}})$ calls to a linear minimization oracle. On the technical side, the principal contributions are in designing a novel moving-average gradient estimator suitable for Markovian data and in designing an auxiliary Markov chain based on a noise decomposition idea (similar to [AMP05]), whose iterates are close to the iterates of the original algorithm. The analysis is sufficiently general to handle both constrained and unconstrained settings. 

The motivation for studying the considered problems comes from strategic classification (an example used in the numerical experiments provided in the paper) and reinforcement learning. These problems are of high interest to the ML community and the contributions of the paper seem sufficient. The results will plausibly lead to more developments in this area. 
confidence: Less certain
Decision: Accept