"随机梯度技术与优化学习理论"

机器学习

需积分: 10 88 浏览量更新于2024-01-04 收藏 25.71MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"Stochastic Gradient Techniques for Optimization and Learning"是Bernd Heidergott 和Felisa J. Vazquez-Abad撰写的关于随机梯度技术在优化与学习中的理论和应用的重要文献。本文深入探讨了随机优化与学习理论和梯度估计技术，涵盖了多个方面，包括确定性优化、随机优化、学习理论以及实际应用等。其中，讨论了无约束优化、约束优化和实际考虑因素等内容。在确定性优化方面，本文首先介绍了无约束优化的基本理论和方法。作者介绍了各种经典的优化算法，并探讨了它们的实际应用。通过对不同算法的比较和分析，读者能够更好地理解和选择合适的优化方法。同时，本文还详细讨论了约束优化问题，包括约束条件下的最优化理论和算法。不仅如此，作者还探讨了在实际问题中的应用考虑因素，如参数选择、收敛性分析、稳健性等。这些内容对于读者理解和应用优化算法都具有重要意义。另一方面，本文还介绍了随机优化与学习理论。作者首先介绍了随机优化的基本概念和原理，然后详细讨论了随机梯度下降等经典算法。通过对随机梯度下降算法的分析，读者能够了解其在优化和学习中的特点和优势。此外，本文还介绍了学习理论的基本原理和方法，包括监督学习、无监督学习和强化学习等内容。通过对这些内容的学习，读者能够更深入地理解机器学习和深度学习等领域的相关知识。此外，本文还介绍了梯度估计技术在优化和学习中的重要性。作者首先介绍了梯度下降算法的基本原理和应用，然后详细讨论了随机梯度下降等算法。通过对这些内容的学习，读者能够更深入地理解和掌握梯度估计技术在优化和学习中的应用。本文还探讨了梯度估计技术在实际问题中的具体应用，包括优化算法的改进、深度学习模型的训练等方面。这些内容对于读者进一步研究和开发新的优化和学习算法都具有重要意义。综上所述，"Stochastic Gradient Techniques for Optimization and Learning"是一部涵盖了随机优化与学习理论和梯度估计技术的重要文献。通过对本文的学习，读者能够更加深入地理解和应用优化与学习中的随机梯度技术，为相关领域的研究和发展提供重要参考。同时，本文的内容丰富，论述清晰，是一部值得一读的学术著作。

资源详情

资源推荐

CHAPTER 1. DETERMINISTIC OPTIMIZATION

unnecessary additional travel time compared to crossing at (0, d), therefore there must be a minimum

point between these two points. That the travel times are continuously differentiable follows from

the linear relationships between distance and time.

At speed v, the distance traveled in time t is vt, so the total travel time can be expressed as:

J(θ) =

cos(α

(θ))

cos(α

(θ))

sec(α

(θ)) +

sec(α

(θ)),

where the angles α

(θ) are as labeled in the diagram of Figure 1.4. Figure 1.5 shows the plot of the

time as a function of the crossing point θ.

Out[12]=

JHΘL

Figure 1.5: Plot of the function J(θ).

According to Theorem 1.1 we now ﬁnd the stationary points of J(θ). We use the following iden-

tities:

tan α

(θ) =

, (1.6a)

tan α

(θ) =

d − θ

, (1.6b)

dα

tan(α) = sec

(α) = cos

−2

(α), (1.6c)

dα

sec(α) = sec(α) tan(α). (1.6d)

To obtain the ﬁrst order optimality condition, differentiate J(θ) and set it equal to zero:

(θ) =

sec(α

(θ)) tan(α

(θ))

dα

(θ)

dθ

sec(α

(θ)) tan(α

(θ))

dα

(θ)

dθ

= 0.

By identity (1.6) it holds tan(α

(θ))/θ = a = constant. Differentiating both sides of this equation with

respect to θ yields

sec

(α

(θ))



dα

(θ)

dθ



−

tan α

(θ)

= 0 ⇒

dα

(θ)

dθ

sin(α

(θ)) cos(α

(θ)).

Similarly,

dα

(θ)

dθ

= −

d − θ

sin(α

(θ)) cos(α

(θ)).

16 June 30, 2019

1.1. UNCONSTRAINED OPTIMIZATION

Replacing these values in J

(θ) and using again the identities in (1.6), one reaches the conclusion that

(θ

∗

) = 0 is achieved at the unique point that satisﬁes:

sin(α

(θ

∗

))

sin(α

(θ

∗

))

, (1.7)

known as Snell’s Law of refraction. Going back to the person at the beach, knowing Snell’s Law is

not very useful because he or she still has to determine the optimal crossing point (0, θ

∗

), however

(1.7) gives it as an implicit solution.

÷×÷×÷×

When solving a problem of the form (1.1) analytically, one ﬁrst looks for all points that satisfy

(1.4). After the set of candidates is determined, one then evaluates the Hessian ∇

J(θ) to verify

which are local minima. If several local minima are found and if, in addition, it can be shown that

J(θ) tends to ∞ as ||θ|| tends to inﬁnity, then the location of the global minimum θ

∗

can be found by

comparing the values of the local minima. It is worth noting that if there exists a unique stationary

point this analysis can be simpliﬁed. Indeed, if θ

∗

is the unique stationary point of J(θ) and if J(θ)

tends to ∞ as ||θ|| tends to inﬁnity, then θ

∗

is the unique location of the global mimimum of J(θ).

EXAMPLEEXAMPLE 1.2. This example is provided to illustrate the terminology used in the ﬁeld of optimization.

Consider the function J : R → R plotted in Figure 1.6. This function has a unique global minimum

that is attained at θ

∗

≈ −3. Now consider the same function but limit its domain to (0, ∞). Since

lim

θ→+∞

J(θ) = 0 we ﬁnd that J(θ) has 0 as improper minimum. Indeed, 0 is not attained by any

value for θ. In addition note that J

(θ) approaches 0 as θ tends to inﬁnity. Loosely speaking we could

express this by saying that “θ = +∞ is a stationary point of J(θ)”. The fact that J

(θ) tends to zero as

θ tends to inﬁnity is called the “vanishing gradient” problem, to which we shall come back in later

chapters.

-4

-2

-0.2

0.2

0.4

0.6

0.8

1.0

Figure 1.6: A function with “vanishing gradient”.

÷×÷×÷×

17 June 30, 2019

CHAPTER 1. DETERMINISTIC OPTIMIZATION

Numerical Methods

In most cases as in Example 1.1, it is impossible to solve the inversion problem ∇J = 0 analytically

and iterative numerical methods are used for ﬁnding a root θ

∗

of ∇

J = 0. Generally speaking, a

numerical algorithm for approximating the solution θ

∗

of ∇

J = 0 is a recursion of the form:

n+1

= θ

+ 

d(θ

), (1.8)

where, for each n, 

is called the stepsize or gain sequence and d(θ

) is called the direction of the

algorithm.

Methods for approximating θ

∗

can be classiﬁed according to the choice of the stepsize rule and

the directions. Together with an initial value θ

and a stopping rule, (1.8) constitutes a numerical

algorithm that terminates hopefully close to the true optimum, where “closeness” has to be deﬁned

appropriately.

Deﬁnition 1.5 A descent direction of a differentiable function J at a point θ ∈ R

is any vector d(θ) such

that ∇J(θ) d(θ) < 0.

A descent direction d(θ) is pointing away from the direction ∇J(θ).

Indeed (−∇J(θ) d(θ)) > 0 implies that there is an angle of less than 90

degrees between d(θ) and −∇J(θ). The ﬁgure to the right depicts the

situation. Recall that ∇J(θ) points towards the direction of growth of

the function. For a detailed geometric interpretation of the gradient,

we refer to Section A.1 in the Appendix.

Gradient-based methods for optimization use d(θ

) = −∇J(θ

)

as a direction in the algorithm,

which is clearly a descent direction. There are many methods available for gradient-based optimiza-

tion. Typically these algorithms are tailored to speciﬁc classes of function such as the conjugate-

gradient method and variations thereof, which is a popular method for optimization of quadratic

functions. The next section will discuss Newton’s Method which is a general method applying to

smooth functions.

*Newton’s Method

One of the most efﬁcient methods for unconstrained optimization is the method developed by New-

ton (published in 1685) and Raphson (1690). It was originally designed to ﬁnd the zeroes of a poly-

nomial. In the context of ﬁnding stationary points of J(θ), θ ∈ R

, let the vector G(θ) represent

the gradient ∇J(θ)

. From a point θ

, use a linear approximation of G(θ), that is, using Taylor’s

expansion,

G(θ

n+1

) ≈ G(θ

) + ∇G(θ)(θ

n+1

− θ

where now ∇G(θ) = ∇

J(θ) is a d × d matrix for each θ.

To obtain the zero (of the approximation) in one step, simply set G(θ

n+1

) = 0 in the approximation

and solve the RHS for θ

n+1

. Assuming that the inverse matrix of ∇G(θ) exists, this results in:

n+1

= θ

− [∇G(θ

)]

−1

G(θ

). (1.9)

In words, Newton’s method is a gradient decent method with step-size sequence 

= [∇G(θ

)]

−1

18 June 30, 2019

1.1. UNCONSTRAINED OPTIMIZATION

Theorem 1.2 Let J : R

→ R ∈ C

be a convex function, and assume that the Hessian is invertible (thus, it

is positive deﬁnite around any local minimum). Choose an initial point θ

∈ R

and let {θ

} be the sequence

deﬁned by (1.9), with G = ∇J

, that is,

n+1

= θ

− [∇

J(θ

)]

−1

∇J(θ

)

Suppose that

θ is an accumulation point of the sequence {θ

}such that ∇

θ) > 0, then

θ is a local minimum

of J(θ) and the rate of convergence is superlinear, that is, there exists a sequence {c

} such that c

tends to

zero as n tends to ∞ and for some ﬁnite N it holds that

kθ

n+1

−

θk ≤ c

kθ

−

θk, n ≥ N.

Furthermore, if J ∈ C

then the rate of convergence is quadratic, that is, there exists a constant c > 0 such

that, for large n,

kθ

n+1

−

θk ≤ ckθ

−

θk

The proof of the result uses Taylor’s approximation. In addition, positive semi-deﬁniteness of the

Hessian due to convexity implies Newton’s direction exists and it is an descent direction at every

point. Although very efﬁcient for convex functions, Newton’s method has a number of practical

problems when applied as a general purpose optimization method:

• Newton’s method ﬁnds zeros of the gradient, which may be locations of minima or inﬂection

points for general functions, and consequently it cannot be guaranteed that the Hessian is pos-

itive deﬁnite at every stationary point.

• The Hessian may not be invertible at every point.

• It needs calculation of gradients, Hessians, and Hessian inversion, all of which may be lengthy

numerical operations, rendering the method slow.

• Finally, when a closed form expression does not exist, approximations to gradients via ﬁnite

differences may make the method very slow, due to the sheer amount of function calculations

required for Hessian evaluation (2

For deterministic problems, the efﬁciency of a method is deﬁned in terms of CPU time to achieve a

given precision δ. A number of algorithms have been proposed under the common name of “quasi-

Newton” methods, which attempt to increase the efﬁciency of the method, overcoming the problems

pointed out above. In particular, if the function J(θ) is not convex, then for points θ

in regions

which are not convex Newton’s direction is not a descent direction. To ensure proper behavior of the

algorithm, one can choose the negative gradient, which is always a descent direction.

*Cauchy’s Method

The method known as steepest descent (or Cauchy’s) for minimization of a cost function J(θ) chooses

d(θ

) = −∇

J(θ

) at each iteration of (1.8). Originally proposed by Cauchy in 1847, instead of

premultiplying by the matrix [∇

J(θ

)]

−1

, the method chooses the step size to “jump” along the

direction d(θ

) to reach the minimum on that line, that is,



= arg min

>0

(J(θ

− ∇J(θ

)

)) .

In this section we present results that use the steepest descent direction d(θ

) = −∇J(θ

)

and focus

on decreasing stepsizes of the simplest form.

19 June 30, 2019

CHAPTER 1. DETERMINISTIC OPTIMIZATION

Gradient-based Methods: Non-Adaptive Step Sizes

As mentioned before, Newton’s method has a good convergence rate but every iteration may re-

quire too much computational time. Cauchy’s method can have slow convergence due to possible

zig-zagging of the iterations, and several modiﬁcations have been proposed for adaptive step sizes

(where 

depends on θ

, J(θ

), ∇J(θ

), etc). Common methods use Wolfe’s conditions [31, 32] and

Armijo’s rules [1], which ensure that all accumulation points are local minima. For deterministic

optimisation adaptive step sizes are undoubtedly superior to non-adaptive step sizes. However, the

focus of the present text is to extend the basic methodology for deterministic optimisation to prob-

lems where the observations of the function J(θ) and its gradients (if available) are noisy, and the

noise models may be very complex. For such a scenario it is often a better idea to use algorithm

parameters that will not be corrupted by the noise, which is why we only study non-adaptive step

sizes here. The gradient-based methods use d(θ) = −∇J(θ) as the direction of the algorithm, and the

step sizes can be of two kinds: either decreasing: 

↓ 0, or constant: 

≡ .

Without any detailed analysis, inspecting the mere structure of (1.8) allows us already to deduce

properties of the stepsize sequence. To see this, insert the expression for θ

on the right-hand side of

(1.8), which yields θ

n+1

= θ

n−1

+ 

d(θ

) + 

n−1

d(θ

n−1

) and continuing the recurrence,

n+1

= θ

i=0



d(θ

Suppose that d(·) is bounded. Then, for the algorithm to ﬁnd θ

∗

, the stepsizes have to satisfy

∞

n=1



= ∞, (1.10)

so that the sequence {θ

} is not conﬁned to some bounded set (or, equivalently, will cover any

bounded set as it can potentially reach any point in R

). Further conditions are required in order

to ensure convergence of the algorithm to the optimal θ

∗

, as we will in the upcoming theorem. How-

ever, before we can turn to the theorem and the proof thereof we will present a technical result.

Deﬁnition 1.6 Let Θ ⊂ R

be an open connected set. A mapping f : Θ → R is called Lipschitz continuous

if L ∈ R exists such that for any x, x + ∆ ∈ Θ is holds that

kf(x) − f(x + ∆)k ≤ L k∆k .

The constant L is called Lipschitz constant.

Before we state and prove the main result in this section, we provide a useful technical result.

Lemma 1.1 Consider the real-valued recursion:

n+1

= x

− g

+ h

, x

∈ R

where g

≥ 0 for all n, and the sequence h

is summable, i.e., |

| < ∞. Then either (i) x

→ −∞ or (ii)

converges to a ﬁnite value and

converges.

20 June 30, 2019

剩余237页未读，继续阅读

努力+努力=幸运

粉丝: 2
资源: 138

会员权益专享

"随机梯度技术与优化学习理论"

IE598NH-lecture-24-Stochastic Optimization for Reinforcement Learning.pdf

First-Order and Stochastic Optimization Methods for Machine Learning.pdf

Unit Tests for Stochastic Optimization.pdf

Derive the stochastic gradient descent algorithm

Stochastic Gradient Descent" (SGD)的MLA格式

from torch import optim

Stochastic Gradient Boosting是什么

import torch.nn as nn import torch.nn.functional as F import torch.optim as optim

torch.nn.Adam

tf.optimizers.Adam

机器学习中优化器有哪些

tf.keras.optimizers.SGD()

stochastic models, estimation, and control volume 1. pdf

torch.optim.SGD

能推荐几篇遗传算法优化的文献吗

不同梯度下降法程序实现

沈弢-Stochastic Gradient Push for Distributed Deep Learning1

会员权益专享

最新资源