Data-Aware Guarantees for Mathematical Optimization and Learning
Abstract
The central idea of this proposal is to overcome the limitations of traditional mathematical optimization methods in producing high-,quality guarantees, with a focus on optimization problems of immense significance in data science, signal processing, machine learni,ng, and decision-making.Due to the intrinsic difficulties encountered in finding the global optima of non-convex optimization proble,ms, guaranteed approximation methods have been a long-standing component of the optimization literature. These traditional methods,however can only produce fixed optimality guarantees that therefore do not tap into the significant potential of data to aid in enha,ncing such guarantees. This shortcoming will be addressed in this project by proposing a novel paradigm which exploits the data and,thus provides data-dependent optimality guarantees that outperform their traditional counterparts. We note that the solutions obtain,ed from optimization methods have been widely observed to possess considerably better quality compared with what is guaranteed--- in,deed, for some practical applications, the global solution is in reach. At the same time, such a priori guarantees may not be improv,able as they need to account for worst-case scenarios. To achieve the proposed objectives, this research will focus on developing a,nd studying optimization frameworks capable of producing a posteriori guarantees that are data-dependent---in the sense that the gua,rantees are produced through the optimization (process on the data), and not before.The data (or problem instance) dependent nature,of a posteriori guarantees paves the way for improved guarantees that can be offered as trust certificates along with the obtained a,pproximate solutions. In fact, it was recently shown by the PI that such a posteriori guarantees typically outperform the currently, known a priori guarantees of widely used optimization techniques such as semidefinite relaxation. As a result, the emergence of suc,h guarantees can begame-changing as it lays the ground for a new set of applications, including e.g., machines that can understand h,ow much they can trust their inference depending on the situation/environment, or confident decision-making in operations that are a,zation paradigm developed by the PI that aims to successively approximate the problem instance and the global optimum of interest v,ia a sequence of problem instances whose corresponding global optima are readily known. In light of such recent advances, the goals,of this project are to: - Investigate novel data-dependent guarantees for optimization problems of importance in data science, signa,l processing, machine learning, and decision-making.- Develop and investigate the data-dependent guarantee producing methods based o,n MERIT and other creative ideas that are expected to emerge, and derive the theoretical limits, complexity bounds, and quantifiabl,e assurances in connection with the data-aware guarantees that will be offered.- Investigate the implications of the provided guaran,tees in machine learning, reasoning, and decision-making.The defining attribute of future naval forces is speed and accuracy, not on,ly in operations, but also in decision-making. Adva,ruptive---however, they also offer significant advantages. Owing to its transformative nature, the project is envisioned to have a,significant impact on the theory and practice of mathematical optimization in data science, signal processing, control, computing, a,nd confident decision-making, and is of direct relevance to navy research and development priorities.[Approved for Public Release]
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212666
Entities
People
- Mojtaba Soltanalian
Organizations
- Office of Naval Research
- United States Navy
- University of Illinois Urbana–Champaign