Mathematics of Computation and Optimisation

Title: Coordinate Descent Without Coordinates: Tangent Subspace Descent on Riemannian Manifolds

Speaker: Nam Ho-Nguyen (University of Sydney)

Date and Time: February 10th, 2021, 11:00 AEDT (Register here for remote connection via Zoom)

Abstract: We consider an extension of the coordinate descent algorithm to manifold domains, and provide convergence analyses for geodesically convex and non-convex smooth objective functions. Our key insight is to draw an analogy between coordinate blocks in Euclidean space and tangent subspaces of a manifold. Hence, our method is called tangent subspace descent (TSD). The core principle behind ensuring convergence of TSD is the appropriate choice of subspace at each iteration. To this end, we propose two novel conditions: the gap ensuring and C-randomized norm conditions on deterministic and randomized modes of subspace selection respectively. These ensure convergence for smooth functions, and are satisfied in practical contexts. We propose two subspace selection rules of particular practical interest that satisfy these conditions: a deterministic one for the manifold of square orthogonal matrices, and a randomized one for the more general Stiefel manifold. (This is joint work with David Huckleberry Gutman, Texas Tech University.)

Title: Scaled Relative Graph: Nonexpansive operators via 2D Euclidean Geometry

Speaker: Ernest Ryu (Seoul National University)

Date and Time: November 25th, 2020, 17:00 AEDT (Register here for remote connection via Zoom)

Abstract: Many iterative methods in applied mathematics can be thought of as fixed-point iterations, and such algorithms are usually analyzed analytically, with inequalities. In this work, we present a geometric approach to analyzing contractive and nonexpansive fixed point iterations with a new tool called the scaled relative graph (SRG). The SRG provides a rigorous correspondence between nonlinear operators and subsets of the 2D plane. Under this framework, a geometric argument in the 2D plane becomes a rigorous proof of contractiveness of the corresponding operator.

Title: Local and Global Inverse and Implicit Function Theorems

Speaker: Aram Arutyunov (Moscow State University) & S.E. Zhukovskiy (V. A. Trapeznikov Institute of Control Sciences of RAS)

Date and Time: November 18th, 2020, 17:00 AEDT (Register here for remote connection via Zoom)

Abstract: In the talk, we present a local inverse function theorem on a cone in a neighbourhood of abnormal point. We present a global inverse function theorem in the form of theorem on trivial bundle, guaranteeing that if a smooth mapping of finite-dimensional spaces is uniformly nonsingular, then it has a smooth right inverse satisfying a priori estimate. We also present a global implicit function theorem guaranteeing the existence and continuity of a global implicit function under the condition that the mappings in question are uniformly nonsingular. The generalization of these results to the case of mappings of Hilbert spaces and Banach spaces are discussed.