On the Impossibility of Global Convergence in Multi-Loss Optimization

• URL: http://arxiv.org/abs/2005.12649v3
• Date: Sun, 17 Jan 2021 09:14:59 GMT
• Title: On the Impossibility of Global Convergence in Multi-Loss Optimization
• Authors: Alistair Letcher
• Abstract summary: We prove that desirable convergence properties cannot simultaneously hold for any algorithm. Our result has more to do with the existence of games with no satisfactory outcomes, than with algorithms per se. It remains an open question whether such behavior can arise in high-dimensional games of interest to ML practitioners.
• Score: 10.081768261298098
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Under mild regularity conditions, gradient-based methods converge globally to a critical point in the single-loss setting. This is known to break down for vanilla gradient descent when moving to multi-loss optimization, but can we hope to build some algorithm with global guarantees? We negatively resolve this open problem by proving that desirable convergence properties cannot simultaneously hold for any algorithm. Our result has more to do with the existence of games with no satisfactory outcomes, than with algorithms per se. More explicitly we construct a two-player game with zero-sum interactions whose losses are both coercive and analytic, but whose only simultaneous critical point is a strict maximum. Any 'reasonable' algorithm, defined to avoid strict maxima, will therefore fail to converge. This is fundamentally different from single losses, where coercivity implies existence of a global minimum. Moreover, we prove that a wide range of existing gradient-based methods almost surely have bounded but non-convergent iterates in a constructed zero-sum game for suitably small learning rates. It nonetheless remains an open question whether such behavior can arise in high-dimensional games of interest to ML practitioners, such as GANs or multi-agent RL.

Related papers

• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  The Gradient Descent (SGD) algorithm has triggered people's interest due to its good performance in practice but lack of theoretical understanding. It still remains unclear whether the lastiterate convergence can be provably extended to wider composite optimization and non-Euclidean norms.
  arXiv  Detail & Related papers  (2023-12-13T21:41:06Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  State-of-the-art methods for solving 2-player zero-sum imperfect games rely on linear programming or dynamic regret minimization. We propose a novel family of promising approaches complementing those relying on linear programming or iterative methods.
  arXiv  Detail & Related papers  (2022-10-26T11:41:57Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02:26Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  We analyze inexact and versions of the CGALP algorithm developed in the authors' previous paper. This allows one to compute some gradients, terms, and/or linear minimization oracles in an inexact fashion. We show convergence of the Lagrangian to an optimum and feasibility of the affine constraint.
  arXiv  Detail & Related papers  (2020-05-11T14:52:16Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  We characterize the finite-time last-iterate convergence rate for joint OGD learning on $lambda$-cocoercive games. We show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as non-adaptive counterpart.
  arXiv  Detail & Related papers  (2020-02-23T01:46:34Z)
• Replica Exchange for Non-Convex Optimization [4.421561004829125]
  Gradient descent (GD) is known to converge quickly for convex objective functions, but it can be trapped at local minima. Langevin dynamics (LD) can explore the state space and find global minima, but in order to give accurate estimates, LD needs to run with a small discretization step size and verify weak force. This paper shows that these two algorithms and their non-swapping variants can collaborate" through a simple exchange mechanism.
  arXiv  Detail & Related papers  (2020-01-23T03:13:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.