Covariance Matrix Adaptation Evolutionary Strategy with Worst-Case Ranking Approximation for Min--Max Optimization and its Application to Berthing Control Tasks

• URL: http://arxiv.org/abs/2303.16079v1
• Date: Tue, 28 Mar 2023 15:50:56 GMT
• Title: Covariance Matrix Adaptation Evolutionary Strategy with Worst-Case Ranking Approximation for Min--Max Optimization and its Application to Berthing Control Tasks
• Authors: Atsuhiro Miyagi and Yoshiki Miyauchi and Atsuo Maki and Kazuto Fukuchi and Jun Sakuma and Youhei Akimoto
• Abstract summary: 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.
• Score: 19.263468901608785
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this study, we consider a continuous min--max optimization problem $\min_{x \in \mathbb{X} \max_{y \in \mathbb{Y}}}f(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 using a covariance matrix adaptation evolution strategy (CMA-ES) in which the rankings of solution candidates are approximated by our proposed worst-case ranking approximation (WRA) mechanism. We develop two variants of WRA combined with CMA-ES and approximate gradient ascent as numerical solvers for the inner maximization problem. Numerical experiments show that our proposed approach outperforms several existing approaches when the objective function is a smooth strongly convex--concave function and the interaction between $x$ and $y$ is strong. We investigate the advantages of the proposed approach for problems where the objective function is not limited to smooth strongly convex--concave functions. The effectiveness of the proposed approach is demonstrated in the robust berthing control problem with uncertainty.ngly convex--concave functions. The effectiveness of the proposed approach is demonstrated in the robust berthing control problem with uncertainty.

Related papers

• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Smoothing Policy Iteration for Zero-sum Markov Games [9.158672246275348]
  We propose the smoothing policy robustness (SPI) algorithm to solve the zero-sum MGs approximately. Specially, the adversarial policy is served as the weight function to enable an efficient sampling over action spaces. We also propose a model-based algorithm called Smooth adversarial Actor-critic (SaAC) by extending SPI with the function approximations.
  arXiv  Detail & Related papers  (2022-12-03T14:39:06Z)
• Black-Box Min--Max Continuous Optimization Using CMA-ES with Worst-case Ranking Approximation [22.576922942465142]
  A popular approach updates $x$ and $y$ simultaneously or alternatingly. Existing approaches fail if $f$ is not Lipschitz smooth and strongly convex-concave around the optimal solution. We propose minimizing the worst-case objective function $F(x)=max_yf(x,y)$ directly using the covariance matrix adaptation evolution strategy.
  arXiv  Detail & Related papers  (2022-04-06T08:03:39Z)
• 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)
• Coordinate Descent Methods for DC Minimization [12.284934135116515]
  Difference-of-Convex (DC) refers to the problem of minimizing the difference of two convex functions. This paper proposes a non-dimensional one-dimensional subproblem globally, and it is guaranteed to converge to a coordinatewise stationary point.
  arXiv  Detail & Related papers  (2021-09-09T12:44:06Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control [7.347989843033034]
  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.
  arXiv  Detail & Related papers  (2021-05-25T00:08:47Z)
• Bayesian Optimization of Risk Measures [7.799648230758491]
  We consider Bayesian optimization of objective functions of the form $rho[ F(x, W) ]$, where $F$ is a black-box expensive-to-evaluate function. We propose a family of novel Bayesian optimization algorithms that exploit the structure of the objective function to substantially improve sampling efficiency.
  arXiv  Detail & Related papers  (2020-07-10T18:20:46Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• 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.