論文の概要: Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning
- arxiv url: http://arxiv.org/abs/2605.29148v1
- Date: Wed, 27 May 2026 22:17:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-30 02:45:55.543898
- Title: Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning
- Title（参考訳）: 個人確率決定理論オンライン学習のための最適ギャップ依存レグレット
- Authors: Tommaso Cesari, Roberto Colomboni,
- Abstract要約: 我々は、完全な情報とイベントレベルの純粋差分プライバシーを用いて決定論的オンライン学習を研究する。
HuとMehtaのCOLTオープンな問題は、決定論的オンライン学習において最適なギャップ依存の後悔率を決定することを要求する。
- 参考スコア（独自算出の注目度）: 10.610898393214175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic decision-theoretic online learning with full information and event-level pure differential privacy. A COLT open problem of Hu and Mehta asks to determine the optimal gap-dependent regret rate for stochastic decision-theoretic online learning under pure event-level differential privacy. For $K$ actions, losses in $[0,1]$, and a unique best action separated from the second-best action by gap $Δ_{\min}$, the known lower bound is of order $ \frac{\log K}{\min\{Δ_{\min},\varepsilon\}}, $ or equivalently, up to universal constants, of order \[ \frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}. \] We give a horizon-free pure-DP algorithm and prove the explicit regret bound \[ \operatorname{Reg}_T \le 1000 \cdot \left(\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}\right) \] for every horizon $T$. The numerical constant is not optimized. The algorithm partitions time into blocks of exponentially increasing size, plays a single action throughout each block, and chooses the next action by an exponential mechanism applied to a data-independent random prefix of the previous block. The random prefix converts block regret into a sum, over all prefix lengths, of softmax selection errors. A single entropy-potential argument controls all privacy-dominated large-gap actions at cost $\log K/\varepsilon$.
- Abstract（参考訳）: 確率的決定論的オンライン学習を、完全な情報とイベントレベルの純粋差分プライバシーを用いて研究する。
HuとMehtaのCOLTのオープンな問題は、純粋なイベントレベルの差分プライバシーの下で確率論的決定論的オンライン学習のための最適ギャップ依存の後悔率を決定することを求めている。
K$アクションの場合、$[0,1]$の損失と、ギャップ$Δ_{\min}$によって第二のベストアクションから分離されたユニークなベストアクションは、既知の下限は次数$$ \frac{\log K}{\min\{Δ_{\min},\varepsilon\}}、$または同等に、次数$[ \frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon} である。
\] 地平線フリーの純DPアルゴリズムを与え、すべての地平線$T$に対して明示的後悔境界 \[ \operatorname{Reg}_T \le 1000 \cdot \left(\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}\right) \] を証明する。
数値定数は最適化されていない。
このアルゴリズムは、時間を指数関数的に増大するブロックに分割し、各ブロックを通して単一のアクションを再生し、前のブロックのデータ非依存のランダムプレフィックスに適用される指数的なメカニズムにより次のアクションを選択する。
ランダムプレフィックスはブロック後悔をソフトマックス選択誤差のすべてのプレフィックス長の和に変換する。
単一のエントロピーポテンシャル引数は、プライバシが支配するすべての大きなギャップアクションをコスト$\log K/\varepsilon$で制御する。
関連論文リスト
- Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy [17.711455925206298]
HuとMehta(2024年)は、オープンな問題を提起した:$varepsilon$-differential privacyの下で、決定論的オンライン学習($K$アクションと$T$ラウンドを含む)の最適なインスタンス依存率は何ですか?
論文 参考訳（メタデータ） (2025-02-16T05:13:51Z) - Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。
各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。
目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
ユーザ好みでアクティブな学習を行うための,最初の微分プライベートなダリング帯域幅アルゴリズムを提案する。
我々のアルゴリズムは、ほぼ最適性能で計算効率が良い。
我々は結果を任意の一般的な決定空間に拡張し、潜在的に無限の腕を持つ$d$次元を持つ。
論文 参考訳（メタデータ） (2024-03-22T09:02:12Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-10-24T18:40:19Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。
差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。
同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文 参考訳（メタデータ） (2021-02-16T02:48:16Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。