Title: New Accelerated Methods for Optimization and Reinforcement Learning

Date: July 16th, 2025

Time: 10:00 AM – 11:30 AM EST

Location: Virtual

Meeting Link: https://gatech.zoom.us/j/9539444986

Tianjiao Li

Ph.D. Candidate in Operations Research

School of Industrial and Systems Engineering

Georgia Institute of Technology

Committee:

Dr. Guanghui Lan (advisor), School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Ashwin Pananjady (co-advisor), School of Industrial and Systems Engineering & School of Electrical and Computer Engineering, Georgia Institute of Technology

Dr. Anatoli Juditsky, Laboratoire Jean Kuntzmann, Université Grenoble Alpes

Dr. Renato Monteiro, School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Arkadi Nemirovski, School of Industrial and Systems Engineering, Georgia Institute of Technology

Abstract:

First-order methods are widely used to tackle modern data science and machine learning problems. In this thesis, we focus on the design and analysis of novel accelerated first-order algorithms for large-scale nonlinear and stochastic optimization, addressing key challenges such as stochasticity, nonconvexity, and uncertainty in problem structures and parameters. We also develop new accelerated methods for reinforcement learning, accompanied by improved computational and statistical complexity guarantees.

The main body of this thesis is divided into two parts. Part I studies accelerated methods for different classes of optimization problems. Chapter 2 considers stochastic convex optimization under rather general state-dependent noise assumptions. We investigate two accelerated stochastic approximation routines—stochastic accelerated gradient descent (SAGD) and stochastic gradient extrapolation (SGE)—which carry a particular duality relationship. Although both routines can achieve the optimal convergence rate under appropriate conditions, the corresponding assumptions for the SGE algorithm are more general; they allow, for instance, heavy tail noises and discontinuous score functions. We also discuss the application of the SGE to problems satisfying quadratic growth conditions, and show how it can be used to recover sparse solutions.

Chapters 3 to 5 focus on designing adaptive accelerated algorithms for optimization problems with ambiguous structures and unknown parameters. In Chapter 3, we begin with convex optimization and propose a new accelerated gradient descent type algorithm, which demonstrates that line search is superfluous in attaining the optimal rate of convergence when parameters are not given a priori. In Chapter 4, we consider bilinear saddle point and linearly constrained problems, and introduce new primal-dual and ADMM-type methods, which can fully adapt to the linear operator while requiring no line search subroutines. In Chapter 5, we present a novel class of projected gradient (PG) methods for stochastic smooth but not necessarily convex problems, establishing new complexity bounds in different oracle settings and developing new parameter-free stepsize policies.

In Part II, we develop acceleration schemes for problems arising from reinforcement learning, with a focus on policy evaluation. Chapter 6 considers a broader class of stochastic variational inequalities with Markovian noise and proposes a fast temporal difference (FTD) method, which improves upon the iteration complexity of the classical temporal difference (or stochastic approximation) method. In Chapter 7, we further explore the problem of policy evaluation with linear function approximation, by proving lower bounds that establish baselines on both the deterministic error and stochastic error. We then develop an accelerated, variance-reduced fast temporal difference algorithm (VRFTD) that simultaneously matches both lower bounds and attains a strong notion of instance-optimality.