Title: Gradient-Normalized Smoothness for Optimization with Approximate Hessians

Abstract: In this talk, we discuss the design of optimization algorithms that use approximate second-order information to achieve fast global convergence rates for both convex and non-convex objectives. The key innovation of our analysis is a novel notion called Gradient-Normalized Smoothness, which characterizes the maximum radius of a ball around the current point that yields a good relative approximation of the gradient field. Our theory establishes a natural intrinsic connection between Hessian approximation and the linearization of the gradient. Importantly, Gradient-Normalized Smoothness does not depend on the specific problem class of the objective functions, while effectively translating local information about the gradient field and Hessian approximation into the global behavior of the method.  This new concept equips approximate second-order algorithms with universal global convergence guarantees, recovering state-of-the-art rates for functions with Hölder-continuous Hessians and third derivatives, quasi-self-concordant functions, as well as smooth classes in first-order optimization. These rates are achieved automatically and extend to broader classes, such as generalized self-concordant functions. We demonstrate direct applications of our results for global linear rates in logistic regression and softmax problems with approximate Hessians, as well as in non-convex optimization using Fisher and Gauss-Newton approximations.

Bio: Nikita Doikov joined Cornell in January 2026 as an Assistant Professor in the School of Operations Research and Information Engineering. He received his PhD from UCLouvain, Belgium, under the supervision of Yurii Nesterov in 2021. After that, he was a postdoctoral researcher at EPFL, Switzerland, working in the Machine Learning and Optimization Laboratory led by Martin Jaggi. He also gained industrial experience as an intern at Google in 2016 and 2018.