17
votes
Accepted
Are Quasi-Newton methods computationally impractical?
I'm guessing you're referring to the discussion on pages 188-189 of that book.
The author doesn't give much detail on quasi-Newton methods or substantiate the $\mathscr O(W^2)$ complexity estimate.
To ...
- 9,813
11
votes
Are Quasi-Newton methods computationally impractical?
Traditional quasi-newton methods like BFGS require $O(n^{2})$ storage for a potentially fully dense quasi-Hessian matrix and $O(n^{2})$ work in each iteration to update the factorized quasi-Hessian ...
- 18.5k
7
votes
Accepted
Low-rank updates in BFGS
A low rank update to an $n$ by $n$ matrix $A$ is an update of the form
$A=A+UU^{T}$
where $U$ is matrix with $n$ rows but very few columns (typically just one or two.) If the matrix $UU^{T}$ has $...
- 18.5k
5
votes
Difference between asymptotic and non-asymptotic convergence in optimization?
Traditionally, the convergence of optimization algorithms has been analyzed in terms of the asymptotic rate of convergence. A quadratically convergent algorithm has $x_{k} \rightarrow x^{*}$ and
$\...
- 18.5k
4
votes
Accepted
Computational complexity of Newton's method
If you take $m$ steps, and update the Jacobian every $t$ steps, the time complexity will be $O(m N^2 + (m/t)N^3)$. So the time taken per step is $O(N^2+N^3/t)$. You're reducing the amount of work you ...
- 11.4k
3
votes
Accepted
The linear system in Quasi Newton method
It is a well-known theorem that conjugate gradients is guaranteed to converge (in exact arithmetic) within $r+1$ steps for an identity-plus-rank-$r$ matrix, regardless of its size. In finite precision,...
- 2,455
2
votes
Linear constraints for L-BFGS-B
One approach to this problem is to reparameterize your problem in terms of
$x_{1}$
and
$z_{i}=x_{i}-x_{i-1}$, $i=2, \ldots, n-1$.
You can then rewrite your objective function in terms of the the ...
- 18.5k
2
votes
Low-rank updates in BFGS
To add on Brian's answer. The idea behind the low rank update is to find what an approximation that is "good enough", thus saving on computation resources. The BFGS method approximates the hessian ...
- 89
2
votes
Accepted
Interpretation of error between Hessian approximation and real Hessian - Quasi-Newton Method
Either I am not understanding the issue, or you're making it out to be more difficult than it really is.
You have a thing $A$ that should ideally be equal to $I$. The norm $\|I-A\|_2$ measures its ...
- 10.6k
1
vote
When does L-BFGS outperform GD?
(Not exactly an answer to my question, but some empirical experiments which might give guidance to what a worst-case analysis of the L-BFGS iteration of a quadratic function should result in). I ...
- 211
1
vote
Sensitivity of BFGS to the accuracy of the gradient
From a pure convergence point of view, I believe the only thing that's necessary is to satisfy the convergence criteria from a globalization method such as a line-search or trust-region. This is ...
- 747
1
vote
Product of rank one updates as a low rank update for quasi newton/BFGS
You can do this using the Sherman-Morrison Formula and some other tricks, detailed starting on page 124 of Kelley, Iterative Methods for Linear and Nonlinear Equations
- 1,832
1
vote
Accepted
Doubt regarding principled approach towards approximating the Hessian
You may find this paper relevant. They give some BFGS-inspired methods and convergence proofs for cases where the Hessian is the sum of a part you can compute easily and a part you can't ("structured ...
- 9,813
Only top scored, non community-wiki answers of a minimum length are eligible