Title: The condition number of a function relative to a set

Speaker: Javier Peña (Carnegie-Mellon University)

Date and Time: March 3rd, 2021, 11:00 AEDT (Register here for remote connection via Zoom)

Abstract: The condition number of a differentiable convex function, namely the ratio of its smoothness to strong convexity constants, is closely tied to fundamental properties of the function. In particular, the condition number of a quadratic convex function is the square of the aspect ratio of a canonical ellipsoid associated to the function. Furthermore, the condition number of a function bounds the linear rate of convergence of the gradient descent algorithm for unconstrained convex minimization.

We propose a condition number of a differentiable convex function relative to a reference set and distance function pair. This relative condition number is defined as the ratio of a relative smoothness to a relative strong convexity constants. We show that the relative condition number extends the main properties of the traditional condition number both in terms of its geometric insight and in terms of its role in characterizing the linear convergence of first-order methods for constrained convex minimization.

This is joint work with David H. Gutman at Texas Tech University.

Title: Necessary conditions for transversality properties

Speaker: Nguyen Duy Cuong (Federation University)

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

Abstract: Transversality properties of collections of sets play an important role in optimization and variational analysis, e.g., as constraint qualifications, qualification conditions in subdifferential, normal cone and coderivative calculus, and convergence analysis of computational algorithms. In this talk, we present some new results on primal (geometric, metric, slope) and dual (subdifferential, normal cone) necessary (in some cases also sufficient) conditions for transversality properties in both linear and nonlinear settings. Quantitative relations between transversality properties and the corresponding regularity properties of set-valued mappings are also discussed.

Title: Subgradient Projection Algorithm with Computational Errors

Speaker: Alexander J. Zaslavski (The Technion – Israel Institute of Technology)

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

Abstract: We study the subgradient projection algorithm for minimization of convex and nonsmooth functions, under the presence of computational errors. We show that our algorithms generate a good approximate solution, if computational errors are bounded from above by a small positive constant. Moreover, for a known computational error, we find out what an approximate solution can be obtained and how many iterates one needs for this.

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.)