Optimizing in the dark: Learning an optimal solution through a simple request interface

Qiao Xiang, Haitao Yu, James Aspnes, Franck Le, Linghe Kong, and Y. Richard Yang. Optimizing in the dark: Learning an optimal solution through a simple request interface. IEEE/ACM Transactions on Networking, 29(2):571–584, April 2021. An earlier version appeared in Thirty-Third AAAI Conference on Artificial Intelligence, January 2019, pp. 1674–1681.

Abstract

Network resource reservation systems are being developed and deployed, driven by the demand and substantial benefits of providing performance predictability for modern distributed applications. However, existing systems suffer limitations: They either are inefficient in finding the optimal resource reservation, or cause private information (e.g., from the network infrastructure) to be exposed (e.g., to the user). In this paper, we design BoxOpt, a novel system that leverages efficient oracle construction techniques in optimization and learning theory to automatically, and swiftly learn the optimal resource reservations without exchanging any private information between the network and the user. We implement a prototype of BoxOpt and demonstrate its efficiency and efficacy via extensive experiments using real network topology and trace. Results show that (1) BoxOpt has a 100% correctness ratio, and (2) for 95% of requests, BoxOpt learns the optimal resource reservation within 13 seconds.

BibTeX

Download
@article{XiangYALKY2019,
author    = {Xiang, Qiao and Yu, Haitao and Aspnes, James and Le, Franck and Kong, Linghe and Yang, Y. Richard},
title     = {Optimizing in the Dark: Learning an Optimal Solution Through a Simple Interface},
  month = apr,
  year = 2021,
  journal={IEEE/ACM Transactions on Networking},
  volume=29,
  number=2,
    pages={571--584}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page