Difference between revisions of "GradientLess Descent"

From statwiki
Jump to: navigation, search
(Created page with "==Introduction== ==Motivation and Set-up== ==Zeroth-Order Optimisation== ==GradientLess Descent Algorithm== ==Proof of correctness==")
 
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]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]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