The condition number of a function relative to a set

By David H. Gutman, Javier F. Peña. 2019

26 citations recorded by the source corpus.

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 convex set and distance function pair. This relative condition number is defined as the ratio of relative smoothness to 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. When the reference set X is a convex cone or a polyhedron and the function f is of the form $$f = g\circ A$$ f = g ∘ A , we provide characterizations of and bounds on the condition number of f relative to X in terms of the usual condition number of g and a suitable condition number of the pair ( A ,  X ).

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Thomas Kerdreux
2. Damien Scieur
3. Simon Lacoste-Julien
4. Lewis Liu
5. Peter Richtárik
6. Sebastian Pokutta
7. Francis R. Bach
8. Fabian Pedregosa

In Computational Mechanics

1. Thomas Kerdreux
2. Damien Scieur
3. Simon Lacoste-Julien
4. Lewis Liu
5. Peter Richtárik
6. Fabian Pedregosa
7. Sebastian Pokutta
8. Zeyuan Allen-Zhu

In Numerical Analysis

1. Simon Lacoste-Julien
2. Lewis Liu
3. Thomas Kerdreux
4. Damien Scieur
5. Sebastian U. Stich

In Numerical Methods & Scientific Computing

1. Simon Lacoste-Julien
2. Lewis Liu
3. Thomas Kerdreux
4. Damien Scieur

Citations in the corpus

• Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “39), an affine invariant measure of (generalized) strong convexity, while [Gutman et al. 2020] consider strongly convex functions relative to a pair ( , ω ) where ω is a distance-like function.”