Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems
This provides a solution for nonconvex-nonconcave min-max problems, such as robust least squares estimation, with accelerated convergence, though it is incremental in relaxing assumptions rather than introducing a new paradigm.
The paper tackles min-max problems without requiring strong convexity-concavity by proposing a saddle point dynamical system that guarantees fixed-time convergence under the two-sided Polyak-Łojasiewicz inequality, achieving arbitrarily fast convergence compared to state-of-the-art methods.
This study develops a fixed-time convergent saddle point dynamical system for solving min-max problems under a relaxation of standard convexity-concavity assumption. In particular, it is shown that by leveraging the dynamical systems viewpoint of an optimization algorithm, accelerated convergence to a saddle point can be obtained. Instead of requiring the objective function to be strongly-convex--strongly-concave (as necessitated for accelerated convergence of several saddle-point algorithms), uniform fixed-time convergence is guaranteed for functions satisfying only the two-sided Polyak-Łojasiewicz (PL) inequality. A large number of practical problems, including the robust least squares estimation, are known to satisfy the two-sided PL inequality. The proposed method achieves arbitrarily fast convergence compared to any other state-of-the-art method with linear or even super-linear convergence, as also corroborated in numerical case studies.