Towards Fine-Grained Complexity of Nonsmooth Optimization
Abstract
First-order, or (sub)gradient-based, algorithms stand as the preferred method for large-scale optimization, owing to their inherent simplicity, nearly linear scaling with problem size, and compatibility with parallel computation. Since the pioneering work of Nemirovski and Yudin, the worst-case subgradient oracle complexity of first-order methods has been extensively studied and characterized in general normed vector spaces, under broad assumptions about the Lipschitz continuity of the objective function and-or its high-dimensional derivatives (provided they exist), leading to what is currently considered a well-understood domain. However, the worst-case complexity characterization of these methods seems overly pessimistic for many instances commonly encountered in practice. To address this large gap in our current understanding, this project focuses on advancing the theory of nonsmooth first-order optimization, aiming to establish softer complexity guarantees that can interpolate between easy and hard problem instances. This will be achieved through a fine-grained characterization of broad classes of optimization problems, coupled with careful algorithmic design and rigorous analysis. These targeted problem classes hold not only fundamental significance but also manifest generically in resource allocation, threat detection, and the control of autonomous vehicles, all of which align closely with core areas of interest for AFOSR. As a result, the research stemming from this project possesses significant potential to advance the algorithmic landscape for these vital problem classes and to facilitate the deployment of relevant applications on a larger scale. The Principal Investigator has a proven track record in nonlinear optimization, having developed mathematical techniques and algorithms closely related to the central challenges addressed in this project.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 05, 2025
- Source ID
- FA95502410076
Entities
People
- Jelena Diakonikolas
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Wisconsin System