Cross-Entropy Method Variants for Optimization

• URL: http://arxiv.org/abs/2009.09043v1
• Date: Fri, 18 Sep 2020 19:51:30 GMT
• Title: Cross-Entropy Method Variants for Optimization
• Authors: Robert J. Moss
• Abstract summary: Cross-entropy (CE) method is a popular method for optimization due to its simplicity and effectiveness. Certain objective functions may be computationally expensive to evaluate, and the CE-method could potentially get stuck in local minima. We introduce novel variants of the CE-method to address these concerns.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The cross-entropy (CE) method is a popular stochastic method for optimization due to its simplicity and effectiveness. Designed for rare-event simulations where the probability of a target event occurring is relatively small, the CE-method relies on enough objective function calls to accurately estimate the optimal parameters of the underlying distribution. Certain objective functions may be computationally expensive to evaluate, and the CE-method could potentially get stuck in local minima. This is compounded with the need to have an initial covariance wide enough to cover the design space of interest. We introduce novel variants of the CE-method to address these concerns. To mitigate expensive function calls, during optimization we use every sample to build a surrogate model to approximate the objective function. The surrogate model augments the belief of the objective function with less expensive evaluations. We use a Gaussian process for our surrogate model to incorporate uncertainty in the predictions which is especially helpful when dealing with sparse data. To address local minima convergence, we use Gaussian mixture models to encourage exploration of the design space. We experiment with evaluation scheduling techniques to reallocate true objective function calls earlier in the optimization when the covariance is the largest. To test our approach, we created a parameterized test objective function with many local minima and a single global minimum. Our test function can be adjusted to control the spread and distinction of the minima. Experiments were run to stress the cross-entropy method variants and results indicate that the surrogate model-based approach reduces local minima convergence using the same number of function evaluations.

Related papers

• Self-Supervised Dataset Distillation for Transfer Learning [77.4714995131992]
  We propose a novel problem of distilling an unlabeled dataset into a set of small synthetic samples for efficient self-supervised learning (SSL) We first prove that a gradient of synthetic samples with respect to a SSL objective in naive bilevel optimization is textitbiased due to randomness originating from data augmentations or masking. We empirically validate the effectiveness of our method on various applications involving transfer learning.
  arXiv  Detail & Related papers  (2023-10-10T10:48:52Z)
• DF2: Distribution-Free Decision-Focused Learning [53.2476224456902]
  Decision-focused learning (DFL) has recently emerged as a powerful approach for predictthen-optimize problems. Existing end-to-end DFL methods are hindered by three significant bottlenecks: model error, sample average approximation error, and distribution-based parameterization of the expected objective. We present DF2 -- the first textit-free decision-focused learning method explicitly designed to address these three bottlenecks.
  arXiv  Detail & Related papers  (2023-08-11T00:44:46Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Efficient Approximation of Expected Hypervolume Improvement using Gauss-Hermite Quadrature [0.0]
  Gauss-Hermite quadrature is an accurate alternative to Monte Carlo for both independent and correlated predictive densities. We show it can be an accurate alternative to Monte Carlo for both independent and correlated predictive densities.
  arXiv  Detail & Related papers  (2022-06-15T22:09:48Z)
• R-MBO: A Multi-surrogate Approach for Preference Incorporation in Multi-objective Bayesian Optimisation [0.0]
  We present an a-priori multi-surrogate approach to incorporate the desirable objective function values as the preferences of a decision-maker in multi-objective BO. The results and comparison with the existing mono-surrogate approach on benchmark and real-world optimisation problems show the potential of the proposed approach.
  arXiv  Detail & Related papers  (2022-04-27T19:58:26Z)
• Approximate Bayesian Optimisation for Neural Networks [6.921210544516486]
  A body of work has been done to automate machine learning algorithm to highlight the importance of model choice. The necessity to solve the analytical tractability and the computational feasibility in a idealistic fashion enables to ensure the efficiency and the applicability.
  arXiv  Detail & Related papers  (2021-08-27T19:03:32Z)
• KL Guided Domain Adaptation [88.19298405363452]
  Domain adaptation is an important problem and often needed for real-world applications. A common approach in the domain adaptation literature is to learn a representation of the input that has the same distributions over the source and the target domain. We show that with a probabilistic representation network, the KL term can be estimated efficiently via minibatch samples.
  arXiv  Detail & Related papers  (2021-06-14T22:24:23Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Finding Optimal Points for Expensive Functions Using Adaptive RBF-Based Surrogate Model Via Uncertainty Quantification [11.486221800371919]
  We propose a novel global optimization framework using adaptive Radial Basis Functions (RBF) based surrogate model via uncertainty quantification. It first employs an RBF-based Bayesian surrogate model to approximate the true function, where the parameters of the RBFs can be adaptively estimated and updated each time a new point is explored. It then utilizes a model-guided selection criterion to identify a new point from a candidate set for function evaluation.
  arXiv  Detail & Related papers  (2020-01-19T16:15:55Z)
• Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic [5.395127324484869]
  SplitSGD is a new dynamic learning schedule for optimization. The method decreases the learning rate for better adaptation to the local geometry of the objective function. It essentially does not incur additional computational cost than standard SGD.
  arXiv  Detail & Related papers  (2019-10-18T19:38:53Z)

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.