6

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 $k$ columns, then its rank is at most $k$, so this is a low-rank update to the $A$ matrix. Low rank updates are important in computational linear algebra and ...


4

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 do by a factor of $1/t$, and it's $O(N^2)$ when $t\geq N$. But $t$ is determined adaptively by the behaviour of the loss function, so the point is just that you'...


3

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, you would find that in the worst case, CG would nearly stagnate for the first $r+1$ iterations, then rapidly converge towards the solution for every iteration ...


2

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 $z_{i}$ variables by substituting $x_{i}=x_{1}+z_{1}+\ldots + z_{i}$, $i=2, 3, \ldots, n$. Your separation constraints become $k \leq z_{i}$


2

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 with low rank updates by enforcing properties of the real hessian (e.g symmetry, etc.). You can also have a full update every certain number of iterations and a ...


2

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 distance from $I$; that's what norms do.


1

(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 tested directly translated algorithm pseudocode implementations of GD and L-BFGS. See the code and all my experiments here. Even in the nicest setting you can think ...


1

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 generally required for convergence even if you used the exact gradient when determining your search direction. Meaning, BFGS will not generally converge by itself ...


1

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

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 secant" methods), and you want to leverage your knowledge of the computable part as much as possible.


Only top voted, non community-wiki answers of a minimum length are eligible