Etesami group
A novel convergence analysis for the optimization of Polyak-Lojasiewicz Condition
We consider the optimization problem of non-convex function
| \min_{x\in\mathbb{R}^d}f(x)=f(x_1,...,x_n), |
where
| x_i\in\mathbb{R}^{d_i} |
is the i-th block of the variables. By generalizing the well-known Polyak-Lojasiewicz (PL) condition and multi-convexity condition, we propose the n-sided PL condition, which is satisfied by numerous classes of non-convex functions. We study the block coordinate descent algorithm and introduce a set of sufficient conditions under which it converges to the global solution of Nash Equilibrium (NE). This result can be applied to a more general setting when the objective function does not have any global NE. In this ill-conditioned case, convergence to the local NE can be obtained by modifying the algorithm.