• Home
  • Page : 'emploi' inconnue (menus.php)

Thesis : Online Computation with Machine-Learned Advice

PhD school thesis
The main objective in this project can be summarized as follows: Can we narrow the big gap between the advice-complexity model and the ML-prediction model? Can we obtain better online algorithms with predictions by combining, and extending techniques from both approaches?
Below we present some specific directions we will pursue with the PhD student.
  1. The price of erroneous advice. In our work [1] and [2] we studied advice in a setting in which it is either always correct, or always adversarially generated (informally: either provided by a friend or by an enemy). For this reason, some of the performance tradeoffs are only of theoretical significance. A more realistic model would allow for noisy advice (see [5] for a recent application in online financial optimization). This can be interpreted as using a number of noisy binary queries as predictions. There is a plethora of problems to be studied in this setting.
  2. Compact predictions and learnability. The ML-prediction framework so far has not placed any restrictions on the size of the advice, unlike the advice-complexity framework. However, there are situations in which some restriction is necessary in practice (e.g., in caching, we cannot afford too much time in gathering information). Thus, we would like to study time-sensitive problems and applications (e.g., caching and its generalizations) in a setting in which there is a prediction of small size. On the flip side, the advice-complexity framework does not consider the learnability of the advice, hence we would like to study the power and limitations of learnable advice.
  3. Combining advice from several experts. Here, we are interested in using potentially erroneous predictions that may originate from several sources (i.e., experts), instead of a single one. This was only recently explored in [13] for the ski rental problem, and the same question can be asked for many other online problems.
  4. Better tools for analysis of algorithms with predictions. The advice complexity field has introduced some powerful theoretical tools (e.g., the string guessing game [12]), which however are tailored to a setting in which the advice is error-free. We would like to extend them to a more general setting in which the advice is imperfect.
  5. The overall approach to these problems will involve two steps. The first is the theoretical analysis of the online algorithms and their limitations, from the point of view of both positive and negative (i.e., impossibility) results. The second step is the experimental validation of these algorithms.

    This PhD research project has been submitted for a funding request to “Ecole Doctorale d‘Informatique, Télécommunication et d‘Electronique (EDITE)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.

More details here

Contact :Spyros Angelopoulos, Christoph Dürr