Fugu-MT 論文翻訳(概要): On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

論文の概要: On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

arxiv url: http://arxiv.org/abs/2402.16778v3
Date: Sun, 20 Oct 2024 17:58:11 GMT
ステータス: 翻訳完了
システム内更新日: 2024-10-22 13:13:07.356047
Title: On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective
Title（参考訳）: 差分的私的オンライン学習における誤りの生長について--境界の低い視点から
Authors: Daniil Dmitriev, Kristóf Szabó, Amartya Sanyal,
Abstract要約: 我々は、差分的プライベート(DP)オンライン学習アルゴリズムに対して、より低いバウンダリを提供する。我々の研究は、DP-オンライン学習の下位境界の設定に向けた最初の成果である。
参考スコア（独自算出の注目度）: 8.104151304193216
License:
Abstract: In this paper, we provide lower bounds for Differentially Private (DP) Online Learning algorithms. Our result shows that, for a broad class of $(\varepsilon,\delta)$-DP online algorithms, for number of rounds $T$ such that $\log T\leq O(1 / \delta)$, the expected number of mistakes incurred by the algorithm grows as $\Omega(\log \frac{T}{\delta})$. This matches the upper bound obtained by Golowich and Livni (2021) and is in contrast to non-private online learning where the number of mistakes is independent of $T$. To the best of our knowledge, our work is the first result towards settling lower bounds for DP-Online learning and partially addresses the open question in Sanyal and Ramponi (2022).
Abstract（参考訳）: 本稿では,差分的プライベート(DP)オンライン学習アルゴリズムの低限界について述べる。我々の結果は、幅広い種類の$(\varepsilon,\delta)$-DPオンラインアルゴリズムに対して、$\log T\leq O(1 / \delta)$が$\Omega(\log \frac{T}{\delta})$として増加することを示す。これは Golowich と Livni (2021) が獲得した上限値と一致する。我々の知識を最大限に活用するために、私たちの研究は、DP-Online学習の下位境界を確定する最初の結果であり、SanyalとRamponi(2022年)のオープンな問題に部分的に対処する。

関連論文リスト

Private Online Learning via Lazy Algorithms [52.772510023828744]
我々は,オンライン学習の問題,特に専門家によるオンライン予測(OPE)とオンライン凸最適化(OCO)について検討する。遅延オンライン学習アルゴリズムをプライベートアルゴリズムに変換する新しい変換を提案する。
論文参考訳（メタデータ） (2024-06-05T20:43:05Z)
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries [31.339322747660635]
我々は、$Omegaleft(minn,log Tright)$の新しい下限を示す。また、我々の低い境界は"オンラインしきい値問題"にまで拡張され、そこでは、多くの"量子クエリ"をプライベートに答えることが目標であることも示しています。
論文参考訳（メタデータ） (2024-02-28T16:45:54Z)
A Trichotomy for Transductive Online Learning [32.03948071550447]
我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
論文参考訳（メタデータ） (2023-11-10T23:27:23Z)
Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文参考訳（メタデータ） (2023-08-15T21:50:40Z)
Near-Optimal Differentially Private Reinforcement Learning [16.871660060209674]
差分プライバシー制約による強化学習におけるオンライン探索について検討する。共同微分プライバシ(JDP)と局所微分プライバシ(LDP)の下では、非回帰学習が可能であることが確立されている。我々は、情報理論上の非私的学習の下位境界に一致する$widetildeO(sqrtSAH2T+S2AH3/epsilon)$を後悔する$epsilon$-JDPアルゴリズムを設計する。
論文参考訳（メタデータ） (2022-12-09T06:03:02Z)
Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文参考訳（メタデータ） (2022-10-24T18:40:19Z)
Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes [78.27542864367821]
強化学習(RL)アルゴリズムは、ユーザのプライベートで機密性の高いデータに依存するパーソナライズされたサービスを提供するために使用することができる。ユーザのプライバシを保護するために、プライバシ保護RLアルゴリズムが要求されている。線形混合MDPと呼ばれるマルコフ決定過程(MDP)のクラスを学習するための新しい$(varepsilon, delta)$-LDPアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-10-19T17:44:09Z)
Littlestone Classes are Privately Online Learnable [28.04975353867202]
プライバシー制約下でのオンライン分類の問題点を考察する。この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
論文参考訳（メタデータ） (2021-06-25T09:08:33Z)
Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文参考訳（メタデータ） (2021-02-13T12:57:51Z)
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文参考訳（メタデータ） (2020-04-16T16:12:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。