Farkında olmayan, fark edilebilir rakipler altında, diferansiyel olarak özel çevrimiçi öğrenme ve çevrimiçi tahmin için hata sınırlarını inceliyoruz. Çevrimiçi öğrenme, öğrencinin her zaman adımında bir hipotez yayınlamasını gerektirirken, çevrimiçi tahminde öğrencinin bir hipotez yayınlamadan yalnızca tahminlerde bulunması gerekir. Özel çevrimiçi öğrenme için yeni bir alt sınır ve özel tahmin için bir üst sınır kullanarak, bu iki problemin örnek karmaşıklığının, $d$ sonlu Littlestone boyutunun her sınıfı için zaman ufku ile birlikte büyüyen bir faktörle ayrıldığını gösteriyoruz.
- Farkında olmayan, fark edilebilir rakipler altında, diferansiyel olarak özel çevrimiçi öğrenme ve çevrimiçi tahmin için hata sınırlarını inceliyoruz.
- Çevrimiçi öğrenme, öğrencinin her zaman adımında bir hipotez yayınlamasını gerektirirken, çevrimiçi tahminde öğrencinin bir hipotez yayınlamadan yalnızca tahminlerde bulunması gerekir.
- Özel çevrimiçi öğrenme için yeni bir alt sınır ve özel tahmin için bir üst sınır kullanarak, bu iki problemin örnek karmaşıklığının, $d$ sonlu Littlestone boyutunun her sınıfı için zaman ufku ile birlikte büyüyen bir faktörle ayrıldığını gösteriyoruz.
Farkında olmayan, fark edilebilir rakipler altında, diferansiyel olarak özel çevrimiçi öğrenme ve çevrimiçi tahmin için hata sınırlarını inceliyoruz.
02 Özet
Farkında olmayan, fark edilebilir rakipler altında, diferansiyel olarak özel çevrimiçi öğrenme ve çevrimiçi tahmin için hata sınırlarını inceliyoruz. Çevrimiçi öğrenme, öğrencinin her zaman adımında bir hipotez yayınlamasını gerektirirken, çevrimiçi tahminde öğrencinin bir hipotez yayınlamadan yalnızca tahminlerde bulunması gerekir. Özel çevrimiçi öğrenme için yeni bir alt sınır ve özel tahmin için bir üst sınır kullanarak, bu iki problemin örnek karmaşıklığının, $d$ sonlu Littlestone boyutunun her sınıfı için zaman ufku ile birlikte büyüyen bir faktörle ayrıldığını gösteriyoruz. İlk olarak, her $br{ε,δ}$-private çevrimiçi öğrenicinin, hata sınırının en az $bEbs{M_T}=Om{frac dεlogbr{ T}^{2/3}}$ olduğu, $T$ uzunluğunda deterministik gerçekleştirilebilir bir akışa sahip olduğunu kanıtlıyoruz. Özellikle bu, 1$/T aralığındaki ilk önemsiz olmayan düşük seviyedir.
Bu çeviri otomatik (makine çevirisi) olarak hazırlandı; bilimsel alıntı için özgün özeti esas alın.
We study mistake bounds for differentially private online learning and online prediction under oblivious realisable adversaries. Online learning requires the learner to release a hypothesis at each time step whereas in online prediction, the learner only needs to make predictions without releasing a hypothesis. Using a novel lower bound for private online learning and an upper bound for private prediction, we show that the sample complexity of these two problems are separated by a factor that grows with the time horizon for every class of finite Littlestone dimension $d$. First, we prove that every $br{ε,δ}$-private online learner has a deterministic realisable stream of length $T$ on which the mistake bound is at least $bEbs{M_T}=Om{frac dεlogbr{ T}^{2/3}}$. In particular, this is the first non-trivial lower in the range $1/T<δ0$. Thus, for every fixed class of finite Littlestone dimension when $δ=Θbr{1/log T}$, private learning requires $Om{br{log T}^{2/3}}$ expected mistakes, whereas private prediction admits $bigO{br{loglog T}^2}$.
03 PDF
Bu PDF başka bir sitede (arxiv.org) barındırılıyor ve sayfa içinde gösterilemiyor. Yukarıdaki düğmelerle yeni sekmede açabilir ya da indirebilirsiniz.
04 Kaynak göster
@article{sanyal2026private,
title = {Private online learning and prediction for Littlestone classes},
author = {Amartya Sanyal},
journal = {arXiv preprint arXiv:2610.06822},
year = {2026},
url = {https://arxiv.org/abs/2610.06822}
}
Sanyal, A. (2026). Littlestone sınıfları için özel çevrimiçi öğrenme ve tahmin. arXiv. https://arxiv.org/abs/2610.06822
Yorumlar 0
Henüz yorum yok. İlk yorumu siz yazın.
Yorum yazın