First Advisor

Dacian Daescu

Date of Award

Spring 6-11-2026

Document Type

Thesis

Degree Name

Bachelor of Science (B.S.) in Mathematics and University Honors

Department

Mathematics and Statistics

Language

English

Subjects

Katyusha, Uniform Stability, Nesterov Accelerated Gradient, Stochastic Variance-Reduced Gradient, Lyapunov Functions, Semidefinite Programming

DOI

10.15760/honors.1838

Abstract

Acceleration of convergence and reduction of variance constitute a trade-off in the design of stochastic optimization machine learning algorithms. Katyusha was introduced to address this trade-off, synthesizing Nesterov Accelerated Gradient (NAG) and Stochastic Variance-Reduced Gradient (SVRG) into a single first-order optimizer with promising empirical performance. However, the generalization properties of Katyusha remain largely unexplored. We conjecture that, in the smooth quadratic regime (i.e., under assumptions of strong convexity and smoothness of the loss function, and boundedness of gradients), Katyusha is uniformly stable in the sense of Bousquet and Elisseeff. Instantiating our framework for NAG, we extend the use of Lyapunov functions from convergence analysis to uniform stability analysis for accelerated first-order optimizers and derive a uniform stability bound for smooth quadratic NAG via a Lyapunov function. We then show that, by modeling NAG as a Lur'e type feedback system with convexity conditions encoded as integral quadratic constraints (IQC's), the uniform stability of NAG can be found by solving a feasibility problem with a linear matrix inequality (LMI) constraint via semi-definite programming (SDP), and show that any first-order optimizer expressible in Lur'e form can, in theory, have its uniform stability bound in the smooth quadratic regime numerically derivable via this SDP scheme. We supplement these conjectures with numerical experiments on each of NAG and Katyusha that cohere with our conjecture(s). We propose how to derive a uniform stability bound for smooth quadratic Katyusha via the aforementioned SDP scheme. These preliminary results lay the groundwork for a proof of the uniform stability of smooth quadratic Katyusha via the conceptual framework detailed herein.

Persistent Identifier

https://archives.pdx.edu/ds/psu/44771

Download

Share

COinS