Gradient-Descent Optimization Algorithm: Difference between revisions

From GM-RKB
Jump to navigation Jump to search
No edit summary
m (Text replacement - ". "" to ". “")
 
(6 intermediate revisions by the same user not shown)
Line 1: Line 1:
A [[Gradient-Descent Optimization Algorithm]] is an [[first-order iterative optimization algorithm]] (that uses a [[differentiable function|differentiable]] [[gradient function]]).
A [[Gradient-Descent Optimization Algorithm]] is an [[first-order iterative optimization algorithm]] (to solve a [[gradient descent-based optimization task]]) that uses a [[differentiable function|differentiable]] [[gradient function]].
* <B>AKA:</B> [[Gradient-Descent Optimization Algorithm|Method of Steepest Descent]].
* <B>AKA:</B> [[Gradient-Descent Optimization Algorithm|Method of Steepest Descent]].
* <B>Context</U>:</B>
* <B>Context</U>:</B>
** It can range from being a [[Batch Gradient Descent Algorithm]] to being an [[Online Gradient Descent Algorithm]].
** It can range from being a [[Batch Gradient Descent Algorithm]] to being an [[Online Gradient Descent Algorithm]].
** It can range from being an [[Exact Gradient Descent Algorithm]] to being a [[Approximate Gradient Descent Algorithm]] (such as [[SGD]]).
** It can range from being an [[Exact Gradient Descent Algorithm]] to being a [[Approximate Gradient Descent Algorithm]] (such as [[SGD]]).
** It can be applied by a [[Gradient Descent-based Optimization System]] (that can solve a [[gradient descent-based optimization task]]).
** It can be implemented by a [[Gradient Descent-based Optimization System]] (that can solve a [[gradient descent-based optimization task]]).
** ...
**
* <B>Example(s):</B>
* <B>Example(s):</B>
** [[Newton's Method]];
** [[Newton's Method]];
Line 15: Line 15:
*** an [[Adaptive Learning Rate Algorithm (ADADELTA)]],
*** an [[Adaptive Learning Rate Algorithm (ADADELTA)]],
*** an [[Adaptive Moment Estimation Algorithm (Adam)]],
*** an [[Adaptive Moment Estimation Algorithm (Adam)]],
*** a [[Mini-Batch Gradient Descent Algorithm (MBGD)]]
*** a [[Mini-Batch Gradient Descent Algorithm (MBGD)]].
*** a [[Momentum Gradient Descent (MGD)]],
*** a [[Momentum Gradient Descent (MGD)]],
*** a [[Root Mean Square Propagation Algorithm (RMSprop)]];
*** a [[Root Mean Square Propagation Algorithm (RMSprop)]];
Line 36: Line 36:


== References ==
== References ==
=== 2024 ===
* GPT-4
Procedure: [[Gradient-Descent Optimization]]
Description: This algorithm finds the minimum of a [[differentiable function]] using the [[gradient descent method]], adjusting parameters iteratively to minimize the function's output.
Initialization:
- Input:
  - f: A [[differentiable function]] whose minimum is to be found.
  - grad_f: The [[gradient function]] of f.
  - x_0: Initial guess for the location of the minimum.
  - alpha: Initial learning rate.
  - tolerance: The tolerance level for stopping criteria.
  - max_iterations: Maximum number of iterations allowed.
- Output:
  - x_min: The estimated location of the minimum.
  - f_min: The value of f at x_min.
Algorithm Steps:
- Initialize:
  - x := x_0
  - iteration := 0
- Repeat until convergence or maximum iterations reached:
  - if |grad_f(x)| < tolerance or iteration >= max_iterations:
    - break
  - Update x:
    - x := x - alpha * grad_f(x)
  - Update iteration count:
    - iteration := iteration + 1
- Finalize:
  - x_min := x
  - f_min := f(x_min)
Output Results:
- Return: (x_min, f_min)


=== 2019 ===
=== 2019 ===
* (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Gradient_descent Retrieved:2019-9-20.
* (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Gradient_descent Retrieved:2019-9-20.
** '''Gradient descent''' is a [[first-order]] [[Iterative algorithm|iterative]] [[Mathematical optimization|optimization]] [[algorithm]] for finding the minimum of a function. To find a [[local minimum]] of a function using gradient descent, one takes steps proportional to the ''negative'' of the [[gradient]] (or approximate gradient) of the function at the current point. If, instead, one takes steps proportional to the ''positive'' of the gradient, one approaches a [[local maximum]] of that function; the procedure is then known as '''gradient ascent'''. Gradient descent was originally proposed by [[Augustin-Louis_Cauchy|Cauchy]] in 1847. <ref> Dimitri P. Bertsekas, ''Nonlinear Programming'', Athena Scientific 1999, 2nd edition, pp. 187. </ref> <ref> Cauchy, Augustin. "Méthode générale pour la résolution des systemes d’équations simultanées." Comp. Rend. Sci. Paris 25.1847 (1847): 536-538. </ref>        <P>        Gradient descent is also known as '''steepest descent'''. However, gradient descent should not be confused with the [[method of steepest descent]] for approximating integrals.
** '''Gradient descent''' is a [[first-order]] [[Iterative algorithm|iterative]] [[Mathematical optimization|optimization]] [[algorithm]] for finding the minimum of a function. To find a [[local minimum]] of a function using gradient descent, one takes steps proportional to the ''negative'' of the [[gradient]] (or approximate gradient) of the function at the current point. If, instead, one takes steps proportional to the ''positive'' of the gradient, one approaches a [[local maximum]] of that function; the procedure is then known as '''gradient ascent'''. Gradient descent was originally proposed by [[Augustin-Louis_Cauchy|Cauchy]] in 1847. <ref> Dimitri P. Bertsekas, ''Nonlinear Programming'', Athena Scientific 1999, 2nd edition, pp. 187. </ref> <ref> Cauchy, Augustin. “Méthode générale pour la résolution des systemes d’équations simultanées." Comp. Rend. Sci. Paris 25.1847 (1847): 536-538. </ref>        <P>        Gradient descent is also known as '''steepest descent'''. However, gradient descent should not be confused with the [[method of steepest descent]] for approximating integrals.


=== 2018b ===
=== 2018b ===

Latest revision as of 04:34, 8 May 2024

A Gradient-Descent Optimization Algorithm is an first-order iterative optimization algorithm (to solve a gradient descent-based optimization task) that uses a differentiable gradient function.



References

2024

  • GPT-4
Procedure: Gradient-Descent Optimization
Description: This algorithm finds the minimum of a differentiable function using the gradient descent method, adjusting parameters iteratively to minimize the function's output.
Initialization:
- Input:
 - f: A differentiable function whose minimum is to be found.
 - grad_f: The gradient function of f.
 - x_0: Initial guess for the location of the minimum.
 - alpha: Initial learning rate.
 - tolerance: The tolerance level for stopping criteria.
 - max_iterations: Maximum number of iterations allowed.
- Output:
 - x_min: The estimated location of the minimum.
 - f_min: The value of f at x_min.
Algorithm Steps:
- Initialize:
 - x := x_0
 - iteration := 0
- Repeat until convergence or maximum iterations reached:
 - if |grad_f(x)| < tolerance or iteration >= max_iterations:
   - break
 - Update x:
   - x := x - alpha * grad_f(x)
 - Update iteration count:
   - iteration := iteration + 1
- Finalize:
 - x_min := x
 - f_min := f(x_min)
Output Results:
- Return: (x_min, f_min)

2019

2018b

  • (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm#Related_algorithms Retrieved:2018-8-19.
    • In a quasi-Newton method, such as that due to Davidon, Fletcher and Powell or Broyden–Fletcher–Goldfarb–Shanno (BFGS method) an estimate of the full Hessian [math]\displaystyle{ \frac{\partial^2 S}{\partial \beta_j \partial\beta_k} }[/math] is built up numerically using first derivatives [math]\displaystyle{ \frac{\partial r_i}{\partial\beta_j} }[/math] only so that after n refinement cycles the method closely approximates to Newton's method in performance. Note that quasi-Newton methods can minimize general real-valued functions, whereas Gauss–Newton, Levenberg–Marquardt, etc. fits only to nonlinear least-squares problems.

      Another method for solving minimization problems using only first derivatives is gradient descent. However, this method does not take into account the second derivatives even approximately. Consequently, it is highly inefficient for many functions, especially if the parameters have strong interactions.

2018a

2018b

2012

  • http://en.wikipedia.org/wiki/Gradient_descent#Description
    • QUOTE: Gradient descent is based on the observation that if the multivariable function [math]\displaystyle{ F(\mathbf{x}) }[/math] is defined and differentiable in a neighborhood of a point [math]\displaystyle{ \mathbf{a} }[/math], then [math]\displaystyle{ F(\mathbf{x}) }[/math] decreases fastest if one goes from [math]\displaystyle{ \mathbf{a} }[/math] in the direction of the negative gradient of [math]\displaystyle{ F }[/math] at [math]\displaystyle{ \mathbf{a} }[/math], [math]\displaystyle{ -\nabla F(\mathbf{a}) }[/math]. It follows that, if :[math]\displaystyle{ \mathbf{b} = \mathbf{a}-\gamma\nabla F(\mathbf{a}) }[/math] for [math]\displaystyle{ \gamma \to 0 }[/math] a small enough number, then [math]\displaystyle{ F(\mathbf{a})\geq F(\mathbf{b}) }[/math]. With this observation in mind, one starts with a guess [math]\displaystyle{ \mathbf{x}_0 }[/math] for a local minimum of [math]\displaystyle{ F }[/math], and considers the sequence [math]\displaystyle{ \mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots }[/math] such that :[math]\displaystyle{ \mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0. }[/math] We have :[math]\displaystyle{ F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots, }[/math] so hopefully the sequence [math]\displaystyle{ (\mathbf{x}_n) }[/math] converges to the desired local minimum. Note that the value of the step size [math]\displaystyle{ \gamma }[/math] is allowed to change at every iteration. With certain assumptions on the function [math]\displaystyle{ F }[/math] (for example, [math]\displaystyle{ F }[/math] convex and [math]\displaystyle{ \nabla F }[/math] Lipschitz) and particular choices of [math]\displaystyle{ \gamma }[/math] (e.g., chosen via a line search that satisfies the Wolfe conditions), convergence to a local minimum can be guaranteed. When the function [math]\displaystyle{ F }[/math] is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

      This process is illustrated in the picture to the right. Here [math]\displaystyle{ F }[/math] is assumed to be defined on the plane, and that its graph has a bowl shape. The blue curves are the contour lines, that is, the regions on which the value of [math]\displaystyle{ F }[/math] is constant. A red arrow originating at a point shows the direction of the negative gradient at that point. Note that the (negative) gradient at a point is orthogonal to the contour line going through that point. We see that gradient descent leads us to the bottom of the bowl, that is, to the point where the value of the function [math]\displaystyle{ F }[/math] is minimal.

1999

  • (Orr, 1999a) ⇒ Genevieve Orr. (1999). “Linear Neural Networks.” In: "CS-449: Neural Networks." Fall 99
    • To find the gradient G for the entire data set, we sum at each weight the contribution given by equation 6 over all the data points. We can then subtract a small proportion µ (called the learning rate) of G from the weights to perform gradient descent.
    • 1. Initialize all weights to small random values.
    • 2. REPEAT until done
      • 1. For each weight wij set
      • 2. For each data point (x, t)p
        • 1. set input units to x
        • 2. compute value of output units
        • 3. For each weight wij set
    • 3. For each weight wij set
    • An alternative approach is online learning, where the weights are updated immediately after seeing each data point. Since the gradient for a single data point can be considered a noisy approximation to the overall gradient G (Fig. 5), this is also called stochastic (noisy) gradient descent.

  1. Dimitri P. Bertsekas, Nonlinear Programming, Athena Scientific 1999, 2nd edition, pp. 187.
  2. Cauchy, Augustin. “Méthode générale pour la résolution des systemes d’équations simultanées." Comp. Rend. Sci. Paris 25.1847 (1847): 536-538.