Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy

Bingshan Hu, Nishant A. Mehta
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5330-5334, 2024.

Abstract

For the stochastic variant of decision-theoretic online learning with $K$ actions, $T$ rounds, and minimum gap $\Delta_{\min}$, the optimal, gap-dependent rate of the pseudo-regret is known to be $O \left( \frac{\log K}{\Delta_{\min}} \right)$. We ask to settle the optimal gap-dependent rate for the problem under $\varepsilon$-differential privacy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-hu24a, title = {Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy}, author = {Hu, Bingshan and Mehta, Nishant A.}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {5330--5334}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/hu24a/hu24a.pdf}, url = {https://proceedings.mlr.press/v247/hu24a.html}, abstract = {For the stochastic variant of decision-theoretic online learning with $K$ actions, $T$ rounds, and minimum gap $\Delta_{\min}$, the optimal, gap-dependent rate of the pseudo-regret is known to be $O \left( \frac{\log K}{\Delta_{\min}} \right)$. We ask to settle the optimal gap-dependent rate for the problem under $\varepsilon$-differential privacy.} }
Endnote
%0 Conference Paper %T Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy %A Bingshan Hu %A Nishant A. Mehta %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-hu24a %I PMLR %P 5330--5334 %U https://proceedings.mlr.press/v247/hu24a.html %V 247 %X For the stochastic variant of decision-theoretic online learning with $K$ actions, $T$ rounds, and minimum gap $\Delta_{\min}$, the optimal, gap-dependent rate of the pseudo-regret is known to be $O \left( \frac{\log K}{\Delta_{\min}} \right)$. We ask to settle the optimal gap-dependent rate for the problem under $\varepsilon$-differential privacy.
APA
Hu, B. & Mehta, N.A.. (2024). Open Problem: Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:5330-5334 Available from https://proceedings.mlr.press/v247/hu24a.html.

Related Material