Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control

• URL: http://arxiv.org/abs/2105.11586v4
• Date: Tue, 4 Jan 2022 13:31:22 GMT
• Title: Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control
• Authors: Youhei Akimoto, Yoshiki Miyauchi, Atsuo Maki
• Abstract summary: We propose an approach to saddle point optimization relying only on oracles that solve minimization problems approximately. We analyze its convergence property on a strongly convex--concave problem and show its linear convergence toward the global min-max saddle point. An implementation of the developed approach using the (1+1)-CMA-ES as the minimization oracle, namely Adversarial-CMA-ES, is shown to outperform several existing approaches on test problems.
• Score: 7.347989843033034
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We propose an approach to saddle point optimization relying only on oracles that solve minimization problems approximately. We analyze its convergence property on a strongly convex--concave problem and show its linear convergence toward the global min--max saddle point. Based on the convergence analysis, we develop a heuristic approach to adapt the learning rate. An implementation of the developed approach using the (1+1)-CMA-ES as the minimization oracle, namely Adversarial-CMA-ES, is shown to outperform several existing approaches on test problems. Numerical evaluation confirms the tightness of the theoretical convergence rate bound as well as the efficiency of the learning rate adaptation mechanism. As an example of real-world problems, the suggested optimization method is applied to automatic berthing control problems under model uncertainties, showing its usefulness in obtaining solutions robust to uncertainty.

Related papers

• Multiple Greedy Quasi-Newton Methods for Saddle Point Problems [0.0]
  We introduce the Multiple Greedysi-SP (MGSR1-SP) method to solve Hessian point problems. We show that our method significantly improves both stability and efficiency. Results affirm MGSR1-SP performance across a broad spectrum of machine learning applications.
  arXiv  Detail & Related papers  (2024-08-01T02:40:37Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
  We focus on high-dimensional and plausible settings in which the problem admits a low-rank solution. We provide several theoretical results proving that, under these circumstances, the well-known Extragradient method converges to a solution of the constrained optimization problem.
  arXiv  Detail & Related papers  (2024-02-14T10:48:00Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Covariance Matrix Adaptation Evolutionary Strategy with Worst-Case Ranking Approximation for Min--Max Optimization and its Application to Berthing Control Tasks [19.263468901608785]
  We consider a continuous min--max optimization problem $min_x in mathbbX max_y in mathbbYf(x,y)$ whose objective function is a black-box. We propose a novel approach to minimize the worst-case objective function $F(x) = max_y f(x,y)$ directly.
  arXiv  Detail & Related papers  (2023-03-28T15:50:56Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  We present a new model of a general convex or non objective machine machine objectives. We propose an algorithm that solves a constraint with gradually relaxed point levels of each subproblem. We demonstrate the effectiveness of our new numerical scale problems.
  arXiv  Detail & Related papers  (2020-10-23T05:24:05Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43: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.