Random gradient-free minimization of convex functions
From MaRDI portal
Let \(E\) be an \(n\)-dimensional space. The Gaussian approximation of \(f:E\rightarrow \mathbb{R}\) is defined as \(f_{\mu }(x)=\frac{1}{\kappa } \int\limits_{E}f(x+\mu u)e^{-\frac{1}{2}\left\| x\right\| ^{2}}du\), with \(\kappa =\int\limits_{E}e^{-\frac{1}{2}\left\| x\right\| ^{2}}du\). Among other properties of this approximation, the authors prove that, if \(f\) is convex and \(L_{0}(f)\) Lipschitz continuous for any \(x\in E\) and \(\mu \geq 0\) one has \(\nabla f_{\mu }(x)\in \partial _{\epsilon }f(x)\), with \(\epsilon =\mu L_{0}(f)n^{\frac{1}{2}}\). Three random gradient-free oracles, \(g_{\mu }\), \(\widehat{g}_{\mu }\) and \(g_{0}\), are introduced;\ for a random vector \(u\in E\) having Gaussian distribution with correlation operator \(B^{-1}\), they return \(g_{\mu}(x)=\frac{f(x+\mu u)-f(x)}{\mu }Bu\), \(\widehat{g}_{\mu}(x)=\frac{f(x+\mu u)-f(x-\mu u)}{2\mu}Bu\) and \(g_{0}(x)=f^{\prime}(x,u)Bu\), respectively. For the expected values of the squared norms of these oracles upper bounds are provided. The use of the oracles for minimizing convex functions on closed convex sets, both in the nonsmooth and the smooth cases, is shown, and their speeds of convergence are compared with that of the subgradient method. An accelerated version of one of the methods is presented for the case when the objective function is strongly convex and \(C^{1,1}\). The application of the methods to the unconstrained minimization of nonconvex functions is briefly studied, and its rate of convergence to a stationary point is estimated. Computational experiments comparing the performance of the proposed methods with standard gradient methods are presented.
Recommendations
- Random algorithms for convex minimization problems
- Random minibatch subgradient algorithms for convex problems with functional constraints
- Random convex programs
- Optimization of convex functions with random pursuit
- Random Coordinate Descent Methods for <inline-formula> <tex-math notation="TeX">$\ell_{0}$</tex-math></inline-formula> Regularized Convex Optimization
- An optimal randomized incremental gradient method
- A simple randomised algorithm for convex optimisation
- Convergence of a random algorithm for function optimization
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- A variational approach to stochastic minimization of convex functionals
Cites work
- A Simplex Method for Function Minimization
- Algorithms for approximate calculation of the minimum of a convex function from its values
- Convergence of the restricted Nelder-Mead algorithm in two dimensions
- Convergence Properties of the Nelder--Mead Simplex Method in Low Dimensions
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Expected number of steps of a random optimization method
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 5485582 (Why is no real title available?)
- Introduction to Derivative-Free Optimization
- Introductory lectures on convex optimization. A basic course.
- Lexicographic differentiation of nonsmooth functions
- On the convergence of the Baba and Dorea random optimization methods
- Online convex optimization in the bandit setting: gradient descent without a gradient
- Optimization and nonsmooth analysis
- Random optimization
- Robust Stochastic Approximation Approach to Stochastic Programming
- Solving convex programs by random walks
- Stochastic convex optimization with bandit feedback
Cited in
(only showing first 100 items - show all)- Gradient-free two-point methods for solving stochastic nonsmooth convex optimization problems with small non-random noises
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- On the information-adaptive variants of the ADMM: an iteration complexity perspective
- Asynchronous gossip-based gradient-free method for multiagent optimization
- Approximating convex functions via non-convex oracles under the relative noise model
- A derivative-free trust-region algorithm for composite nonsmooth optimization
- Gradient-free method for nonsmooth distributed optimization
- An accelerated directional derivative method for smooth stochastic convex optimization
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives
- Accelerating reinforcement learning with a directional-Gaussian-smoothing evolution strategy
- A zeroth order method for stochastic weakly convex optimization
- A new one-point residual-feedback oracle for black-box learning and control
- Nash equilibrium seeking in N-coalition games via a gradient-free method
- Robustness and averaging properties of a large-amplitude, high-frequency extremum seeking control scheme
- Riemannian barycentres of Gibbs distributions: new results on concentration and convexity in compact symmetric spaces
- The recursive variational Gaussian approximation (R-VGA)
- Revisiting the ODE method for recursive algorithms: fast convergence using quasi stochastic approximation
- Superquantiles at work: machine learning applications and efficient subgradient computation
- Inverse reinforcement learning in contextual MDPs
- Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials
- Linesearch Newton-CG methods for convex optimization with noise
- A geometric integration approach to nonsmooth, nonconvex optimisation
- Perturbed iterate SGD for Lipschitz continuous loss functions
- Distributed online bandit optimization under random quantization
- Noisy zeroth-order optimization for non-smooth saddle point problems
- One-point gradient-free methods for smooth and non-smooth saddle-point problems
- Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference
- Oracle complexity separation in convex optimization
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- Efficient unconstrained black box optimization
- Zeroth-order algorithms for stochastic distributed nonconvex optimization
- Improved exploitation of higher order smoothness in derivative-free optimization
- Zeroth-order methods for noisy Hölder-gradient functions
- Gradient-free distributed optimization with exact convergence
- Parallel sequential Monte Carlo for stochastic gradient-free nonconvex optimization
- Spanning attack: reinforce black-box attacks with unlabeled data
- Smoothed functional-based gradient algorithms for off-policy reinforcement learning: a non-asymptotic viewpoint
- Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
- Accelerated directional search with non-Euclidean prox-structure
- Incremental gradient-free method for nonsmooth distributed optimization
- Variable metric random pursuit
- Minimax efficient finite-difference stochastic gradient estimators using black-box function evaluations
- Improved complexities for stochastic conditional gradient methods under interpolation-like conditions
- A mixed finite differences scheme for gradient approximation
- Zeroth-order feedback optimization for cooperative multi-agent systems
- Bound-constrained global optimization of functions with low effective dimensionality using multiple random embeddings
- Complexity guarantees for an implicit smoothing-enabled method for stochastic MPECs
- On the computation of equilibria in monotone and potential stochastic hierarchical games
- Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
- Trust-region methods without using derivatives: worst case complexity and the nonsmooth case
- Optimization of convex functions with random pursuit
- scientific article; zbMATH DE number 5883928 (Why is no real title available?)
- A smoothing direct search method for Monte Carlo-based bound constrained composite nonsmooth optimization
- Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains
- Efficient convex optimization with oracles
- Minimization Algorithms for Functions with Random Noise
- Randomized iterative methods for linear systems
- Stochastic model-based minimization of weakly convex functions
- Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
- A simple randomised algorithm for convex optimisation
- Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
- Stochastic three points method for unconstrained smooth minimization
- Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise
- Bandit convex optimization in non-stationary environments
- A Supervised Learning Approach Involving Active Subspaces for an Efficient Genetic Algorithm in High-Dimensional Optimization Problems
- A noise-tolerant quasi-Newton algorithm for unconstrained optimization
- New first-order algorithms for stochastic variational inequalities
- scientific article; zbMATH DE number 7625189 (Why is no real title available?)
- Finite Difference Gradient Approximation: To Randomize or Not?
- Adaptive Tikhonov strategies for stochastic ensemble Kalman inversion
- Asymptotically Exact Data Augmentation: Models, Properties, and Algorithms
- Zeroth-order stochastic compositional algorithms for risk-aware learning
- Tracking and Regret Bounds for Online Zeroth-Order Euclidean and Riemannian Optimization
- Zeroth-order regularized optimization (ZORO): approximately sparse gradients and adaptive sampling
- An accelerated method for derivative-free smooth stochastic convex optimization
- A New Likelihood Ratio Method for Training Artificial Neural Networks
- Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
- Pathological subgradient dynamics
- Black-box reductions for zeroth-order gradient algorithms to achieve lower query complexity
- Tuning of multivariable model predictive controllers through expert bandit feedback
- Derivative-free optimization methods
- Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
- Direct search based on probabilistic descent
- On the numerical performance of finite-difference-based methods for derivative-free optimization
- Full-low evaluation methods for derivative-free optimization
- Block coordinate type methods for optimization and learning
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- Worst case complexity of direct search under convexity
- Scalable subspace methods for derivative-free nonlinear least-squares optimization
- Zeroth-order optimization with orthogonal random directions
- A trust region method for noisy unconstrained optimization
- Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- Dimension Free Nonasymptotic Bounds on the Accuracy of High-Dimensional Laplace Approximation
- Zeroth-order algorithms for nonconvex-strongly-concave minimax problems with improved complexities
- A Zeroth-Order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimization
- A gradient‐free distributed optimization method for convex sum of nonconvex cost functions
- Robust design optimization for enhancing delamination resistance of composites
- Direct Search Based on Probabilistic Descent in Reduced Spaces
This page was built for publication: Random gradient-free minimization of convex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397749)
