On Some Fundamental Tradeoffs in Optimization
Abstract
Project Summary (approved for public release)The main focus of this research is to address some fundamental tradeoffs concerning twodifferent settings and classes of problems arising in optimization.In the first setting, we consider the canonical problem of first-order convex optimizationin which one aims to minimize a function with access to an oracle which, for any querypoint, returns the value and a subgradient of the function at that point. Arguably, thisis one of the most fundamental problems in optimization, mathematical programming, andmachine learning. A classical question is how many oracle queries are required to guaranteefinding an epsilon-approximate minimizer for such functions. We propose to fully analyzethe theoretical trade-offs between query complexity and memory requirement for convexoptimization and its related feasibility problem, considering both non-smooth and smoothfunctions. In addition, we are proposing to investigate similar possible tradeoffs betweenquery complexity and memory requirement for the problem of first-order minimax (convexconcave)optimization, an equally fundamental problem in optimization, game theory, andmachine learning.In the second setting, we consider canonical online optimization problems where inputinformation is revealed sequentially, and a decision maker must make irrevocable decisionsat each time period. Using either competitive ratio or regret as a measure of algorithmicperformance, many positive and impressive results have been obtained on a wide range ofsuch problems. However, a critical assumption behindthese results is that the numberof decisions to be made (that is, the total number of arrivals, or the time horizon of theproblem),must be known a priori. In many applications, however, this is far from beingrealistic. We propose to explore what can and cannot be provably obtained algorithmicallywhen we don#t assume anymore a priori knowledge about an exact value for the time horizon.We propose to consider manycases, including when the time horizon is chosen adversarially,or when it is a random variable, whose distribution is either (i) fully known, (ii) partiallyknown, or (iii) learnable from oracle queries. For the latter case, we are interested inexploringthe tradeoffs (Pareto frontier) between sampling query complexity and achievable onlinealgorithm performances.Solving fundamental optimization problems to acceptable accuracies under various computationalconstraints, and online optimization problems under uncertainty are fundamentalbuilding blocks to successfully address key operational and strategic decision making of navalrelevance. Future needs will only increase in complexity due to the need to process efficientlytremendous amount of input data, sometimes generated in a noisy and/or adversarial way,and to do so with practical computational memory. Establishing fundamental tradeoffs ofwhatcan be achieved under such settings is a key component of this research.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 08, 2024
- Source ID
- N000142412470
Entities
People
- Patrick Jaillet
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy