Back to search

Cornell University

METRIC AND TAME GEOMETRY IN OPTIMIZATION

Abstract

dc:description.abstract

Structure in optimization is traditionally studied through variational analysis. Structural results usually require convexity or other regularity conditions. However, contemporary optimization involves problems that lie beyond this traditional scope, especially in machine learning, both in Euclidean space and in non-Euclidean metric spaces. This thesis pursues theories for such problems that reveal underlying geometric structure and aid algorithm design and analysis. A central philosophy in the thesis is to highlight the slope as a tool for capturing first-order information of objectives. This engenders a subgradient-free development: subgradients are indirect in depicting structure and do not extend naturally to non-Euclidean settings. The development focuses on two ideas traditionally studied through subgradients. The first idea is identification: the phenomenon of a set being identified by certain convergent sequences in finite time. By re-interpreting identification via the slope, the thesis extends the idea from Euclidean space to general metric spaces, and establishes results on objective growth rates and necessary conditions for optimization on metric spaces. An extension of identification behavior from discrete-time sequences to continuous-time trajectories is also included. The second idea is the Kurdyka-Łojasiewicz (KL) inequality: a popular tool for convergence analysis in optimization. Defining the KL inequality via the slope reveals its connection with identification, and more importantly its impact on complexity analysis of first-order methods in metric spaces. The prevalence of identifiability and of objectives satisfying the KL inequality is established in the literature from semialgebraic (or, more generally, tame) geometry. Based on the same technique, the thesis presents two other results. The first characterizes the structure of conservative gradient fields, a notion of generalized gradients especially useful in analyzing deep learning methods. The second concerns the generic prevalence of partly smooth set-valued mappings, a type of structure known to be associated with identifiable sets. Furthermore, the thesis gives a short slope-based proof for the fundamental fact that semialgebraic functions possess the KL property. Finally, to unify and relax traditional structural assumptions such as convexity, smoothness, and their compositions, the thesis proposes a new type of implicit structure — smooth approximate convexity. The thesis shows the prevalence of such structure and demonstrates its applicability with a Riemannian optimization example.

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
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tian, Tonghua
Chair dc:contributor.chair
  • Lewis, Adrian
Committee members dc:contributor.committeemember
  • Davis, Damek
  • Scheinberg, Katya

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16575526
Dc Identifier Other
ProQuest Submission ID: 14207
ProQuest Publication ID: 31237872

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

Tian, Tonghua. METRIC AND TAME GEOMETRY IN OPTIMIZATION. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/116015