論文の概要: Online Algorithms with Limited Data Retention
- arxiv url: http://arxiv.org/abs/2404.10997v1
- Date: Wed, 17 Apr 2024 02:17:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-18 15:34:07.511880
- Title: Online Algorithms with Limited Data Retention
- Title（参考訳）: データ保持を限定したオンラインアルゴリズム
- Authors: Nicole Immorlica, Brendan Lucier, Markus Mobius, James Siderius,
- Abstract要約: データ保持に関する厳密な制約を受けるオンラインアルゴリズムのモデルを導入する。
我々は,全てのデータをできるだけ長く保持するベースラインアルゴリズムよりも指数関数的に改善できることを示す。
我々の結果の1つの意味は、データ保持法は忘れられる権利を保証するのに不十分であるということだ。
- 参考スコア（独自算出の注目度）: 4.101276693704335
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a model of online algorithms subject to strict constraints on data retention. An online learning algorithm encounters a stream of data points, one per round, generated by some stationary process. Crucially, each data point can request that it be removed from memory $m$ rounds after it arrives. To model the impact of removal, we do not allow the algorithm to store any information or calculations between rounds other than a subset of the data points (subject to the retention constraints). At the conclusion of the stream, the algorithm answers a statistical query about the full dataset. We ask: what level of performance can be guaranteed as a function of $m$? We illustrate this framework for multidimensional mean estimation and linear regression problems. We show it is possible to obtain an exponential improvement over a baseline algorithm that retains all data as long as possible. Specifically, we show that $m = \textsc{Poly}(d, \log(1/\epsilon))$ retention suffices to achieve mean squared error $\epsilon$ after observing $O(1/\epsilon)$ $d$-dimensional data points. This matches the error bound of the optimal, yet infeasible, algorithm that retains all data forever. We also show a nearly matching lower bound on the retention required to guarantee error $\epsilon$. One implication of our results is that data retention laws are insufficient to guarantee the right to be forgotten even in a non-adversarial world in which firms merely strive to (approximately) optimize the performance of their algorithms. Our approach makes use of recent developments in the multidimensional random subset sum problem to simulate the progression of stochastic gradient descent under a model of adversarial noise, which may be of independent interest.
- Abstract（参考訳）: データ保持に関する厳密な制約を受けるオンラインアルゴリズムのモデルを導入する。
オンライン学習アルゴリズムは、一定のプロセスによって生成される1ラウンドごとに1つのデータポイントのストリームに遭遇する。
重要なことに、各データポイントは、到着後にメモリ$m$ラウンドから削除するよう要求することができる。
除去の影響をモデル化するために、我々はアルゴリズムがデータポイントのサブセット以外のラウンド間での情報や計算を格納することを許さない(保持制約に従わなければならない)。
ストリームの終了時に、アルゴリズムは全データセットに関する統計的クエリに答える。
どのようなレベルのパフォーマンスが$m$の関数として保証できるのか?
多次元平均推定と線形回帰問題に対するこの枠組みについて説明する。
我々は,全てのデータをできるだけ長く保持するベースラインアルゴリズムよりも指数関数的に改善できることを示す。
具体的には、$m = \textsc{Poly}(d, \log(1/\epsilon))$ Retention suffices to achieve mean squared error $\epsilon$ observed $O(1/\epsilon)$ $d$-dimensional data points。
これは、全てのデータを永久に保持する最適な、しかし実現不可能なアルゴリズムのエラー境界と一致する。
また、エラーを$\epsilon$で保証するために必要な保持値にほぼ一致する低い境界を示す。
我々の結果の1つの意味は、企業がアルゴリズムの性能を(ほぼ)最適化しようとする非敵の世界においても、データ保持法は忘れられる権利を保証するには不十分であるということだ。
本手法は, 確率的勾配降下の進行を, 独立性のある対向雑音のモデルの下でシミュレートするために, 多次元ランダム部分集合和問題における最近の展開を利用する。
関連論文リスト
- On the Convergence of a Federated Expectation-Maximization Algorithm [0.0]
本稿では,Federated Mixture of $K$ Linear Regressionsモデルに対する期待最大化(EM)アルゴリズムの収束率について検討する。
驚くべきことに、結果はボトルネックではなく、データの異質性によってフェデレート学習アルゴリズムの収束が加速することを示している。
論文 参考訳（メタデータ） (2024-08-11T16:46:42Z) - Private Geometric Median [10.359525525715421]
データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。
我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
論文 参考訳（メタデータ） (2024-06-11T16:13:09Z) - Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - Scaling Laws for Data Filtering -- Data Curation cannot be Compute Agnostic [99.3682210827572]
ビジョン言語モデル(VLM)は、慎重にキュレートされたWebデータセット上で数千のGPU時間でトレーニングされる。
データキュレーション戦略は通常、トレーニングに利用可能な計算を知らないように開発されている。
ウェブデータの非均一性を考慮したニューラルスケーリング法則を導入する。
論文 参考訳（メタデータ） (2024-04-10T17:27:54Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Differentially Private Federated Learning via Inexact ADMM [0.0]
差分プライバシー(DP)技術は、データプライバシを推論攻撃から保護するために、フェデレーション付き学習モデルに適用することができる。
我々は,信頼領域のサブプロブレム列を解く乗算器アルゴリズムのDP不正確な交互方向法を開発した。
提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも22%削減すると同時に,データプライバシのレベルも同等に向上する。
論文 参考訳（メタデータ） (2021-06-11T02:28:07Z) - An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic
Gradient Descent and Thompson Sampling [83.48992319018147]
プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。
この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。
本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。
過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
論文 参考訳（メタデータ） (2020-06-07T01:12:39Z) - A Deterministic Streaming Sketch for Ridge Regression [15.256452294422294]
リッジ回帰を推定するための決定論的空間効率アルゴリズムを提案する。
これは、ソリューションエラーが保証された最初の$o(d2)$空間決定論的ストリーミングアルゴリズムである。
合成データセットと実世界のデータセットのランダムなスケッチアルゴリズムと比較して、我々のアルゴリズムは空間と類似時間が少なくて経験的誤差が少ない。
論文 参考訳（メタデータ） (2020-02-05T22:08:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。