Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems

• URL: http://arxiv.org/abs/2408.17387v2
• Date: Tue, 18 Feb 2025 12:21:12 GMT
• Title: Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems
• Authors: Jack M. Buckingham, Ivo Couckuyt, Juergen Branke,
• Abstract summary: We formulate a knowledge-gradient-based acquisition function to jointly optimize the first variables, establish a guarantee of consistency, and provide an approximation. We demonstrate comparable empirical results to an alternative we formulate with fewer focuss, which alternates between the two variable types.
• Score: 2.9016548477524156
• License:
• Abstract: Bayesian optimization is a sample-efficient method for solving expensive, black-box optimization problems. Stochastic programming concerns optimization under uncertainty where, typically, average performance is the quantity of interest. In the first stage of a two-stage problem, here-and-now decisions must be made in the face of uncertainty, while in the second stage, wait-and-see decisions are made after the uncertainty has been resolved. Many methods in stochastic programming assume that the objective is cheap to evaluate and linear or convex. We apply Bayesian optimization to solve non-convex, two-stage stochastic programs which are black-box and expensive to evaluate as, for example, is often the case with simulation objectives. We formulate a knowledge-gradient-based acquisition function to jointly optimize the first- and second-stage variables, establish a guarantee of asymptotic consistency, and provide a computationally efficient approximation. We demonstrate comparable empirical results to an alternative we formulate with fewer approximations, which alternates its focus between the two variable types, and superior empirical results over the state of the art and the standard, na\"ive, two-step benchmark.

Related papers

• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand. We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• BO4IO: A Bayesian optimization approach to inverse optimization with uncertainty quantification [5.031974232392534]
  This work addresses data-driven inverse optimization (IO) The goal is to estimate unknown parameters in an optimization model from observed decisions that can be assumed to be optimal or near-optimal.
  arXiv  Detail & Related papers  (2024-05-28T06:52:17Z)
• Bayesian Optimization with Conformal Prediction Sets [44.565812181545645]
  Conformal prediction is an uncertainty quantification method with coverage guarantees even for misspecified models. We propose conformal Bayesian optimization, which directs queries towards regions of search space where the model predictions have guaranteed validity. In many cases we find that query coverage can be significantly improved without harming sample-efficiency.
  arXiv  Detail & Related papers  (2022-10-22T17:01:05Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Accelerating Stochastic Probabilistic Inference [1.599072005190786]
  Variational Inference (SVI) has been increasingly attractive thanks to its ability to find good posterior approximations of probabilistic models. Almost all the state-of-the-art SVI algorithms are based on first-order optimization and often suffer from poor convergence rate. We bridge the gap between second-order methods and variational inference by proposing a second-order based variational inference approach.
  arXiv  Detail & Related papers  (2022-03-15T01:19:12Z)
• 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)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
  We show that common optimization methods lead to poor variational approximations if the problem is moderately large. Motivated by these findings, we develop a more robust and accurate optimization framework by viewing the underlying algorithm as producing a Markov chain.
  arXiv  Detail & Related papers  (2020-09-01T19:12:11Z)
• 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)
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems [12.010310883787911]
  We analyze a new family of adaptive subgradient methods for solving an important class of weakly convex (possibly nonsmooth) optimization problems. Experimental results indicate how the proposed algorithms empirically outperform its zerothorder gradient descent and its design variant.
  arXiv  Detail & Related papers  (2020-05-19T07:44:52Z)

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.