Geometric Approaches to Near-Optimization
Abstract
Large-scale optimization is a workhorse of modern machine learning and statistics. Most computational techniques in these domains can be understood as optimizing some objective function over the parameters of a model. Optimization-based algorithmic techniques for data analysis have reached new heights of sophistication, coping with stochasticity, limited communication bandwidth, and hardware architectures to accelerate computation. A curious observation is that it is often unnecessary to find an accurate optimum during the minimization procedure to extract reasonable performance from a learned model. This suggests that the landscapes of objectives used to measure performance are inexact at best, and that there is a large region---or in the nonconvex regime multiple regions---of nearly-optimal points that may be acceptable for a given statistical task. Motivated by this observation, a reasonable twist on conventional optimization is to identify a collection of nearly-optimal points for a given minimization problem. There are many reasons to consider this task. On the one hand, optimization to an accurate minimum incurs unnecessary computational burden since the true minimizer does not necessarily yield the best performance anyway. On the other hand, understanding the space of near-optima may bring additional insight or opportunity for adjustment, e.g. by incorporating secondary criteria when choosing between near-optima or by characterizing a model s robustness. In this proposal, we consider the near-optimization problem from a geometric perspective. In particular, for real-valued optimization problems typical in statistical applications, we can think of the set of near-optima as cutting out a geometric region within the feasible domain for, whose shape describes the flexibility to adjust the solution an optimization problem without affecting the objective value significantly. Moreover, the image of this set under the objective function provides a second geometry in performance space relevant to multi-objective problems. Our proposal is centered around a few case study research problems designed to expose themes common to geometrically-structured near-optimization problems: TASK 1: Near-optimization in multi-objective problems TASK 2: Coreset-based near-optimization TASK 3: Near-optimization for infinite-dimensional problems The research will be led by Prof. Justin Solomon and members of the MIT Geometric Data Processing Group. Solomon received the Army Young Investigator Award in 2017 and is a well-recognized member of the machine learning, optimization, and applied geometry communities.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 09, 2020
- Source ID
- W911NF2010168
Entities
People
- Justin Solomon
Organizations
- Army Contracting Command
- Massachusetts Institute of Technology
- United States Army