Title: Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods,
Abstract: We study the smooth structure of convex functions by generalizing a powerful
concept so-called self-concordance introduced by Nesterov and Nemirovskii in
the early 1990s to a broader class of convex functions, which we call
generalized self-concordant functions. This notion allows us to develop a
unified framework for designing Newton-type methods to solve convex optimiza-
tion problems. The proposed theory provides a mathematical tool to analyze both
local and global convergence of Newton-type methods without imposing
unverifiable assumptions as long as the un- derlying functionals fall into our
generalized self-concordant function class. First, we introduce the class of
generalized self-concordant functions, which covers standard self-concordant
functions as a special case. Next, we establish several properties and key
estimates of this function class, which can be used to design numerical
methods. Then, we apply this theory to develop several Newton-type methods for
solving a class of smooth convex optimization problems involving the
generalized self- concordant functions. We provide an explicit step-size for
the damped-step Newton-type scheme which can guarantee a global convergence
without performing any globalization strategy. We also prove a local quadratic
convergence of this method and its full-step variant without requiring the
Lipschitz continuity of the objective Hessian. Then, we extend our result to
develop proximal Newton-type methods for a class of composite convex
minimization problems involving generalized self-concordant functions. We also
achieve both global and local convergence without additional assumption.
Finally, we verify our theoretical results via several numerical examples, and
compare them with existing methods.