Grant: Discovery Grants Program - Individual
University of Waterloo
$41,000.00
Approximation Dichotomies in Continuous Optimization
FY 2024-25
Summary
This research program aims to further unify the theoretical landscape surrounding the approximability of continuous optimization problems. Many optimization problems of interest (both in theory and in practice) are NP-Hard to solve exactly, which motivates the study of algorithms producing approximately optimal solutions. This is a vast field of research and the study of efficient algorithms optimally approximating an optimization problem has led to substantial theories surrounding convex optimization and probabilistically checkable proofs (PCPs).
This theory has been very successful in determining optimal approximation algorithms for various classes of discrete optimization problems. Surprisingly, in many cases it has been established that a single generic algorithm obtains the optimal approximation factor for a wide class of discrete optimization tasks (under standard complexity theoretic assumptions). We aim to extend this beautiful theory to continuous optimization where methods from discrete optimization encounter severe limitations. Such a theory is necessary, as natural and fundamental problems in various areas (such as compressed sensing or machine learning) are inherently continuous in nature.
A key insight from some of my recent work is that approximability of continuous optimization often depends crucially on the geometry of the set being optimized over. This dependence has provided a link between continuous optimization and deep phenomena in convex geometry and functional analysis. In this research program we intend to focus on a rich subclass of continuous optimization, namely polynomial maximization over a convex set. For various choices of polynomials and convex sets, this class captures a vast array of continuous and discrete optimization problems spanning several disparate areas such as quantum information, machine learning, game theory, compressed sensing, constraint satisfaction, statistical physics, communication complexity, etc. Below is a sample of seemingly unrelated tasks captured by this framework illustrating the diverse nature of the problems it connects:
- Compressed Sensing: Find the sparsest vector in a subspace.
- Robust Principal Component Analysis: Find a subspace maximizing correlation with a given set of vectors.
- Quantum XOR Games: Two-player one-round game where the referee provides quantum states as questions.
- Graph Regularity: Partition a graph into pseudo-random pieces.
- Small-Set Expansion: Test if every sufficiently small set in a graph has many outgoing edges.
Some of the problems in this list are important from the algorithms perspective and some represent important bottlenecks in the field of hardness of approximation. Thus, a unified theory of approximability for this class promises to have broad scope and applicability and indeed this is the main thrust of the proposed research program. We will also investigate the possibility of a generic optimal approximation algorithm for this class.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2023-03599
Name nom
Bhattiprolu, Venkata Satya Purna Vijay
Department département
Combinatorics and Optimization Department
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
41000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Approximation Dichotomies in Continuous Optimization
Keywords
approximation algorithms; hardness of approximation; continuous optimization; polynomial optimization; convex optimization; convex geometry; functional analysis; high dimensional probability
Application summary
This research program aims to further unify the theoretical landscape surrounding the approximability of continuous optimization problems. Many optimization problems of interest (both in theory and in practice) are NP-Hard to solve exactly, which motivates the study of algorithms producing approximately optimal solutions. This is a vast field of research and the study of efficient algorithms optimally approximating an optimization problem has led to substantial theories surrounding convex optimization and probabilistically checkable proofs (PCPs).
This theory has been very successful in determining optimal approximation algorithms for various classes of discrete optimization problems. Surprisingly, in many cases it has been established that a single generic algorithm obtains the optimal approximation factor for a wide class of discrete optimization tasks (under standard complexity theoretic assumptions). We aim to extend this beautiful theory to continuous optimization where methods from discrete optimization encounter severe limitations. Such a theory is necessary, as natural and fundamental problems in various areas (such as compressed sensing or machine learning) are inherently continuous in nature.
A key insight from some of my recent work is that approximability of continuous optimization often depends crucially on the geometry of the set being optimized over. This dependence has provided a link between continuous optimization and deep phenomena in convex geometry and functional analysis. In this research program we intend to focus on a rich subclass of continuous optimization, namely polynomial maximization over a convex set. For various choices of polynomials and convex sets, this class captures a vast array of continuous and discrete optimization problems spanning several disparate areas such as quantum information, machine learning, game theory, compressed sensing, constraint satisfaction, statistical physics, communication complexity, etc. Below is a sample of seemingly unrelated tasks captured by this framework illustrating the diverse nature of the problems it connects:
- Compressed Sensing: Find the sparsest vector in a subspace.
- Robust Principal Component Analysis: Find a subspace maximizing correlation with a given set of vectors.
- Quantum XOR Games: Two-player one-round game where the referee provides quantum states as questions.
- Graph Regularity: Partition a graph into pseudo-random pieces.
- Small-Set Expansion: Test if every sufficiently small set in a graph has many outgoing edges.
Some of the problems in this list are important from the algorithms perspective and some represent important bottlenecks in the field of hardness of approximation. Thus, a unified theory of approximability for this class promises to have broad scope and applicability and indeed this is the main thrust of the proposed research program. We will also investigate the possibility of a generic optimal approximation algorithm for this class.