The online optimization paradigm deals with optimization as a process: an online decision maker (or player) iteratively makes a decision, at each time unit, based on the past history; at the time of each decision, the outcomes associated with the choices are unknown to the player. After committing to a decision, the decision maker suffers a loss. The losses imposed do not necessarily follow a pattern (known or unknown, statistical or other), and can be adversarially chosen.This robust framework allows for online optimization to address highly complex dynamical settings with time varying elements, that the classical (offline) mathematical optimization is unable to capture. Examples of online non-convex problems are ubiquitous in theoretical computer science, operations research, industrial engineering, and many other fields where online decision-making is the norm. However, there is yet no clear methodology, nor well-based algorithmic frameworks, to address non-convex online problems. This project’s goal is to develop a methodology and applicable algorithms to handle online non-convex models.
Many contemporary problems involve data matrices that are too large to store or fully access during an optimization procedure. This project aims to develop optimization algorithms which use matrix approximations, also known as sketches, in the optimization procedure as data or as the decision variables, with theoretical guarantees.
