Back to search

Cornell University

Combatting ill-conditioning and heavy-tailed noise in non-convex optimization

Abstract

dc:description.abstract

Ill-conditioning is a major challenge for optimization with first-order methods. This is especially the case for stochastic optimization, where the classical preconditioners - designed to compensate ill-conditioned curvatures - are hard to construct due to the inherent variability of stochastic gradients. Compounding this challenge, heavy-tailed noise further corrupts the reliability of gradient-based update directions. This thesis confronts these challenges through three algorithms. For deterministic non-convex problems, we analyze a subgradient method whose convergence rate is independent of the functional conditioning. In stochastic regimes, we derive a stochastic gradient method with block-coordinate stepsizes that effectively combat imbalanced gradients and inhomogeneous noise. Finally, we propose a statistically efficient data-driven method that adapts to the heavy-tail distribution of the noise. In Chapter 2, we analyze a preconditioned subgradient method for optimizing composite functions $h\circ c$, where $h$ is a locally Lipschitz function and $c$ is a smooth nonlinear mapping. We prove that when $c$ satisfies a constant rank property and $h$ is semismooth and sharp on the image of $c$, the method converges linearly. In contrast to standard subgradient methods, its oracle complexity is invariant under reparameterizations of $c$. In Chapter 3, we consider stochastic approximation methods with block-coordinate stepsizes and propose adaptive stepsize rules that aim to minimize the expected distance of the next iterate from an optimal point.These stepsize rules use online estimates of the mean and second moment of the search direction along each block coordinate. The popular Adam algorithm can be interpreted as using a particular heuristic for such estimation. By leveraging a simple conditional estimator, we derive variants that require fewer hyperparameters and optimizer states but obtain comparable performance. In addition, our convergence analysis relies on a simple aiming condition that is weaker than convexity, thus has broader applicability. In Chapter 4, we develop statistically efficient data-driven methods that can adapt to the heavy-tail distribution of the noise and obtain optimal performance. Our methods build upon the pioneering work of Polyak and Tsypkin in the 1980's, who developed a framework of nonlinear stochastic gradient methods where the stochastic gradients first go through a monotone nonlinear mapping, determined by the probability distribution of the noise, before being used to update the optimization variable. These methods are statistically efficient, in the sense that their asymptotic performance achieves the Cram\'er-Rao lower bound. We extend the framework of Polyak and Tsypkin to the non-asymptotic regime, showing that the same nonlinear mapping obtains the optimal statistical performance with finite samples; in addition, we allow the nonlinear mapping to be non-monotone, thus can handle heavier-tail noises than Laplacian. Empirically, we identify families of heavy-tail distributions that not only give good approximations in practice but also admit simple nonlinear mappings and can be implemented efficiently. Chapter 5 documents future directions beyond the scope of this thesis.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jiang, Tao
Chair dc:contributor.chair
  • Davis, Damek
Committee members dc:contributor.committeemember
  • Damle, Anil
  • Lewis, Adrian
  • Scheinberg, Katya
  • Renegar, James

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16938407
Dc Identifier Other
ProQuest Submission ID: 14976
ProQuest Publication ID: 32000551

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Jiang, Tao. Combatting ill-conditioning and heavy-tailed noise in non-convex optimization. Doctor of Philosophy thesis, Cornell University, 2025. https://hdl.handle.net/1813/117506