MinMax Methods for Optimal Transport and Beyond: Regularization, Approximation and Numerics

• URL: http://arxiv.org/abs/2010.11502v1
• Date: Thu, 22 Oct 2020 07:43:51 GMT
• Title: MinMax Methods for Optimal Transport and Beyond: Regularization, Approximation and Numerics
• Authors: Luca De Gennaro Aquino, Stephan Eckstein
• Abstract summary: Theoretically, the focus is on fitting a large class of problems into a single MinMax framework. We show that regularization techniques justify the utilization of neural networks to solve such problems.
• Score: 6.09170287691728
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study MinMax solution methods for a general class of optimization problems related to (and including) optimal transport. Theoretically, the focus is on fitting a large class of problems into a single MinMax framework and generalizing regularization techniques known from classical optimal transport. We show that regularization techniques justify the utilization of neural networks to solve such problems by proving approximation theorems and illustrating fundamental issues if no regularization is used. We further study the relation to the literature on generative adversarial nets, and analyze which algorithmic techniques used therein are particularly suitable to the class of problems studied in this paper. Several numerical experiments showcase the generality of the setting and highlight which theoretical insights are most beneficial in practice.

Related papers

• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• A Block-Coordinate Approach of Multi-level Optimization with an Application to Physics-Informed Neural Networks [0.0]
  We propose a multi-level algorithm for the solution of nonlinear optimization problems and analyze its evaluation complexity. We apply it to the solution of partial differential equations using physics-informed neural networks (PINNs) and show on a few test problems that the approach results in better solutions and significant computational savings.
  arXiv  Detail & Related papers  (2023-05-23T19:12:02Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Scalable Uni-directional Pareto Optimality for Multi-Task Learning with Constraints [4.4044968357361745]
  We propose a scalable MOO solver for Multi-Objective (MOO) problems, including support for optimization under constraints. An important application of this is to estimate high-dimensional runtime for neural classification tasks.
  arXiv  Detail & Related papers  (2021-10-28T21:35:59Z)
• On Riemannian Approach for Constrained Optimization Model in Extreme Classification Problems [2.7436792484073638]
  A constrained optimization problem is formulated as an optimization problem on matrix manifold. The proposed approach is tested on several real world large scale multi-label datasets.
  arXiv  Detail & Related papers  (2021-09-30T11:28:35Z)
• Decentralized Personalized Federated Learning for Min-Max Problems [79.61785798152529]
  This paper is the first to study PFL for saddle point problems encompassing a broader range of optimization problems. We propose new algorithms to address this problem and provide a theoretical analysis of the smooth (strongly) convex-(strongly) concave saddle point problems. Numerical experiments for bilinear problems and neural networks with adversarial noise demonstrate the effectiveness of the proposed methods.
  arXiv  Detail & Related papers  (2021-06-14T10:36:25Z)
• Certificates of quantum many-body properties assisted by machine learning [0.0]
  We propose a novel approach combining the power of relaxation techniques with deep reinforcement learning. We illustrate the viability of the method in the context of finding the ground state energy of many transfer systems. We provide tools to generalize the approach to other common applications in the field of quantum information processing.
  arXiv  Detail & Related papers  (2021-03-05T17:47:26Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances [58.54078318403909]
  The min-max problem, also known as the saddle point problem, is a class adversarial problem which is also studied in the context ofsum games.
  arXiv  Detail & Related papers  (2020-06-15T05:33:42Z)

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.