1
$\begingroup$

Given a strongly convex function $f(x)$ with Lipschitz continuous gradient and Lipschitz Hessian, i.e.,

$$\mu I \leq \nabla ^2 f(x)\leq LI,\quad ||\nabla^2f(x)-\nabla f^2(y)||\leq M||x-y||^2,$$

and if we use the BFGS to approximate the curvature information, i.e., $$B_{t+1} = B_t+\frac{y_ty_t^\top}{y_t^\top s_t}-\frac{B_ts_ts_t^\top B_t}{s_t^\top B_ts_t},$$

where $y_t=\nabla f_{t+1}-\nabla f_t$ and $s_t=x_{t+1}-x_t$, can we bound the difference between $B_t$ and $\nabla^2 f_t$ other than the triangle inequality ? It seems a intuitive question to ask but I couldn't find anything on this. $$||B_t-\nabla^2 f_t||\leq \,\,??$$ You can also assume $\gamma I\leq B_t\leq \Gamma I$ if that helps. Feel free to put on more "meaningful" assumptions.

$\endgroup$
2
  • $\begingroup$ how do you update $x_t$ ? $\endgroup$
    – Red shoes
    Mar 7, 2021 at 3:59
  • $\begingroup$ Assuming I am updating as $x_{t+1}=x_t-\epsilon_t B_t^{-1}\nabla f(x_t)$ where the step size is determined by some line search methods. $\endgroup$
    – Lavender
    Mar 8, 2021 at 19:49

0

You must log in to answer this question.