Convergence Analysis of Gradient Descent under Coordinate-wise Gradient Dominance

We appreciate your comprehensive review and valuable feedback of our paper. We would like to address each of your questions.

$**Weakness 1:**$ As pointed out by the reviewer, our linear convergence rate results are established under additional assumptions, i.e., $n$-sided PL condition. It is worth noting that this assumption is weaker conditions than the strong convexity. Specifically, if a function is strongly convex with respect to $x_i$ while keeping the other coordinates fixed, it satisfies the $n$-sided PL condition. This indicates $n$-sided PL condition can be verified straightforwardly, as it requires the positive definiteness of the corresponding diagonal block of the Hessian matrix. Also, we would like to emphasize that achieving linear convergence is a significant result, as it is typically established under stronger assumptions in the literature, such as strong convexity or strong PL condition.

$**Weakness 2:**$ Please note that this work is mainly theoretical and focuses on establishing the convergence rate for non-convex problems that satisfy the n-sided PL condition. We also tried to empirically verify our theoretical findings using simple but not that small size problems. For example, we compared our algorithms with the state-of-the-art algorithm (RBCD) with functions up to 20 dimensions. We expect similar results for higher dimensions, as our algorithms are only a constant factor slower than RBCD since they require a constant factor more gradient computations than RBCD. But our algorithm enjoy theoretical guarantees which is missing in the literature for non-convex objective functions.

$**Weakness 3:**$ We propose IA-RBCD in Algorithm 2 and A-RBCD in Algorithm 3. Please note that both of them require only a constant factor of more gradient computations than BCD. This is because IA-RBCD needs to compute the gradient of $G_f$ in addition to the BCD. The A-RBCD algorithm requires additional gradient computations to approximate $G_f(x)$, denoted by $T'$, which depends solely on the parameters of the objective function and is independent of the final precision of $f - G_f$. This means that, in each iteration, A-RBCD incurs only a constant factor of additional gradient computations compared to IA-RBCD, with the factor determined by properties of the objective function such as smoothness and $\mu$. Compared with IA-RBCD, A-RBCD only cost $\mathcal{O}(\log(n))$ times more, where $n$ is the number of blocks. And we should also notice that our algorithm still works even stably if the function is not lower-bounded or the NE is saddle point.

$**Weakness 4:**$ In fact, implementing the proposed algorithms are quite similar to standard BCD. The main difference is the subdivision into three cases which are quite straightforward to implement. Please note that we have uploaded the code along with the paper as well.

$**Question 1:**$ Please note that such examples could be found in the literature. For example, please see the introduction of [1] in which the authors mentioned an example built by H. B. Curry in "The method of steepest descent for non-linear minimization problems''. The example is "Let $G(x, y)=0$ on the unit circle and $G(x, y)>0$ elsewhere. Outside the unit circle let the surface have a spiral gully making infinitely many turns about the circle. The path $C$ will evidently follow the gully and have all points of the circle as limit points.''

$**Question 2:**$ We would like to thank the reviewer for the constructive comments. It is important to emphasize that the primary goal of this paper is to find the NE, rather than the global minimizer. Furthermore, having $f(x^\star)-G_f(x^\star)=0$ is equivalent to have $x^\star$ is a NE. Notice that at NE, no player can improve its payoff by deviating from its current strategy. This implies that if $x^\star$ is a NE, $f(x^\star)=\min_{x_i}f(x_i,x_{-i}^\star)$, $\forall i$ or $f(x^\star)=G_f(x^\star)$. Conversely, if $f(x^\star)-G_f(x^\star)=0$, then $\sum_{i} [f(x^\star)-\min_{x_i}f(x_i,x_{-i}^\star)]=0$. So we have $f(x^\star)-\min_{x_i}f(x_i,x_{-i}^\star)=0$, $\forall i$. Therefore, we can conclude that $x^\star$ is a NE if and only if $f(x^\star)-G_f(x^\star)=0$. We will revisit the statement of Theorem 3.3 to provide more clarification in the final version of the paper.

$**Question 3:**$ Please note that our algorithms do not require prior knowledge of these points. It is important to highlight that the primary reason for incorporating three different cases in both IA-RBCD and A-RBCD is to update the point based on the position of the current iterate. In particular, condition (5) corresponds to one of these three cases.

Thank you for your comments.

$**Q-3 and Q-4:**$ As noted in the paper and highlighted by the reviewer, we neither provide a theoretical guarantee for when the first case (i.e., when Assumption 3.5 holds) of the presented algorithms is satisfied, nor have we been able to disprove it by identifying a counterexample under the strongly convex condition near the NE points.

However, we can argue the following points to support that Assumption 3.5 is an appropriate tool for analyzing the BCD algorithm. Furthermore, as $\gamma \to 1$ and $C\to 0$, it becomes increasingly likely to eliminate case 3.

To support this statement, we present a new theorem in Appendix F, which demonstrates that the measure of the set of points not satisfying case 1 or case 2 converges to zero as $\gamma\to 1$ and $C\to 0$. Moreover, the maximum of $f-G_f$ over this set of points also converges to 0. This indicates that even if we enter case 3 and experience a sublinear convergence rate, we can still ensure that $f-G_f$ is small at these points.

In addition, even if the third case of the algorithms (e.g., when assumption 3.5 is violated) occurs at most $c_0 T$, where $c_0<1$, then we can still guarantee the linear convergence of $f-G_f$ using Theorems 3.10 and 3.11. Please note that $c_0 T$ is not negligible.

Last but not least, we empirically verify how often the third case occurs (Fig. 4 (d) ) and show that it happens quite rarely, which again verifies our arguments.

$**Q-5:**$ Please note that

$

f(x)-G_f(x)=\frac{1}{n}\sum_{i=1}^n\big(f(x)-f(x^\star_i(x),x_{-i})\big),

$

and for every $i$, $f(x)-f(x^\star_i(x),x_{-i})\geq0$ because $x^\star_i(x)$ is the best response to $x_{-i}$. This already shows that the left hand side of the inequality in Theorem 3.7, i.e.,

$

f(x^{t+1})-G_f(x^{t+1})\leq \Big(1-\frac{n\mu\alpha(1-\kappa)}{2}\Big)(f(x^t)-G_f(x^t)).

$

is positive and therefore $(1-\frac{n\mu \alpha(1-\kappa)}{2})$ is also nonnegative. To see why the above inequality holds, please see the proof of Theorem 3.7 which uses the smoothness and n-sided PL condition of the function $f$.

$**Q-6:**$ Please note that in this case, the function $f$ satisfies the $(\theta,\nu)$-PŁ condition iff there exists $\theta \in[1,2)$ and $\nu>0$ such that $\|\nabla f(x)\|^\theta \geq(2 \nu)^{\theta / 2} (f(x)-\min_x f(x)).$ This doesn't change the result of Theorem 3.10 and Theorem 3.11.

We thank for your reviews and valuable insights, which could be much helpful for improving and clarifying our paper. We would like to address your each concern in detail.

$**Weakness 1 and Question 1:**$ Finding Nash Equilibrium is important in the potential game literature[1], for example, in reinforcement learning[2] and network theory[3]. In such games, agents often aim at finding an NE using partial information about the full gradient vector of the potential function. To achieve such NE for the agents, we introduced the $n$-sided PL condition. This condition guarantees the existence of a solution for every agent's subproblem, i.e., $\min_{x_i} f(x_i,x_{-i})$, and also an efficient algorithm for finding the NE when only partial gradient is available. Secondly, it enables us to solve a broader set of problems as we do not need the objective function to be lower-bounded, unlike the previous methods. Please note that a function could satisfy the $n$-sided PL condition but not lower-bounded. Moreover, the process of finding an NE is not always guaranteed to be stable[4]. For instance, strategies may diverge when agents simply apply gradient descent to the potential function.

It is noteworthy that games with adversarial players could also be included in our problem setting. More precisely, consider an objective function $f$ that depends on $x_1,\cdots,x_n$ and $z$, where $x_i$ is the coordinate corresponding to the $i$-th player and $z$ is the coordinate of an adversarial agent. The players' goal is to minimize the objective function while the adversarial agent aims at maximizing it. Thus, we have

$

\begin{aligned} &\min g(x_1,\cdots,x_n)=f(x_1,\cdots,x_n,z^\star(x_1,\cdots,x_n)),\ &\mathrm{s.t.}\ z^\star(x_1,\cdots,x_n)\in\mathrm{argmax}_z f(x_1,\cdots,x_n,z). \end{aligned}

$

Note that the above problem is a minimization problem for the objective function $g$ and it is in the scope of our paper.

$**Weakness 2:**$ Please note that the GD dynamic (iterates $\{x^t\}$ generated by the algorithm) of a smooth function could potentially visit case 3. However, by choosing hyper-parameters (in Algorithms 2 and 3) $\gamma$ close to one and $C$ close to zero, we can reduce the area for which case 3 occurs. Thus, we can reduce the number of times that the GD dynamic visit the third case. In this work, we did not characterize functions for which the GD dynamic never visit the third case as it is quite challenging and it is left for future investigations. But, we showed empirically (Fig. 5 (d) ) that such visits to case 3 is quite rare during the updates. Moreover, based on our analysis in Appendix F, the dynamic of GD remains outside or on the boundary of the area of case 3 in average by choosing $\gamma$ close to one.

$**Weakness 3:**$ We thank the reviewer for the helpful suggestion. We avoid to preset the precise contraction inequality as a function of number of total rounds only for simplicity and the fact that we do not have any bound on how often the algorithm visits case 3. However, it is quite straightforward to obtain such inequality by assuming that the algorithm visits case 3 at most $T_3$ rounds out of total $T$ rounds. In this case, for $\alpha$ small enough, we have

$**Question 2:**$ We would like to thank the reviewer for the valuable question. To this question, $**yes**$. Please note that it is possible that the conditions for case 1 and case 2 are both satisfied. If the case 1 of the algorithm occurs during the updates (the algorithm checks the first case before moving to the other cases), then we only use the partial gradient of $f$ and no information of the gradient of $G_f$. On the other hand, from Lee et al. (2016), we know that if only the information of the gradient of $f$ is used to find a stationary point, then the iterates almost surely escape the saddle point when the initialization is random.

$**Question 3:**$ Understanding when and how often case 3 occurs is an interesting but also challenging problem. In Appendix F, we further studied this case and provide some related results for the gradient dynamics. In short, we could show that for a smooth function, when the iterates are close enough to an isolated NE, $\langle \nabla f(x^t),\nabla G(x^t)\rangle\leq\|\nabla f(x^t)\|^2$ holds in average. Furthermore, when the function is strongly convex, then there exists $0<\gamma<1$ such that $\langle \nabla f(x^t),\nabla G(x^t)\rangle\leq\gamma\|\nabla f(x^t)\|^2$ holds in average.

Thank you for your comment.

For your consideration, in Appendix F, we present our new theorem that as $\gamma\to 1$ and $C\to 0$, then the set of points doesn't satisfy case 1 and case 2 has its measure converge to 0. Also, the maximum of $f-G_f$ over this set converges to 0. This indicates the area that satisfies case 3 can be very small. What's more, even if we enter case 3 and have a sublinear convergence rate, we can still make sure $f-G_f$ is small enough at that time.

We appreciate your comprehensive review and valuable feedback of our paper. We would like to address each of your questions.

$**Weakness 1.a:**$ We thank the reviewer for the valuable suggestion and we have the comparision between these methods in the new version. Indeed, this work is primarily theoretical, focusing on providing convergence guarantees and analyzing the convergence rates of various block coordinate descent (BCD) algorithms under the n-sided PL condition. This contribution represents a novel addition to the field. In our experiments, we observed that our algorithms exhibit comparable convergence rates to state-of-the-art approaches in LRN and n-player LQR games. However, it is important to highlight a key distinction: unlike the state-of-the-art methods for these types of games, our BCD-based approaches can find NE even when the objective function is not lower bounded or agents do not share their strategies with one another. Specifically, our methods allow agents to individually update their own coordinates using partial gradients, rather than relying on the full gradient vector.

$**Weakness 1.b:**$ We propose A-RBCD in Algorithm 3 and IA-RBCD in Algorithm 2. Please note that both of them require only a constant factor of more gradient computations than BCD, and are independent of the final precision of $f-G_f$. This is because IA-RBCD needs to compute the gradient of $G_f$ in addition to the BCD. The A-RBCD algorithm requires additional gradient computations to approximate $G_f(x)$, denoted by $T'$, which depends solely on the parameters of the objective function and is independent of the final precision of $f - G_f$. This means that, in each iteration, A-RBCD incurs only a constant factor of additional gradient computations compared to IA-RBCD, with the factor determined by properties of the objective function such as smoothness and the number of blocks $n$. Compared with IA-RBCD, A-RBCD only cost $\mathcal{O}(\log(n))$times more, where $n$ is the number of blocks. We should also notice that our algorithm still works even if the function is not lower-bounded or the Nash Equilibrium is a saddle point from the example in the Figure 3.

$**Weakness 1.c:**$ In line with such comparisons to baseline methods, we selected a more relevant algorithm: random block coordinate descent, which is an SGD-based method. Please note that in expectation, random block coordinate descent behaves similarly to SGD. We then compared our algorithm against this baseline to provide a meaningful evaluation.

$**Question 1:**$ We thank the reviewer for the valuable suggestion. We have added couple of sentences after algorithm 3 to highlight the differences between IA-RBCD and A-RBCD.

$**Question 2:**$ We thank the reviewer for the valuable suggestion. We have added the line $y=\gamma-\gamma\frac{\alpha^3}{13}$ to the figure for more clarification.

Thank you for your comments.

However, we can argue the following points to support that Assumption 3.5 is an appropriate tool for analyzing the BCD algorithm. Furthermore, as $\gamma \to 1$ and $C\to 0$, it becomes increasingly likely to eliminate case 3.

To support this statement, we present a new theorem in Appendix F, which demonstrates that the measure of the set of points not satisfying case 1 or case 2 converges to zero as $\gamma\to 1$ and $C\to 0$. Moreover, the maximum of $f-G_f$ over this set of points also converges to 0. This indicates that even if we enter case 3 and experience a sublinear convergence rate, we can still ensure that $f-G_f$ is small at these points.

In addition, even if the third case of the algorithms (e.g., when assumption 3.5 is violated) occurs at most $c_0 T$, where $c_0<1$, then we can still guarantee the linear convergence of $f-G_f$ using Theorems 3.10 and 3.11. Please note that $c_0 T$ is not negligible.

Last but not least, we empirically verify how often the third case occurs (Fig. 4 (d) ) and show that it happens quite rarely, which again verifies our arguments.

Thank you for taking the time to review this paper. We appreciate the constructive feedback and would like to address the comments below:

$**Weakness 1**:$ Finding Nash equilibria (NE) is a central topic in the literature on multi-agent potential games [1] such as multi-agent reinforcement learning[2]. In potential games, each agent seeks to minimize a unified potential function while having limited knowledge of the strategies of other agents. The NE in such games represents a point of strategic stability, where no agent can improve their payoff by unilaterally deviating from their current strategy. It is important to note that a NE does not necessarily coincide with the global minimum of the potential function. Moreover, the process of finding an NE is not always guaranteed to be stable [3]. For instance, strategies may diverge when agents simply apply gradient descent to the potential function. As discussed on pages 4 and 5 and illustrated in Figure 1, there can also be multiple NEs. In such cases, it becomes impossible to guarantee that the identified NE corresponds to the global minimum of the potential function. We will provide a more detailed explanation of these points in the introduction and Section 2 of the final version.

$**Weakness 2**:$ We would like to thank the reviewer for the constructive comments. It is important to emphasize that the primary goal of this paper is to find the NE, rather than the global minimizer. Furthermore, having $f(x^\star)-G_f(x^\star)=0$ is equivalent to have $x^\star$ is a NE. Notice that at NE, no player can improve its payoff by deviating from its current strategy. This implies that if $x^\star$ is a NE, $f(x^\star)=\min_{x_i}f(x_i,x_{-i}^\star)$, $\forall i$ or $f(x^\star)=G_f(x^\star)$. Conversely, if $f(x^\star)-G_f(x^\star)=0$, then $\sum_{i} [f(x^\star)-\min_{x_i}f(x_i,x_{-i}^\star)]=0$. So we have $f(x^\star)-\min_{x_i}f(x_i,x_{-i}^\star)=0$, $\forall i$. Therefore, we can conclude that $x^\star$ is a NE if and only if $f(x^\star)-G_f(x^\star)=0$. We will revisit the statement of Theorem 3.3 to provide more clarification in the final version of the paper.

$**Weakness 3**:$ Although the statement of Assumption 3.4(the assumption 3.5 in the new version) may seem artificial, it essentially asserts that the vectors $\nabla f(x_t)$ and $\nabla G_f(x_t)$ are well-aligned. Intuitively, this alignment is expected based on the definition of $G_f$ in the vicinity of isolated NEs.
This intuition has been rigorously justified on average in Appendix F and mentioned before Lemma 3.7. Specifically, we demonstrated in Appendix F that around every isolated minimum of smooth functions, this assumption holds on average for all iterates of the GD algorithm. It is important to note, however, that this assumption does not hold globally. This limitation is the primary reason we have further divided our algorithm into three distinct cases.

$**Weakness 4**:$ We thank the reviewer for the valuable suggestion. Indeed, this work is primarily theoretical, focusing on providing convergence guarantees and analyzing the convergence rates of various block coordinate descent (BCD) algorithms under the n-sided PL condition. This contribution represents a novel addition to the field. In our experiments, we observed that our algorithms exhibit comparable convergence rates to state-of-the-art approaches in LRN and n-player LQR games. However, it is important to highlight a key distinction: unlike the state-of-the-art methods for these types of games, our BCD-based approaches can find NE even when the objective function is not lower bounded or agents do not share their strategies with one another. Specifically, our methods allow agents to individually update their own coordinates using partial gradients, rather than relying on the full gradient vector.

$**References**$

[1] Monderer, D. and Shapley, L. S. (1996). Potential games. Games and economic behavior, 14(1):124–143.

[2] Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. (2021). Global convergence of multi-agent policy gradient in markov potential games. ICLR 2022.

[3] Carmona, G. (2013). Existence and stability of Nash equilibrium. World scientific.

Thank you for your reviews and suggestions on this paper. We wanted to kindly remind you that the deadline for authors to make revisions to the manuscript is approaching soon (Nov. 27 AoE). While the discussion period has been generously extended by the ICLR committee until Dec. 2 AoE, revisions to the manuscript can only be made before Nov. 27 AoE.

We believe your initial feedback has been very beneficial in clarifying and improving upon our paper. We have already made some revisions under the suggestions from your review and the other reviewers alike, if there are any remaining concerns or suggestions that you feel would benefit from additional updates to the manuscript, we would be very grateful to hear from you before Nov. 27 AoE.

After that date, we are happy to patiently continue the discussion until the end of the discussion period to clarify questions and concerns. Thank you so much for your time and effort in reviewing our work, we appreciate it.