Convergence Analysis of Gradient Descent under Coordinate-wise Gradient Dominance

Authors: Yutong Chao, Jalal Etesami
Primary area: optimization
Keywords: Non-convex Optimization, Nash Equilibrium, Gradient Dominance, Strict Saddle

Abstract:
We consider the optimization problem of finding Nash Equilibrium (NE)  for a nonconvex function $f(x)=f(x_1,...,x_n)$, where $x_i\in\mathbb{R}^{d_i}$ denotes the $i$-th block of the variables. 
Our focus is on investigating first-order gradient-based algorithms and their variations such as the block coordinate descent (BCD) algorithm for tackling this problem. 
We introduce a set of conditions, termed the $n$-sided PL condition, which extends the well-established gradient dominance condition a.k.a Polyak-{\L}ojasiewicz (PL) condition and the concept of multi-convexity. This condition, satisfied by various classes of non-convex functions, allows us to analyze the convergence of various gradient descent (GD) algorithms. 
Moreover, our study delves into scenarios where the objective function only has strict saddle points, and normal gradient descent methods fail to converge to NE. In such cases, we propose adapted variants of GD that converge towards NE and analyze their convergence rates.

Decision: reject
Reviewer scores: 5, 6, 5, 5

Reviews and discussion:
<thread>
creation date:
1730214997124

thread_type:
official_review

<thread_object>
creator: reviewer_ufzd

<content>
summary:
This work explores the optimization of finding a Nash Equilibrium for nonconvex functions using first-order gradient-based algorithms and their variations, such as block coordinate descent. The authors introduce the n-sided PL condition, an extension of the PL condition. Then, under this condition, they analyze the convergence of various variants of gradient descent algorithms. They provide theoretical proofs of convergence rates for these algorithms and examine conditions under which linear convergence can be guaranteed.

strengths:
The main strengths of this work are:
-The authors extended the PL condition to the n-sided PL condition. 
-The authors proposed adapted variants of the gradient descent (GD) and block coordinate descent (BCD) algorithms and demonstrated the convergence to Nash Equilibrium of these methods.
-The authors provided theoretical proofs for the convergence rates of the proposed algorithms and established conditions under which linear convergence can be guaranteed.
-The authors provide some numerical tests to validate their claims.

weaknesses:
The main weaknesses of this work are:
-Dependence on Strong Assumptions: I understand that the authors gave some toy examples and linear NN that satisfy the assumptions however in general these assumptions remain strong and hard to check.
-The empirical validation is focused on simple toy examples and linear NN. The performance of the proposed algorithms on large-scale or more complex problems is not deeply explored, making it uncertain how well the algorithms scale in practice. The authors may consider including some tests on bigger problems to assess the numerical efficiency of the proposed variants, even if the conditions to converge are not necessarily satisfied.
-The paper lacks a detailed computational complexity analysis of the proposed variants (the cost per iteration compared to the classical GD or BGD). The added steps (like approximating best responses in certain cases) introduce computational overhead, especially for high-dimensional data, and it’s unclear how these adaptations perform against standard or simpler gradient-based methods in terms of cost/runtime.
-The adaptive algorithms, particularly with the introduction of conditions for selecting step sizes and updating directions, could be challenging to implement efficiently in practice.

questions:
-See the previous section.
-Lines 251-252 you mentioned "The above result ensures the convergence of BCD to the NE set, but it does not necessarily indicate whether the output converges to a point within the NE set." can you give an example where this is the case? i.e. we have the convergence to the NE set but not the convergence to a point in the set. 
-Line 292: can you explain why f(x) = G_f(x) if and only if x is NE.
-Assumption 3.4. you require the condition (5) for a given set of points. But how can one know this set of points beforehand? you mentioned just after that for instance, for f_0 this assumption is valid for some domain, but the iterations of a given algorithm applied to this problem may leave this domain in the middle of the algorithm.
-Can you tell why Ass 3.4 for instance holds for strongly convex functions?
-In thm 3.6 in the linear rate of convergence, since \mu, \alpha and \kappa "do not depend" on "n" this rate can be negative for large "n"?
-Definition 3.8, do you really need the minimum to be zero?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730529098009

thread_type:
official_review

<thread_object>
creator: reviewer_eujj

<content>
summary:
This paper focuses on the convergence rates of block coordinate descent algorithms under an $n$-sided PŁ condition. Based on an adaptive, theoretical algorithm IA-RBCD that provably converges to the NE of a minimization problem of an $n$-sided PŁ objective, the paper proposes a novel algorithm A-RBCD that is implementable via computing the approximate best response and shows the same convergence speed as the ideal version. The paper also shows empirical results in various practical settings involving $n$-sided PŁ functions.

strengths:
- I believe that extending ideas from convex/nonconvex or minimax optimization to multi-player games is a valuable direction to study and develop further. The $n$-PŁ condition might be useful in many cases, especially in handling stuff on nonconvex (and nonconcave) games.
- Experiments are well-aligned with the theorems. The results all demonstrate and support exactly what’s in the theoretical statements.
- The overall writing is clear and easy to follow.

weaknesses:
- **W1.** I don’t get why and when could finding an NE for a *minimization* problem be an important thing. In Figure 1, the set of stationary points (which is equal to the set of Nashes for $n$-PŁ functions) might contain saddle points. Indeed we would want to find Nashes for minimax or multi-player game settings, but for (nonconvex) minimization problems it’s usually also important to *avoid* possible saddles among stationary points (Lee et al., 2016). I get that there might be cases when we won’t care about saddles and just want to find stationary points, maybe as in the example function with only strict saddles points in Section 4, but still, I think it’s not clear in the paper about why this search for NE’s and the $n$-PŁ assumption could be a really necessary or interesting thing.
- **W2.** In the theorems, everything related to Case 3 makes the theoretical contribution of this paper quite weak. While empirical results in Figure 5 suggest that Case 3 never really happens here, there should have been a better explanation than just saying ‘rigorously verifying these cases is intractable’. There are no lower bound results, i.e., which means that there could be pathological cases that get stuck in Case 3 for a long time, and the $n$-PŁ assumption isn’t powerful enough. In fact, we already need a stronger $(\nu, \theta)$-PŁ assumption to get non-asymptotic results for Case 3, which is even sublinear.
- **W3.** Continuing from **W2**, the main results all state no more than case-specific one-step contraction inequalities. These should have been conclusively rewritten in terms of iteration complexities for a complete understanding of the convergence rate of this algorithm. This will include quantifying how rare Case 3 happens (or maybe when exactly can we make it rare), and seeing what convergence rate we get after fixing a single step size (or possibly a schedule) considering all three cases.

questions:
- Can you explain further about what I wrote in W1? When could it be important to find Nashes in minimization problems? Or, in a slightly different perspective, could these algorithms generalize to multi-player games with adversarial components?
- Have you checked if the proposed algorithms are capable of further avoiding saddles if possible either explicitly, or in some sort of an ‘implicit-bias’ sense? We don’t have any evidence proving/disproving this since, in the experiments in the paper, for the first quadratic case the only option is a saddle, while for the rest of the cases, we can only see $f(x) - G_f(x)$ from which we cannot distinguish saddles from minima.
- Case 3 happens when the vectors $\nabla f(x_t)$ and $\nabla G_f(x_t)$ are not well-aligned (or $\| \nabla G_f(x_t) \|$ is much larger than $\| \nabla f(x_t) \|$… which probably won’t happen). While by definition of $G$ it seems intuitive that the two gradients will eventually align together near the stationary points (while both converging to zero vectors), are there any ideas to quantify or theoretically analyze this part a bit further?

TYPO. Page 6, converges sublinearly for $f_1$ (instead of $f_2$)

TYPO. Algorithm 4, $x_{-j}^t \rightarrow x_{-j}$ (while we use $x = x^t$ in Algorithm 3)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691643667

thread_type:
official_review

<thread_object>
creator: reviewer_mncc

<content>
summary:
The paper focuses on the problem of finding Nash Equilibrium for function $f(x)$ having a block form $f(x)=f(x_1, …, x_n)$. The paper introduces $n$-sided PL condition which extends the notion of PL condition to functions with block structure. Under this weaker assumption the algorithm Block Coordinate Descent is analyzed and its convergence to set of NE points is proven. Under additional assumption on the alignment of gradients of $f$ and $G_f$, linear convergence of BCD and vanilla GD is proven. Furthermore, the algorithms Adaptive randomized Block Coordinate Descent and its oracle version are proposed and their convergence rate is analyzed without the additional assumption on gradient alignment.

strengths:
Overall, the paper is well written and uses simple examples to provide intuition for important concepts. The strengths of the paper are as follows:
1. The assumption $n$-sided PL condition introduced in the paper is a weaker notion than two-sided PL condition making the results more general. The assumption is weaker in the sense that under this the stationary points are not guaranteed to be global minimums.
2. Linear convergence guarantee is proven for BCD and GD under $n$-sided PL condition and gradient alignment assumption.

weaknesses:
1. Insufficient empirical evidence presented for demonstrating the benefits of the proposed variant: a. Comparison with BCD method is missing for the experiments with Linear Residual Network and Infinite Horizon $n$-player LQR game. It gives empirical comparison of convergence rate of BCD and A-RBCD which would be helpful. b. The variant A-RBCD requires significantly more gradient computation than BCD. It would be beneficial to have comparison keeping the gradient computation budget constant across different methods. c. Furthermore, adding SGD and Adam as baselines would make the experiments more persuasive.

questions:
1. It would be helpful to highlight the differences between IA-RBCD and A-RBCD that arise due to using approximate best responses.
2. The Figure 5d is used to claim that the third case does not occur while executing the A-RBCD algorithm. I suppose the point being made is that $\rho\leq \gamma-\gamma\frac{\alpha^3}{13}$. A clarification regarding the same would be appreciated. If the graph could indicate the line $y=\gamma-\gamma\frac{\alpha^3}{13}$ that would make it much easier to understand.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730904303775

thread_type:
official_review

<thread_object>
creator: reviewer_cw3t

<content>
summary:
The paper focuses on solving non-convex problems and, in particular, aims to design methods for finding Nash Equilibrium. The paper proposes the n-sided PL condition and provides convergence guarantees for different block coordinate descent methods (BCD, IA-RBCS,  and A-RBCD) under this new assumption. Applications of where the assumption is satisfied and some preliminary experiments are presented.

strengths:
The paper is well-written, and the idea is easy to follow. The authors did a very nice job in the narrative of the paper. The explanation of their new assumption, applications of where this assumption appears, and the theoretical analysis are clearly presented.

weaknesses:
I believe there are a few issues in terms of using specific terminology that are not standard, and the author might need to revise. 

1. The notion of Nash Equilibrium (NE) is very popular in min-max problems and multi-agent games. However, the paper focuses on pure minimization problems and defines NE as a standard concept, which is not typically the case. How is their NE equilibrium related to the minimizer of the function they are trying to optimize? This i believe was not clearly presented in the paper. 

2. I believe the notion G_f(x) should be more carefully presented and explain why this is a valid measure of convergence. Why is showing that f(x^t) - G_f(x^t) reduces enough to guarantee convergence to global minima (again, this is related to the notion of NE)? I would appreciate it if the authors provide more details on this. 

3. Why does Assumption 3.4 make sense? This looks like a very artificial condition to have just to make the proof work. This shows that one example (in Fig 1) satisfies, but that does not mean that this is a relaxed condition. More explanation is needed

4. The paper is clearly theoretical, but I would appreciate it if the authors compared their proposed method with state-of-the-art approaches for training Linear Residual Networks and Infinite Horizon n-player Linear-quadratic (LQR) Game. In my opinion, this is very important for the paper as then it would convey the message that through the new assumption, we not only provide new convergence guarantees but that via the new analysis and algorithms, we can more efficiently solve these practical problems.

questions:
See Weaknesses above
</content>
</thread_object>

</thread>
<thread>
creation date:
1732107635575

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response 1/2

comment:
We thank the reviewers deeply for their thoughtful and in-depth reviews of our draft. To efficiently address all concerns, we provide a General Response section, which serves as an additional discussion and clarification to points raised by multiple reviewers that overlap in terms of topic. We hope that the additional discussion will improve our understanding of our work further and resolve outstanding questions.  

We have also revised the manuscript with relatively minor updates addressing typos, minor adjustments to diagrams, and adjustments to theorems.

$\textbf{Question 1:}$ The importance of $n$-sided PL condition.

This paper focuses on finding NE for a potential function, which is the main topic in multi-agent potential games [1]. In the potential games, the incentive of all agents to change their strategy can be expressed in one global function. It has many applications, such as reinforcement learning [2,3], power control [4], and network theory [5], etc. The existing work, however, has strict assumptions on the potential function, for example, the strong convexity and the PL condition to provide a convergence rate. These conditions, however, can be problematic for games with multiple NEs with different function values [6]. The $n$-sided PL condition, on the one hand, guarantees the existence of a solution for every best-response problem and, on the other hand, accepts the condition when multiple NE exists.

$\textbf{Question 2:}$ The reason $f-G_f$ is a reasonable measure.

The idea of the best response function and its related dynamics exist in the literature [7,8,9]. From the definition of $G_f$, it is straightforward to see $f-G_f\geq 0$. In the new version of our paper, we prove the equivalence of $f(x^\star)-G_f(x^\star)=0$ and $x^\star$ being a NE point without any further assumption. This is helpful for the cases where multiple NE exists since they might have different function values on $f$, but their value on $f-G_f$ is the same.

$\textbf{Question 3:}$ The idea of assumption 3.4 (assumption 3.5 in the new version) and its illustration.

Please note that our algorithms do not solely rely on this assumption, as this assumption is only one of the three cases in our algorithm. This condition, however, explains why gradient descent on $f$ doesn't converge to NE when the NE is a saddle [10]. Moreover, in Appendix F, we further show that, on average, this assumption is satisfied for strongly convex functions.

$\textbf{References:}$

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

[2] Ding, D., Wei, C. Y., Zhang, K., Jovanovic, M. (2022). Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning (pp. 5166-5220). PMLR.

[3]Fox, R., Mcaleer, S. M., Overman, W., Panageas, I. (2022). Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics (pp. 4414-4425).

[4] Liu, W., Xu, H., Wang, X., Zhang, S., Hu, T. (2022). Optimal dispatch strategy of virtual power plants using potential game theory. Energy Reports, 8, 1069-1079.

[5] Moragrega, A., Closas, P., Ibars, C. (2015). Potential game for energy-efficient RSS-based positioning in wireless sensor networks. IEEE Journal on Selected Areas in Communications, 33(7), 1394-1406.

[6] Pozo, D., Contreras, J. (2011). Finding multiple nash equilibria in pool-based markets: A stochastic EPEC approach. IEEE Transactions on Power Systems, 26(3), 1744-1752.

[7] Caruso, F., Ceparano, M. C., Morgan, J. (2020). An inverse-adjusted best response algorithm for Nash equilibria. SIAM Journal on Optimization, 30(2), 1638-1663.

[8] Amiet, B., Collevecchio, A., Scarsini, M., Zhong, Z. (2021). Pure Nash equilibria and best-response dynamics in random games. Mathematics of Operations Research, 46(4), 1552-1572.

[9] Laraki, R., Baudin, L. (2022). Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions.  NeurIPS 2022.

[10] Lee, J. D., Simchowitz, M., Jordan, M. I., Recht, B. (2016). Gradient descent converges to minimizers. COLT 2016
</content>
</thread_object>

</thread>
<thread>
creation date:
1732629764568

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response 2/2

comment:
Once again, we thank the reviewers for their thoughtful feedback on our rebuttal. Since Assumption 3.5, and particularly the theoretical guarantees regarding the frequency of case 3, were questioned, we would like to provide the following clarification. 

$\textbf{In the newly added Theorem F.2}$ in Appendix F, we further provide a bound for the measure of the set of points satisfying case 3 and an upper bound for $f-G_f$ over this set.
In particular, we show 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 the size of the set of points satisfying case 3 shrinks as $\gamma\to 1$ and $C\to 0$, and even if the algorithms enter case 3 and experience a sublinear convergence rate, we can 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733235615690

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Official Comment by Authors

comment:
We sincerely thank the reviewers for their efforts and valuable feedback. The reviewers provided excellent constructive comments and insightful discussions.
To highlight our main contributions: this paper introduces an extension of the PL condition in nonconvex optimization. Under this extended notion, we provide theoretical guarantees for convergence toward Nash Equilibrium using the proposed first-order gradient-based algorithms. These algorithms adjust the update rule based on three possible scenarios. We demonstrate linear convergence in the first two scenarios and sublinear convergence in the third one.

As noted by the reviewers, we have added a new theorem to analyze the rarity of case 3 and illustrated the frequency of case 1 for strongly convex functions. We also included a performance comparison in the experimental section. The manuscript has been revised with minor updates, including corrections of typos, improvements to diagrams, adjustments to definitions and lemmas.

Kind regards, Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the optimization of finding Nash Equilibria for non-convex functions with a block structure, introducing the novel n-sided PL condition, which generalizes the PL condition to such settings. The authors analyze the convergence of gradient-based algorithms, including Block Coordinate Descent (BCD) and its adaptive variants (IA-RBCD and A-RBCD), proving convergence rates and linear convergence under specific gradient alignment assumptions. They further propose A-RBCD, a practical algorithm that approximates the best response and achieves the same convergence speed as its theoretical counterpart. Empirical results demonstrate the effectiveness of these methods in practical scenarios satisfying the n-sided PL condition.