Investigating Solution Existence, Equilibrium Properties, and Algorithm Convergence without Strong Assumptions in Optimization
Keywords:
Concavity, Convexity, Equilibrium, Minimax theorem, OptimizationAbstract
In the past several years, several optimization problems have arisen in machine learning, game theory, control, and adversarial settings that have withstood classical theoretical foundations due to the lack of convexity, concavity, or smoothness. These problems are frequently cast as non-convex, non-concave min-max, or saddle-point problems, where the standard assumptions for solution existence, equilibrium characterization, as well as algorithmic convergence do not hold. This paper explores the basic questions of the existence of solutions, what kind of equilibria arises, and whether iterative algorithms converge under these minimal assumptions.
We review the breakdown of classical results such as Sion's minimax theorem and examine other topological, fixed-point-based, or vibrational conditions that guarantee the existence of solutions. We also examine equilibria properties where Nash or saddle points fail to exist, pointing out concepts such as local minimax points and approximated equilibria. On the algorithmic front, we cover gradient and its variants' behavior in unstable and non-monotone dynamics, highlighting emerging techniques such as optimistic and extra gradient methods. This effort tries to connect the math behind real-world non-convex optimization problems with the most current theoretical developments and problems that haven't been addressed yet. It also provides as a starting point for more research into generalized solution concepts and algorithm construction in situations that are not well-structured or that are hostile.
References
J.P. Aubin and H. Frankowska, Set-Valued Analysis. Boston: Birkhäuser Boston, 2009. doi: https://doi.org/10.1007/978-0-8176-4848-0.
D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel, “The Mechanics of n-Player Differentiable Games,” Arxiv.Org, 2018. https://arxiv.org/abs/1802.0.
C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng, “Training GANs with Optimism,” Arxiv.Org, Feb. 13, 2018. https://arxiv.org/abs/1711.00141.
F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems. New York, NY: Springer New York, 2004. doi: https://doi.org/10.1007/b97543.
A. Sultana and S. Valecha, “Variational Reformulation of Generalized Nash Equilibrium Problems with Non-ordered Preferences,” Arxiv (Cornell University), Jan. 2023, doi: https://doi.org/10.48550/arxiv.2302.08702.
K. Fan, “Minimax Theorems,” Proceedings of the National Academy of Sciences, vol. 39, no. 1, pp. 42–47, Jan. 1953, doi: https://doi.org/10.1073/pnas.39.1.42.
C. Jin, P. Netrapalli, and M. I. Jordan, “What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?” Arxiv.Org, 2019. https://arxiv.org/abs/1902.00618.
P. Mertikopoulos, C. Papadimitriou, and G. Piliouras, “Cycles in adversarial regularized learning,” Arxiv.Org, 2017. https://arxiv.org/abs/1709.02738.
R. T. Rockafellar, Convex analysis. Princeton, N.J.: Princeton University Press, 1970.
S. Boyd and L. Vandenberghe, “Convex Optimization,” 2014. Available: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
