Related papers: Sample Average Approximation for Black-Box VI

Sample Average Approximation for Black-Box VI

URL: http://arxiv.org/abs/2304.06803v2
Date: Wed, 17 May 2023 14:24:50 GMT
Title: Sample Average Approximation for Black-Box VI
Authors: Javier Burroni, Justin Domke, Daniel Sheldon
Abstract summary: We present a novel approach for black-box VI that bypasses the difficulties of gradient ascent. We approximate the solution of optimization problems by transforming them into deterministic ones. Our experiments show that our method simplifies the VI problem and achieves faster performance than existing methods.
Score: 31.664188645648156
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present a novel approach for black-box VI that bypasses the difficulties of stochastic gradient ascent, including the task of selecting step-sizes. Our approach involves using a sequence of sample average approximation (SAA) problems. SAA approximates the solution of stochastic optimization problems by transforming them into deterministic ones. We use quasi-Newton methods and line search to solve each deterministic optimization problem and present a heuristic policy to automate hyperparameter selection. Our experiments show that our method simplifies the VI problem and achieves faster performance than existing methods.

Related papers

Towards Convexity in Anomaly Detection: A New Formulation of SSLM with Unique Optimal Solutions [12.250410918282615]
An unsolved issue in widely used methods as Support Vector Description (SVDD) Small and Large Sphere SVM (MvMs) We introduce a novel SSLM demonstrated to be impossible with traditional non approaches.
arXiv Detail & Related papers (2024-10-31T09:42:39Z)
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z)
Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z)
Parallel Surrogate-assisted Optimization Using Mesh Adaptive Direct Search [0.0]
We present a method that employs surrogate models and concurrent computing at the search step of the mesh adaptive direct search (MADS) algorithm. We conduct numerical experiments to assess the performance of the modified MADS algorithm with respect to available CPU resources.
arXiv Detail & Related papers (2021-07-26T18:28:56Z)
Variational Nonlinear System Identification [0.8793721044482611]
This paper considers parameter estimation for nonlinear state-space models, which is an important but challenging problem. We employ a variational inference (VI) approach, which is a principled method that has deep connections to maximum likelihood estimation. This VI approach ultimately provides estimates of the model as solutions to an optimisation problem, which is deterministic, tractable and can be solved using standard optimisation tools.
arXiv Detail & Related papers (2020-12-08T05:43:50Z)
Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation [9.359939442911127]
We first present a novel operator extrapolation (OE) method for solving deterministic variational inequality (VI) problems. We then introduce the operator extrapolation (SOE) method and establish its optimal convergence behavior for solving different inequality VI problems.
arXiv Detail & Related papers (2020-11-05T17:20:19Z)
Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
We consider optimization problems, where multiple differentiable losses have to be minimized. The presented method computes descent direction in every iteration to guarantee equal relative decrease of objective functions.
arXiv Detail & Related papers (2020-07-14T09:50:33Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
arXiv Detail & Related papers (2020-07-07T21:26:35Z)
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)
GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
arXiv Detail & Related papers (2020-02-17T20:21:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.