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

Bingshan Hu; Nishant A. Mehta

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

Download PDF