Primal and Dual Analysis of Entropic Fictitious Play for Finite-sum Problems

• URL: http://arxiv.org/abs/2303.02957v1
• Date: Mon, 6 Mar 2023 08:05:08 GMT
• Title: Primal and Dual Analysis of Entropic Fictitious Play for Finite-sum Problems
• Authors: Atsushi Nitanda, Kazusato Oko, Denny Wu, Nobuhito Takenouchi, Taiji Suzuki
• Abstract summary: The entropic fictitious play (EFP) is a recently proposed algorithm that minimizes the sum of a convex functional and entropy in the space of measures. We provide a concise primal-dual analysis of EFP in the setting where the learning problem exhibits a finite-sum structure.
• Score: 42.375903320536715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The entropic fictitious play (EFP) is a recently proposed algorithm that minimizes the sum of a convex functional and entropy in the space of measures -- such an objective naturally arises in the optimization of a two-layer neural network in the mean-field regime. In this work, we provide a concise primal-dual analysis of EFP in the setting where the learning problem exhibits a finite-sum structure. We establish quantitative global convergence guarantees for both the continuous-time and discrete-time dynamics based on properties of a proximal Gibbs measure introduced in Nitanda et al. (2022). Furthermore, our primal-dual framework entails a memory-efficient particle-based implementation of the EFP update, and also suggests a connection to gradient boosting methods. We illustrate the efficiency of our novel implementation in experiments including neural network optimization and image synthesis.

Related papers

• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [62.51015395213579]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. The proposed algorithm employs the movements of particles to represent the updates of random strategies for the $ilon$-mixed Nash equilibrium.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Structured Optimal Variational Inference for Dynamic Latent Space Models [16.531262817315696]
  We consider a latent space model for dynamic networks, where our objective is to estimate the pairwise inner products plus the intercept of the latent positions. To balance posterior inference and computational scalability, we consider a structured mean-field variational inference framework.
  arXiv  Detail & Related papers  (2022-09-29T22:10:42Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
  We offer a theoretical characterization of off-policy evaluation (OPE) in reinforcement learning. We show that the minimax approach enables us to achieve a fast rate of convergence for weights and quality functions. We present the first finite-sample result with first-order efficiency in non-tabular environments.
  arXiv  Detail & Related papers  (2021-02-05T03:20:39Z)
• First-Order Optimization Inspired from Finite-Time Convergent Flows [26.931390502212825]
  We propose an Euler discretization for first-order finite-time flows, and provide convergence guarantees, in the deterministic and the deterministic setting. We then apply the proposed algorithms to academic examples, as well as deep neural networks training, where we empirically test their performances on the SVHN dataset. Our results show that our schemes demonstrate faster convergences against standard optimization alternatives.
  arXiv  Detail & Related papers  (2020-10-06T19:28:00Z)
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs [54.967872716145656]
  This work focuses on off-policy evaluation (OPE) with function approximation in infinite-horizon undiscounted Markov decision processes (MDPs) We provide the first finite-sample OPE error bound, extending existing results beyond the episodic and discounted cases. We show that this results in an exponential-family distribution whose sufficient statistics are the features, paralleling maximum-entropy approaches in supervised learning.
  arXiv  Detail & Related papers  (2020-06-17T18:13:37Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Consensus-Based Optimization on the Sphere: Convergence to Global Minimizers and Machine Learning [7.998311072988401]
  We investigate the implementation of a new Kuramoto-Vicsek-type model for global optimization of non functions on the sphere. We present several numerical experiments, which show that the algorithm proposed in the present paper scales well with the dimension and is extremely versatile.
  arXiv  Detail & Related papers  (2020-01-31T18:23:26Z)

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.