Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- Notation
- 1 Introduction
- 2 Simple examples
- 3 Embedded geometry: first order
- 4 First-order optimization algorithms
- 5 Embedded geometry: second order
- 6 Second-order optimization algorithms
- 7 Embedded submanifolds: examples
- 8 General manifolds
- 9 Quotient manifolds
- 10 Additional tools
- 11 Geodesic convexity
- References
- Index
4 - First-order optimization algorithms
Published online by Cambridge University Press: 09 March 2023
- Frontmatter
- Dedication
- Contents
- Preface
- Notation
- 1 Introduction
- 2 Simple examples
- 3 Embedded geometry: first order
- 4 First-order optimization algorithms
- 5 Embedded geometry: second order
- 6 Second-order optimization algorithms
- 7 Embedded submanifolds: examples
- 8 General manifolds
- 9 Quotient manifolds
- 10 Additional tools
- 11 Geodesic convexity
- References
- Index
Summary
The main purpose of this chapter is to define and analyze Riemannian gradient descent methods. This family of algorithms aims to minimize real-valued functions (called cost functions) on manifolds. They apply to general manifolds, hence in particular also to embedded submanifolds of linear spaces. The previous chapter provides all necessary geometric tools for that setting. The initial technical steps involve constructing first-order Taylor expansions of the cost function along smooth curves, and identifying necessary optimality conditions (at a solution, the Riemannian gradient must vanish). Then, the chapter presents the algorithm and proposes a worst-case iteration complexity analysis. The main conclusion is that, under a Lipschitz-type assumption on the gradient of the cost function composed with the retraction, the algorithm finds a point with gradient smaller than $\varepsilon$ in at most a multiple of $\varepsilon^2$ iterations. The chapter ends with three optional sections: They discuss local convergence rates, detail how to compute gradients in practice and describe how to check that a gradient is correctly implemented.
- Type
- Chapter
- Information
- An Introduction to Optimization on Smooth Manifolds , pp. 51 - 78Publisher: Cambridge University PressPrint publication year: 2023