# Difference between revisions of "GradientLess Descent"

From statwiki

(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

## Contents

## 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.