GradientLess Descent: Difference between revisions

From statwiki
Jump to navigation Jump to search
(Created page with "==Introduction== ==Motivation and Set-up== ==Zeroth-Order Optimisation== ==GradientLess Descent Algorithm== ==Proof of correctness==")
 
No edit summary
Line 1: Line 1:
==Introduction==
==Introduction==


==Motivation and Set-up==
===Motivation and Set-up===


==Zeroth-Order Optimisation==
A general optimisation question can be formulated by asking to minimise an objective function  <math display="inline">f : \mathbb{R}^n \to \mathbb{R}</math>, which means finding:
\begin{align*}
x^* = \mathrm{argmin}_{x \in \mathbb{R}^n} f(x)
\end{align*}
 
Depending on the nature of <math display="inline">f</math>, different settings may be considered:
 
* Convex vs non-convex objective functions;
* Differentiable vs non-differentiable objective functions;
* Allowed function or gradient computations;
* Noisy/Stochastic oracle access.
 
For the purpose of this paper, we consider convex smooth objective noiseless functions, where we have access to function computations but not gradient computations.
 
===Zeroth-Order Optimisation===


==GradientLess Descent Algorithm==
==GradientLess Descent Algorithm==


==Proof of correctness==
==Proof of correctness==

Revision as of 17:23, 31 October 2020

Introduction

Motivation and Set-up

A general optimisation question can be formulated by asking to minimise an objective function [math]\displaystyle{ f : \mathbb{R}^n \to \mathbb{R} }[/math], which means finding: \begin{align*} x^* = \mathrm{argmin}_{x \in \mathbb{R}^n} f(x) \end{align*}

Depending on the nature of [math]\displaystyle{ f }[/math], different settings may be considered:

  • Convex vs non-convex objective functions;
  • Differentiable vs non-differentiable objective functions;
  • Allowed function or gradient computations;
  • Noisy/Stochastic oracle access.

For the purpose of this paper, we consider convex smooth objective noiseless functions, where we have access to function computations but not gradient computations.

Zeroth-Order Optimisation

GradientLess Descent Algorithm

Proof of correctness