Optimal No-Regret Learning for One-Sided Lipschitz Functions

Paul Duetting, Guru Guruganesh, Jon Schneider, Joshua Ruizhi Wang
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:8836-8850, 2023.

Abstract

Inspired by applications in pricing and contract design, we study the maximization of one-sided Lipschitz functions, which only provide the (weaker) guarantee that they do not grow too quickly in one direction. We show that it is possible to learn a maximizer for such a function while incurring $O(\log \log T)$ total regret (with a universal constant independent of the number of discontinuities / complexity of the function). This regret bound is asymptotically optimal in $T$ due to a lower bound of Kleinberg and Leighton. By applying this algorithm, we show that one can sell digital goods to multiple buyers and learn the optimal linear contract in the principal-agent setting while incurring at most $O(\log \log T)$ regret.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-duetting23b, title = {Optimal No-Regret Learning for One-Sided {L}ipschitz Functions}, author = {Duetting, Paul and Guruganesh, Guru and Schneider, Jon and Wang, Joshua Ruizhi}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {8836--8850}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/duetting23b/duetting23b.pdf}, url = {https://proceedings.mlr.press/v202/duetting23b.html}, abstract = {Inspired by applications in pricing and contract design, we study the maximization of one-sided Lipschitz functions, which only provide the (weaker) guarantee that they do not grow too quickly in one direction. We show that it is possible to learn a maximizer for such a function while incurring $O(\log \log T)$ total regret (with a universal constant independent of the number of discontinuities / complexity of the function). This regret bound is asymptotically optimal in $T$ due to a lower bound of Kleinberg and Leighton. By applying this algorithm, we show that one can sell digital goods to multiple buyers and learn the optimal linear contract in the principal-agent setting while incurring at most $O(\log \log T)$ regret.} }
Endnote
%0 Conference Paper %T Optimal No-Regret Learning for One-Sided Lipschitz Functions %A Paul Duetting %A Guru Guruganesh %A Jon Schneider %A Joshua Ruizhi Wang %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-duetting23b %I PMLR %P 8836--8850 %U https://proceedings.mlr.press/v202/duetting23b.html %V 202 %X Inspired by applications in pricing and contract design, we study the maximization of one-sided Lipschitz functions, which only provide the (weaker) guarantee that they do not grow too quickly in one direction. We show that it is possible to learn a maximizer for such a function while incurring $O(\log \log T)$ total regret (with a universal constant independent of the number of discontinuities / complexity of the function). This regret bound is asymptotically optimal in $T$ due to a lower bound of Kleinberg and Leighton. By applying this algorithm, we show that one can sell digital goods to multiple buyers and learn the optimal linear contract in the principal-agent setting while incurring at most $O(\log \log T)$ regret.
APA
Duetting, P., Guruganesh, G., Schneider, J. & Wang, J.R.. (2023). Optimal No-Regret Learning for One-Sided Lipschitz Functions. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:8836-8850 Available from https://proceedings.mlr.press/v202/duetting23b.html.

Related Material