Online Optimization and Learning under Uncertainty
Abstract
ONLINE OPTIMIZATION AND LEARNING UNDER UNCERTAINTY Patrick Jaillet, MIT ONR Renewal Proposal Federal Identi er: N00014-12-1-0033 Agency Routing Number: 311 [Wagner, Donald] Project Summary Technical advances in computing, telecommunication, sensing capabilities, and other infor- mation technologies provide tremendous opportunities to use dynamic information in order to enhance productivity, optimize performance, and solve new complex online problems of great practical interests. The main focus of this research is on the fundamental aspects of decision making in the context of uncertain (and possibly large) data sets revealed in an online fashion. More speci cally, we are interested in the interplay of four main phenomena (incomplete and uncertain data, online decisions, online learning, and large data sets), and the corresponding fundamental questions when facing a problem exhibiting one or several of these phenomena: (i) how to properly model and quantify the degree of uncertainty in such a problem, and its impact on our ability to solve" it, (ii) how to quantify the value of additional (deterministic and/or probabilistic) information for solving such a problem, (iii) how to simultaneously optimize and learn in an online environment under uncertainty, and (iv) how to design provably good algorithms for such problems. In our current ONR research grant N00014-12-1-0033 (Online and Dynamic Optimiza- tion Problems Under Uncertainty"), we have concentrated our e orts on basic canonical online optimization problems, dealing with (i) online versions of the traveling salesman prob- lem (TSP), (ii) online versions of the bipartite matching problem (and its generalization to various weighted cases), (iii) online matroid selection problems, and (iv) general online linear programming problems. There are many open and fundamental questions in our long-term research agenda which have yet to be fully addressed and understood. In particular, in this renewal, we propose to continue to address previous themes such as (a) the impact of limited access to past information; (b) the proper inclusion of stochastic information in a robust way, and (c) the value of additional information. Some new important research questions have surfaced during this past investigation and one of the main focus for this renewal will be an attempt to fully integrate online optimization with online learning. In this proposal, we propose to address all these questions for our previous basic canonical models and their variations, as well as for two new classes of models well suited for integrating the online learning aspects. 1
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512083
Entities
People
- Patrick Jaillet
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy