Large-scale optimization in the interpolation regime- theory and algorithms
Abstract
Contemporary tasks in data science and engineering crucially rely on solving challenging large-scale optimization problems. Historically, the algorithmic approaches to an optimization problem were strongly influenced by whether it was convex - a basic property ensuring that local and global minima coincide. Convex problems have traditionally been deemed tractable by efficient algorithms while nonconvex problems were seen as solvable primarily through local search heuristics. As engineering and the domain sciences have evolved, so has the nature of problems. Increasingly, nonconvex problems, arising in domains like control, signal processing, and machine learning, are being effectively solved using simple derivative-based algorithms, thereby challenging traditional beliefs. A significant recent revelation in this regard is that typical non-convex problems satisfy a nondegeneracy condition called the Polyak-Lojasiewicz (PL) inequality. This condition has deep historical roots and allows to develop fast algorithms for a large class of nonconvex problems. The PL condition is particularly potent for so-called interpolation problems, wherein minimizers attain zero loss across every data point. Such problems have become common-place, especially in deep learning (e.g. self-driving cars, chatbots) and structured signal recovery (e.g. imaging, genome sequencing).
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 06, 2025
- Source ID
- FA95502410092
Entities
People
- Dmitriy Drusvyatskiy
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Washington