Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization

• URL: http://arxiv.org/abs/2006.04655v2
• Date: Tue, 9 Jun 2020 18:29:23 GMT
• Title: Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization
• Authors: Daniel Golovin, Qiuyi Zhang
• Abstract summary: In this paper, we consider multi-objective optimization, where $f(x)$ outputs a vector of possibly competing objectives. We show that any provably convergent single-objective optimization process can be effortlessly converted to a multi-objective optimization process with provable convergence guarantees.
• Score: 8.90548944387431
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Single-objective black box optimization (also known as zeroth-order optimization) is the process of minimizing a scalar objective $f(x)$, given evaluations at adaptively chosen inputs $x$. In this paper, we consider multi-objective optimization, where $f(x)$ outputs a vector of possibly competing objectives and the goal is to converge to the Pareto frontier. Quantitatively, we wish to maximize the standard hypervolume indicator metric, which measures the dominated hypervolume of the entire set of chosen inputs. In this paper, we introduce a novel scalarization function, which we term the hypervolume scalarization, and show that drawing random scalarizations from an appropriately chosen distribution can be used to efficiently approximate the hypervolume indicator metric. We utilize this connection to show that Bayesian optimization with our scalarization via common acquisition functions, such as Thompson Sampling or Upper Confidence Bound, provably converges to the whole Pareto frontier by deriving tight hypervolume regret bounds on the order of $\widetilde{O}(\sqrt{T})$. Furthermore, we highlight the general utility of our scalarization framework by showing that any provably convergent single-objective optimization process can be effortlessly converted to a multi-objective optimization process with provable convergence guarantees.

Related papers

• Online Mirror Descent for Tchebycheff Scalarization in Multi-Objective Optimization [14.970965673760427]
  We propose an online mirror descent algorithm for Tcheche scalarization, which we call OMD-TCH. We show the effectiveness of OMD-TCH on both synthetic problems and federated learning tasks under fairness constraints.
  arXiv  Detail & Related papers  (2024-10-29T05:58:33Z)
• ProGO: Probabilistic Global Optimizer [9.772380490791635]
  In this paper we develop an algorithm that converges to the global optima under some mild conditions. We show that the proposed algorithm outperforms, by order of magnitude, many existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-10-04T22:23:40Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Optimal Scalarizations for Sublinear Hypervolume Regret [2.703970154550017]
  We show that hypervolume scalarizations with uniformly random weights achieve an optimal subvolume hypervolume regret bound of $O(T-1/k)$. For the setting of multiobjective linear bandits, we derive a novel non-Euclidean analysis to get regret bounds of $tildeO( d T-1/2 + T-1/k)$, removing unnecessary $textpoly(k)$ dependencies.
  arXiv  Detail & Related papers  (2023-07-06T20:49:42Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Multi-objective optimization via equivariant deep hypervolume approximation [3.069335774032178]
  We show how to approximate the hypervolume function with a deep neural network. We evaluate our method against exact, and approximate hypervolume methods in terms of accuracy, computation time, and generalization.
  arXiv  Detail & Related papers  (2022-10-05T12:07:13Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling. We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods [12.93796690939018]
  We prove that the adaptive Polyak's Heavy-ball (HB) method attains an optimal individual convergence rate of $O(frac1sqrtt)$. Our new analysis shows how the HB momentum and its time-varying weight help us to achieve the acceleration in convex optimization.
  arXiv  Detail & Related papers  (2021-02-15T02:57:14Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• 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.