TomographicImaging
Added BB step size rule to our step size methods
Changes
Adds the BB long and short (from https://en.wikipedia.org/wiki/Barzilai-Borwein_method) step size rule
Adds the stabilisation (adaptive and non-adaptive) from Burdakov, O., Dai, Y.H. and Huang, N., 2019. Stabilized barzilai-borwein method. arXiv preprint arXiv:1907.06409.
Testing you performed
Please add any demo scripts to https://github.com/TomographicImaging/CIL-Demos/tree/main/misc
For a limited angle parallel beam leastsquares +Tikhonov reconstruction using GD the comparison of step size methods is below:
For a random matrix Ax=b problem, with a leastsquares objective, reconstruction using GD the comparison of step size methods is below:
For these couple of examples "SHORT" is the most stable. Removing the stabilisation has the potential for very fast convergence but is unstable (and not guaranteed to converge!)
Related issues/links
Closes #748
Checklist
- [x] I have performed a self-review of my code
- [x] I have added docstrings in line with the guidance in the developer guide
- [x] I have updated the relevant documentation
- [x] I have implemented unit tests that cover any new or modified functionality
- [ ] CHANGELOG.md has been updated with any functionality change
- [ ] Request review from all relevant developers
- [x] Change pull request label to 'Waiting for review'
Contribution Notes
Please read and adhere to the developer guide and local patterns and conventions.
- [x] The content of this Pull Request (the Contribution) is intentionally submitted for inclusion in CIL (the Work) under the terms and conditions of the Apache-2.0 License
- [x] I confirm that the contribution does not violate any intellectual property rights of third parties
Thank you, I can take a look. Could you: Clarify what is plotted on the y-axis, maybe better show y as log, or loglog, and I don't see the green one?
I wasn't aware there so many variants and stabilization methods for BB. We also used BB some years back for a smoothed TV regularization problem and compared with Nesterov acceleration
https://doi.org/10.1007/s10543-011-0359-8
Do you see if these BB methods are related?
Thank you, I can take a look. Could you: Clarify what is plotted on the y-axis, maybe better show y as log, or loglog, and I don't see the green one?
Thanks @jakobsj, I have updated those plots so hopefully they are a bit clearer
I wasn't aware there so many variants and stabilization methods for BB. We also used BB some years back for a smoothed TV regularization problem and compared with Nesterov acceleration
https://doi.org/10.1007/s10543-011-0359-8
Do you see if these BB methods are related?
It looks like you do the "LONG" version but then do an additional back tracking procedure.
This could be an option, instead of the "stabilisation" procedure that I use with an option for the user to turn it on or off. I think it was introduced in
Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997)
but I am having trouble accessing it
I wasn't aware there so many variants and stabilization methods for BB. We also used BB some years back for a smoothed TV regularization problem and compared with Nesterov acceleration https://doi.org/10.1007/s10543-011-0359-8 Do you see if these BB methods are related?
It looks like you do the "LONG" version but then do an additional back tracking procedure.
This could be an option, instead of the "stabilisation" procedure that I use with an option for the user to turn it on or off. I think it was introduced in
Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997)
but I am having trouble accessing it
Oh and many thanks for comparing. I think no reason to add the backtracking instead of the stabiliser.