{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:07Z","timestamp":1750219747237,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>Traditionally, computer systems are designed to optimize classic notions of performance such as flow completion time, cost, etc. The system performance is then typically evaluated by characterizing theoretical bounds in worst-case settings over a single performance metric. In the next generation of computer systems, societal design criteria, such as carbon awareness and fairness, becomes a first-class design goal. However, the classic performance metrics may conflict with societal criteria. Foundational understanding and performance evaluations of systems with these inherent trade-offs lead to novel research questions that could be considered new educational components for performance analysis courses. The classic techniques, e.g., worst-case analysis, for systems with conflicting objectives may lead to the impossibility of results. However, a foundational understanding of the impossibility of results calls for new techniques and tools. In traditional performance evaluation, to understand the foundational limits, typically, it is sufficient to derive lower-bound arguments in worst-case settings. In the new era of system design, lower bounds are inherently about trade-offs between different objectives. Characterizing these trade-offs in settings with multiple design criteria is closer to the notion of Pareto-optimality, which is drastically different from classic lower bounds. With the impossibility of results using classic paradigms, one possible direction is to (re)design systems following the emerging direction of learning-augmented algorithms. With this approach, it might be possible to remove\/mitigate the foundational conflict between classic vs. societal metrics using the right predictions. However, the performance evaluation of learning-augmented algorithms calls for a new set of technical questions, which we highlight in this paper.<\/jats:p>","DOI":"10.1145\/3626570.3626590","type":"journal-article","created":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T22:16:57Z","timestamp":1696285017000},"page":"53-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Trade-off Analysis in Learning-augmented Algorithms with Societal Design Criteria"],"prefix":"10.1145","volume":"51","author":[{"given":"Mohammad H.","family":"Hajiesmaili","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,2]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"566","volume-title":"Budget constrained bidding in keyword auctions and online knapsack problems,\" in Proc. of WINE","author":"Zhou Y.","year":"2008","unstructured":"Y. Zhou, D. Chakrabarty, and R. Lukose, \"Budget constrained bidding in keyword auctions and online knapsack problems,\" in Proc. of WINE, pp. 566--576, 2008."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3492854"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447375"},{"key":"e_1_2_1_4_1","volume-title":"Time fairness in online knapsack problems,\" arXiv preprint arXiv:2305.13293","author":"Lechowicz A.","year":"2023","unstructured":"A. Lechowicz, R. Sengupta, B. Sun, S. Kamali, and M. Hajiesmaili, \"Time fairness in online knapsack problems,\" arXiv preprint arXiv:2305.13293, 2023."},{"key":"e_1_2_1_5_1","volume-title":"The war of the efficiencies: Understanding the tension between carbon and energy optimization,\" in The 2nd Workshop on Sustainable Computer Systems (HotCarbon'23)","author":"Hanafy W. A.","year":"2023","unstructured":"W. A. Hanafy, R. Bostandoost, N. Bashir, D. Irwin, M. Hajiesmaili, and P. Shenoy, \"The war of the efficiencies: Understanding the tension between carbon and energy optimization,\" in The 2nd Workshop on Sustainable Computer Systems (HotCarbon'23), 2023."},{"key":"e_1_2_1_6_1","volume-title":"The online pause and resume problem: Optimal algorithms and an application to carbon-aware load shifting,\" arXiv preprint arXiv:2303.17551","author":"Lechowicz A.","year":"2023","unstructured":"A. Lechowicz, N. Christianson, J. Zuo, N. Bashir, M. Hajiesmaili, A. Wierman, and P. Shenoy, \"The online pause and resume problem: Optimal algorithms and an application to carbon-aware load shifting,\" arXiv preprint arXiv:2303.17551, 2023."},{"key":"e_1_2_1_7_1","first-page":"19943","article-title":"Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm","volume":"33","author":"Yang L.","year":"2020","unstructured":"L. Yang, M. Hajiesmaili, M. S. Talebi, J. Lui, W. S. Wong, et al., \"Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm,\" Advances in Neural Information Processing Systems, vol. 33, pp. 19943--19952, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"T. Lykouris V. Mirrokni and R. Paes Leme \"Stochastic bandits robust to adversarial corruptions \" in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing pp. 114--122 2018.","DOI":"10.1145\/3188745.3188918"},{"key":"e_1_2_1_9_1","volume-title":"PMLR","author":"Gupta A.","year":"2019","unstructured":"A. Gupta, T. Koren, and K. Talwar, \"Better algorithms for stochastic bandits with adversarial corruptions,\" in Conference on Learning Theory, pp. 1562--1578, PMLR, 2019."},{"key":"e_1_2_1_10_1","volume-title":"Group fairness in dynamic refugee assignment,\" arXiv preprint arXiv:2301.10642","author":"Freund D.","year":"2023","unstructured":"D. Freund, T. Lykouris, E. Paulson, B. Sturt, and W. Weng, \"Group fairness in dynamic refugee assignment,\" arXiv preprint arXiv:2301.10642, 2023."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547353.3526951"},{"key":"e_1_2_1_12_1","unstructured":"T. Lykouris and S. Vassilvtiskii \"Competitive caching with machine learned advice \" in Proceedings of the 35th International Conference on Machine Learning (J. Dy and A. Krause eds.) vol. 80 of Proceedings of Machine Learning Research pp. 3296--3305 PMLR 10--15 Jul 2018."},{"volume-title":"Improving online algorithms via ml predictions,\" in Advances in Neural Information Processing Systems","author":"Purohit M.","key":"e_1_2_1_13_1","unstructured":"M. Purohit, Z. Svitkina, and R. Kumar, \"Improving online algorithms via ml predictions,\" in Advances in Neural Information Processing Systems (S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds.), vol. 31,"},{"key":"e_1_2_1_14_1","first-page":"8042","article-title":"Optimal robustness-consistency trade-offs for learning-augmented online algorithms","volume":"33","author":"Wei A.","year":"2020","unstructured":"A. Wei and F. Zhang, \"Optimal robustness-consistency trade-offs for learning-augmented online algorithms,\" Advances in Neural Information Processing Systems, vol. 33, pp. 8042--8053, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_15_1","volume-title":"Online peak-aware energy scheduling with untrusted advice,\" in Proc. of ACM -e-Energy","author":"Lee R.","year":"2021","unstructured":"R. Lee, J. Maghakian, M. Hajiesmaili, J. Li, R. Sitaraman, and Z. Liu, \"Online peak-aware energy scheduling with untrusted advice,\" in Proc. of ACM -e-Energy, 2021."},{"key":"e_1_2_1_16_1","volume-title":"Learning augmented online facility location,\" arXiv preprint arXiv:2107.08277","author":"Fotakis D.","year":"2021","unstructured":"D. Fotakis, E. Gergatsouli, T. Gouleakis, and N. Patris, \"Learning augmented online facility location,\" arXiv preprint arXiv:2107.08277, 2021."},{"key":"e_1_2_1_17_1","volume-title":"Online facility location with predictions,\" in International Conference on Learning Representations","author":"Jiang S. H.-C.","year":"2021","unstructured":"S. H.-C. Jiang, E. Liu, Y. Lyu, Z. G. Tang, and Y. Zhang, \"Online facility location with predictions,\" in International Conference on Learning Representations, 2021."},{"key":"e_1_2_1_18_1","first-page":"7933","article-title":"Secretary and online matching problems with machine learned advice","volume":"33","author":"Antoniadis A.","year":"2020","unstructured":"A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev, \"Secretary and online matching problems with machine learned advice,\" Advances in Neural Information Processing Systems, vol. 33, pp. 7933--7944, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_19_1","volume-title":"PMLR","author":"Antoniadis A.","year":"2020","unstructured":"A. Antoniadis, C. Coester, M. Elias, A. Polak, and B. Simon, \"Online metric algorithms with untrusted predictions,\" in International Conference on Machine Learning, pp. 345--355, PMLR, 2020."},{"key":"e_1_2_1_20_1","volume-title":"Online bin packing with predictions,\" in Proc. of IJCAI","author":"Angelopoulos S.","year":"2022","unstructured":"S. Angelopoulos, S. Kamali, and K. Shadkami, \"Online bin packing with predictions,\" in Proc. of IJCAI, 2022."},{"key":"e_1_2_1_21_1","volume-title":"Pareto-optimal learning-augmented algorithms for online conversion problems,\" in Advances in Neural Information Processing Systems","author":"Sun B.","year":"2021","unstructured":"B. Sun, R. Lee, M. Hajiesmaili, A. Wierman, and D. Tsang, \"Pareto-optimal learning-augmented algorithms for online conversion problems,\" in Advances in Neural Information Processing Systems, vol. 34, 2021."},{"key":"e_1_2_1_22_1","volume-title":"Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model,\" arXiv preprint arXiv:2206.11397","author":"Jin B.","year":"2022","unstructured":"B. Jin and W. Ma, \"Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model,\" arXiv preprint arXiv:2206.11397, 2022."},{"key":"e_1_2_1_23_1","first-page":"244","volume-title":"Competitive snoopy caching,\" in Proc. of IEEE FOCS","author":"Karlin A. R.","year":"1986","unstructured":"A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator, \"Competitive snoopy caching,\" in Proc. of IEEE FOCS, pp. 244--254, 1986."},{"key":"e_1_2_1_24_1","volume-title":"Online computation and competitive analysis. cambridge university press","author":"Borodin A.","year":"2005","unstructured":"A. Borodin and R. El-Yaniv, Online computation and competitive analysis. cambridge university press, 2005."},{"key":"e_1_2_1_25_1","first-page":"502","article-title":"Dynamic TCP acknowledgement and other stories about e\/(e-1)","author":"Karlin A. R.","year":"2001","unstructured":"A. R. Karlin, C. Kenyon, and D. Randall, \"Dynamic TCP acknowledgement and other stories about e\/(e-1),\" in Proc. of ACM STOC, pp. 502--509, 2001.","journal-title":"Proc. of ACM STOC"},{"key":"e_1_2_1_26_1","unstructured":"Z. Zhang Z. Li and C. Wu \"Optimal posted prices for online cloud resource allocation \" in Proc. of ACM SIGMETRICS."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2226216"},{"key":"e_1_2_1_28_1","volume-title":"Online linear optimization with inventory management constraints,\" Proc. of ACM SIGMETRICS","author":"Yang L.","year":"2020","unstructured":"L. Yang, M. H. Hajiesmaili, R. Sitaraman, A. Wierman, E. Mallada, and W. S. Wong, \"Online linear optimization with inventory management constraints,\" Proc. of ACM SIGMETRICS, 2020."},{"key":"e_1_2_1_29_1","volume-title":"ACM SIGMETRICS","author":"Yang L.","year":"2017","unstructured":"L. Yang, M. H. Hajiesmaili, H. Yi, and M. Chen, \"Hour-ahead offering strategies in electricity market for power producers with storage and intermittent supply,\" in Proc of. ACM SIGMETRICS, 2017."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2016.2551282"},{"key":"e_1_2_1_31_1","volume-title":"Competitive online scheduling algorithms with applications in deadline-constrained EV charging,\" in Proc. of IEEE\/ACM IWQoS","author":"Alinai B.","year":"2018","unstructured":"B. Alinai, M. S. Talebi, M. H. Hajiesmaili, A. Yekkehkhany, and N. Crespi, \"Competitive online scheduling algorithms with applications in deadline-constrained EV charging,\" in Proc. of IEEE\/ACM IWQoS, 2018."},{"key":"e_1_2_1_32_1","article-title":"Online EV scheduling algorithms for adaptive charging networks with global peak constraints","author":"Alinia B.","year":"2020","unstructured":"B. Alinia, M. H. Hajiesmaili, Z. J. Lee, N. Crespi, and E. Mallada, \"Online EV scheduling algorithms for adaptive charging networks with global peak constraints,\" IEEE Transactions on Sustainable Computing, 2020.","journal-title":"IEEE Transactions on Sustainable Computing"},{"key":"e_1_2_1_33_1","volume-title":"ACM SIGMETRICS","author":"Yang L.","year":"2018","unstructured":"L. Yang, W. S. Wong, and M. H. Hajiesmaili, \"An optimal randomized online algorithm for QoS buffer management,\" in Proc. ACM SIGMETRICS, 2018."},{"key":"e_1_2_1_34_1","volume-title":"Near-optimal online algorithms for joint pricing and scheduling in ev charging networks,\" in Proc. of ACM e-Energy","author":"Bostandoost R.","year":"2023","unstructured":"R. Bostandoost, B. Sun, C. Joe-Wong, and M. Hajiesmaili, \"Near-optimal online algorithms for joint pricing and scheduling in ev charging networks,\" in Proc. of ACM e-Energy, 2023."},{"key":"e_1_2_1_35_1","volume-title":"Using the multiple knapsack problem to model the problem of virtual machine allocation in cloud computing,\" in Proc. of IEEE CSE","author":"Amarante S. R. M.","year":"2013","unstructured":"S. R. M. Amarante, F. M. Roberto, A. R. Cardoso, and J. Celestino, \"Using the multiple knapsack problem to model the problem of virtual machine allocation in cloud computing,\" in Proc. of IEEE CSE, 2013."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2619743"},{"issue":"2","key":"e_1_2_1_37_1","first-page":"3","article-title":"The design of competitive online algorithms via a primal--dual approach","volume":"3","author":"Buchbinder N.","year":"2009","unstructured":"N. Buchbinder and J. S. Naor, \"The design of competitive online algorithms via a primal--dual approach,\" Foundations and Trends\u00ae in Theoretical Computer Science, vol. 3, no. 2--3, pp. 93--263, 2009.","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"e_1_2_1_38_1","volume-title":"Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging,\" Proc. of ACM SIGMETRICS","author":"Sun B.","year":"2021","unstructured":"B. Sun, A. Zeynali, T. Li, M. Hajiesmaili, A. Wierman, and D. H. Tsang, \"Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging,\" Proc. of ACM SIGMETRICS, 2021."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i12.17294"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9217-8"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_44_1","volume-title":"Individual fairness in prophet inequalities,\" in Proc. of ACM EC","author":"Arsenis M.","year":"2022","unstructured":"M. Arsenis and R. Kleinberg, \"Individual fairness in prophet inequalities,\" in Proc. of ACM EC, 2022"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626570.3626590","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626570.3626590","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:45Z","timestamp":1750178205000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626570.3626590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,9,28]]}},"alternative-id":["10.1145\/3626570.3626590"],"URL":"https:\/\/doi.org\/10.1145\/3626570.3626590","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2023,9,28]]},"assertion":[{"value":"2023-10-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}