Optimizing in the Dark: Learning an Optimal Solution through a Simple Request Interface


  • Qiao Xiang Yale University
  • Haitao Yu Tongji University
  • James Aspnes Yale University
  • Franck Le IBM T.J. Watson Research Center
  • Linghe Kong Shanghai Jiao Tong University
  • Y. Richard Yang Yale University




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.




How to Cite

Xiang, Q., Yu, H., Aspnes, J., Le, F., Kong, L., & Yang, Y. R. (2019). Optimizing in the Dark: Learning an Optimal Solution through a Simple Request Interface. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1674-1681. https://doi.org/10.1609/aaai.v33i01.33011674



AAAI Technical Track: Constraint Satisfaction and Optimization