Back to search

Cornell University

Complexity, conditioning, and saddle avoidance in nonsmooth optimization

Abstract

dc:description.abstract

Continuous optimization has become a prevalent tool across the sciences and engineering. Modern applications have displayed steady growth in problem sizes. Such sizes often prohibit the use of classical algorithmic solutionsthat heavily rely on costly operations, such as matrix inversion, and do not scale well. To counter this phenomenon practitioners have turned their focus to simpler first-order heuristics, such as gradient descent, that are often highly successful, yet are not well-understood. In this thesis, we study a few nonsmooth settings where simple algorithms are provably convergent. We start with the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient method of Chambolle and Pock (2011). The literature on PDHG has focused chiefly on feasible problems. When the problem is not feasible, the iterates of the algorithm do not converge. In this scenario, we show that the iterates diverge at a controlled rate towards a well-defined ray. Leveraging this fact, we design a simple scheme to extract certificates of infeasibility from the iterates. We then turn to unconstrained convex optimization and consider the classic {proximal bundle methods}, an algorithmic family dating back to the 70s. We prove convergence rates for bundle methods under a variety of assumptions. In particular, we show that these algorithms automatically adapt to problem regularity, exhibiting faster convergence rates. We complement these findings with a new parallelizable variant of the bundle method that attains near-optimal rates without prior knowledge of function parameters. These results improve on the limited existing convergence rates and provide a unified approach across problem settings and algorithmic details. After that, we study rapid local convergence guarantees for nonconvex formulations of low-rank matrix recovery problems, a problem family that includes phase retrieval, blind deconvolution, matrix completion, and robust PCA. Standard approaches for solving these problems use smooth penalty functions and often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension. In contrast, we show that natural nonsmooth penalty formulations have two clear advantages: (1) they do not suffer from the same type of ill-conditioning, and (2) they are robust against noise and gross outliers. Consequently, we prove that off-the-shelf algorithms for nonsmooth optimization converge at a rapid dimension-independent rate when initialized close to the solution, even when a constant fraction of the measurements are adversarially corrupted. To complement these local convergence guarantees, we turn to the question of escaping saddle points of nonsmooth functions. Recent work has shown that stochastically perturbed gradient methods can efficiently strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms can escape strict saddle points of the Moreau envelope at a controlled rate.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Applied Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Applied Mathematics
Grantor
Cornell University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Diaz Diaz, Mateo
Chair dc:contributor.chair
  • Davis, Damek Shea
Committee members dc:contributor.committeemember
  • Kleinberg, Robert David
  • Renegar, James
  • Lewis, Adrian S.

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15160163
Dc Identifier Other
ProQuest Submission ID: 12599
ProQuest Publication ID: 28645871

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

Diaz Diaz, Mateo. Complexity, conditioning, and saddle avoidance in nonsmooth optimization. Doctor of Philosophy thesis, Cornell University, 2021. https://hdl.handle.net/1813/110534