Derivación de la regla de actualización del descenso gradual

Question

Estoy tratando de entender la interpretación de Gradient Descent proporcionada en los apuntes del curso de Optimización Convexa 2019 de Ryan Tibshirani:

http://www.stat.cmu.edu/~ryantibs/convexopt-S15/scribes/05-grad-descent-scribed.pdf

Ya que para mí son la explicación más clara del tema que pude encontrar.

Mientras que puedo seguir cómo la función puede ser aproximada en el punto y como:

$$f(y) f(x) + f(x)^T (y x) + \frac{1}{2}(y x)^T ^2f((x y) + y)(y x)$$

Que al reemplazar $^2f((x y) + y)$ con $\frac{1}{t}I$ se puede reescribir como

$$f(y) f(x) + f(x)^T(y x) + \frac{1}{2t}||y x||_2^2 = g(y)$$

Tengo problemas para seguir la primera declaración iff dada aquí:

$$g(y) = 0 f(x)+ \frac{1}{t}(y x) = 0 y = xtf(x)$$

Que, si he entendido bien, deriva la regla de actualización de GD fijando primero su derivada de $g(y)$ a 0, lo que resulta en $f(x)+ \frac{1}{t}(y x)$ .

Mi conjetura es que el autor (al igual que otros que he tratado de consultar, que proporcionan el mismo razonamiento en una forma ligeramente diferente - véase, por ejemplo, la diapositiva 19 aquí: https://www.cs.huji.ac.il/~shais/Lectures2014/lecture6.pdf , de los apuntes de clase de Shai Shalev-Shwartz, adaptado de la página 185 del libro de 2014 "Understanding Machine Learning:From Theory to Algorithms" del mismo autor con Shai Ben-David) no ofrece una explicación paso a paso de este pasaje debido a su trivialidad.

Sin embargo, agradecería mucho que alguien pudiera desglosar matemáticamente este pasaje concreto y señalar las reglas que lo sustentan.

Answer 1

$$g(y)=f(x) + \nabla f(x)^T(y-x) + \frac1{2t}\|y-x\|_2^2$$

Diferenciando con respecto a $y$ ,

$$\nabla g(y) = \nabla f(x) + \frac1{t}(y-x)$$

Por lo tanto, $$\nabla g(y)=0 \iff \nabla f(x) + \frac1t (y-x)=0$$

lo que equivale a $$\frac1t(y-x) = -\nabla f(x)$$

$$y=x-t\nabla f(x)$$

Tenga en cuenta que hemos utilizado

$$\nabla_y (a^Ty)=a$$

desde $$\frac{\partial }{\partial y_i}\sum_{j=1}^n a_iy_j = a_i$$

y

$$\nabla _y \|y\|^2 = \nabla_y (y^Ty)=2y$$

desde $$\frac{\partial }{\partial y_i}\sum_{j=1}^n y_j^2 = 2y_i$$