Fugu-MT 論文翻訳(概要): Private Prediction via Shrinkage

論文の概要: Private Prediction via Shrinkage

arxiv url: http://arxiv.org/abs/2602.05219v1
Date: Thu, 05 Feb 2026 02:17:48 GMT
ステータス: 翻訳完了
システム内更新日: 2026-02-06 18:49:08.71932
Title: Private Prediction via Shrinkage
Title（参考訳）: 収縮による私的予測
Authors: Chao Yan,
Abstract要約: Dwork と Feldman が導入した差分プライベート予測について検討する。標準構成は$T$クエリに対する$sqrtT$依存性をもたらす。ストリーミング設定において,この依存度をT$でポリ対数に還元できることが示される。
参考スコア（独自算出の注目度）: 5.420775647357814
License: http://creativecommons.org/publicdomain/zero/1.0/
Abstract: We study differentially private prediction introduced by Dwork and Feldman (COLT 2018): an algorithm receives one labeled sample set $S$ and then answers a stream of unlabeled queries while the output transcript remains $(\varepsilon,δ)$-differentially private with respect to $S$. Standard composition yields a $\sqrt{T}$ dependence for $T$ queries. We show that this dependence can be reduced to polylogarithmic in $T$ in streaming settings. For an oblivious online adversary and any concept class $\mathcal{C}$, we give a private predictor that answers $T$ queries with $|S|= \tilde{O}(VC(\mathcal{C})^{3.5}\log^{3.5}T)$ labeled examples. For an adaptive online adversary and halfspaces over $\mathbb{R}^d$, we obtain $|S|=\tilde{O}\left(d^{5.5}\log T\right)$.
Abstract（参考訳）: Dwork と Feldman (COLT 2018): 1つのラベル付きサンプルセット $S$ を受け取り、出力書き起こしが $(\varepsilon,δ)$-differentially private である間にラベルなしクエリのストリームに答えるアルゴリズム。標準構成は$T$クエリに対する$\sqrt{T}$依存性をもたらす。ストリーミング設定において,この依存度をT$でポリ対数に還元できることが示される。難解なオンライン敵と任意の概念クラス$\mathcal{C}$に対して、$|S|= \tilde{O}(VC(\mathcal{C})^{3.5}\log^{3.5}T)$ラベル付き例で$T$クエリに答えるプライベート予測器を与える。適応的オンライン逆数と$\mathbb{R}^d$上の半空間に対して、$|S|=\tilde{O}\left(d^{5.5}\log T\right)$を得る。

関連論文リスト

Sparse Linear Regression is Easy on Random Supports [20.128442161507582]
我々は mathbbRN times d$ で設計行列 $X を入力し、 mathbbRN times d$ で測定やラベル $y を入力します。 w*$がランダムに選択されると、およそ$N = O(klog d/epsilon)$サンプルで予測エラー$epsilon$が得られる。
論文参考訳（メタデータ） (2025-11-09T03:48:21Z)
Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition [12.926841066732223]
微分プライバシーモデル(DP-SCO)における凸最適化の検討任意の$thetageq 2$に対して、$rho$-zero集中微分プライバシーのプライベートミニマックスレートが$Omegaleftで制限されることを示す。
論文参考訳（メタデータ） (2025-09-04T21:30:44Z)
PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。我々はアルゴリズムをほぼ一致する下界で補完する。
論文参考訳（メタデータ） (2025-02-20T18:32:02Z)
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)
Profile Reconstruction from Private Sketches [13.929335175122265]
$mathcalD$から$n$のアイテムの多重集合が与えられたとき、強調される再構成問題は、$t = 0, 1, dots, n$ に対して、$mathcalD$ のアイテムの分数 $vecf[t]$ を正確に $tfty 倍と見積もることである。分散空間制約付き環境での個人プロファイル推定について検討し,マルチセットの更新可能なプライベートスケッチを維持したいと考える。 LPベースの手法の高速化方法を示します
論文参考訳（メタデータ） (2024-06-03T09:51:28Z)
Differentially Private Approximate Pattern Matching [0.0]
我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。 1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
論文参考訳（メタデータ） (2023-11-13T15:53:45Z)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文参考訳（メタデータ） (2022-07-15T11:55:09Z)
Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文参考訳（メタデータ） (2021-03-25T18:52:17Z)
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)
On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文参考訳（メタデータ） (2020-09-21T04:13:34Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)

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