(Solved): For a function f:R^(d)->R, a point x_(0) is a locel minimum if there exists \delta >0 such tha ...

For a function

, a point

is a locel minimum if there exists

such that for all

with

. Similarly, a point

is a local maximum if the opposite holds: if there exists

such that for all

with

. There exist smooth functions for which finding a local minimum is NP-hard. However, if

is differentiable, then one necessary condition for

to be a local minimum is that

. (a) This is necessary but not sufficient! Give an example of a function in two dimensions and a point

such that

but

is neither a local minimum nor a local maximum of

. [1 points] (b) Inspite of the above, vanishing gradients is often desired. Suppose we have a

-smooth function

. Show that gradient descent can be used to find a point

such that

. How many iterations of GD do you need for finding such a point? Your bound can depend on the starting point,

, and the value of the glolbal optimum (which you can assume is bounded). [2 points] 1 [Hint: Try to use the monotonicity property of GD and combine all the equations over the iterates.] The goal of this exercise is to implement and compare GD, and Nesterov's accelerated gradient descent (NAGD) for logistic regression. Suppose we have binary data, i.e., the labels are 0 or 1 . When trying to fit binary labels with linear predictors, a commonly used loss function is the logit loss function:

(also known as cross-entropy loss etc.). One commonly used parameterized predictor family is

, where (