Fugu-MT 論文翻訳(概要): From Adaptive Query Release to Machine Unlearning

論文の概要: From Adaptive Query Release to Machine Unlearning

arxiv url: http://arxiv.org/abs/2307.11228v1
Date: Thu, 20 Jul 2023 20:46:39 GMT
ステータス: 処理完了
システム内更新日: 2023-07-24 14:23:04.768797
Title: From Adaptive Query Release to Machine Unlearning
Title（参考訳）: adaptive query releaseからmachine unlearningへ
Authors: Enayat Ullah, Raman Arora
Abstract要約: 我々は、学習アルゴリズムに対応する効率的な学習アルゴリズムの設計として、機械学習の問題を定式化する。凸最適化(SCO)のアンラーニングを上記のように減らし,問題に対する保証を改善できることを示す。
参考スコア（独自算出の注目度）: 34.25760971846068
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We formalize the problem of machine unlearning as design of efficient unlearning algorithms corresponding to learning algorithms which perform a selection of adaptive queries from structured query classes. We give efficient unlearning algorithms for linear and prefix-sum query classes. As applications, we show that unlearning in many problems, in particular, stochastic convex optimization (SCO), can be reduced to the above, yielding improved guarantees for the problem. In particular, for smooth Lipschitz losses and any $\rho>0$, our results yield an unlearning algorithm with excess population risk of $\tilde O\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\rho}\big)$ with unlearning query (gradient) complexity $\tilde O(\rho \cdot \text{Retraining Complexity})$, where $d$ is the model dimensionality and $n$ is the initial number of samples. For non-smooth Lipschitz losses, we give an unlearning algorithm with excess population risk $\tilde O\big(\frac{1}{\sqrt{n}}+\big(\frac{\sqrt{d}}{n\rho}\big)^{1/2}\big)$ with the same unlearning query (gradient) complexity. Furthermore, in the special case of Generalized Linear Models (GLMs), such as those in linear and logistic regression, we get dimension-independent rates of $\tilde O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{2/3}}\big)$ and $\tilde O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{1/3}}\big)$ for smooth Lipschitz and non-smooth Lipschitz losses respectively. Finally, we give generalizations of the above from one unlearning request to \textit{dynamic} streams consisting of insertions and deletions.
Abstract（参考訳）: 構造化クエリクラスから適応クエリを選択する学習アルゴリズムに対応する効率的なアンラーニングアルゴリズムの設計として,機械学習の問題を定式化する。線形およびプレフィックスサムクエリクラスに対する効率的な未学習アルゴリズムを提供する。応用として,多くの問題,特に確率凸最適化(sco)におけるアンラーニングが,上記の問題に還元され,問題に対する保証が向上することを示す。特に、スムースなリプシッツ損失と任意の$\rho>0$に対して、この結果は、$d$がモデル次元であり、$n$がサンプルの初期数である$\tilde o\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\rho}\big)$という過剰な人口リスクを持つ未学習アルゴリズムをもたらす。非スムースリプシッツ損失に対しては、過剰な人口リスクを持つアンラーニングアルゴリズムに、同じアンラーニングクエリ(gradient)複雑性を持つ$\tilde o\big(\frac{1}{\sqrt{n}}+\big(\frac{\sqrt{d}}{n\rho}\big)^{1/2}\big)$を与える。さらに、線形回帰やロジスティック回帰のような一般化線形モデル(GLM)の特別な場合では、滑らかなリプシッツと非滑らかなリプシッツの損失に対して、それぞれ$\tilde O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{2/3}}\big)$と$\tilde O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{1/3}}\big)$の次元非依存率を得る。最後に、上記を1つの未学習リクエストから挿入と削除からなる‘textit{dynamic}ストリームへ一般化する。

関連論文リスト

Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Online Lewis Weight Sampling [62.38157566916501]
コーエンとペンはルイスの重量サンプリングを理論計算機科学コミュニティに導入した。この重要なプリミティブを、オンラインコアセット、スライディングウィンドウ、対向ストリーミングモデルなど、他の設定に拡張した作品もいくつかある。オンラインコアセット,スライディングウィンドウ,および逆ストリーミングモデルにおいて,すべての$pin(0,infty)$に対して,ほぼ最適に近い$ell_p$サブスペース埋め込みを設計する。
論文参考訳（メタデータ） (2022-07-17T19:40:51Z)
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。我々はこの$d$への依存が対数的要因まで最適であることを示す。また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文参考訳（メタデータ） (2021-11-09T00:20:01Z)
On the Sample Complexity of Privately Learning Axis-Aligned Rectangles [16.092248433189816]
有限格子上で軸-アラインド-矩形を学習する基本的な問題を再考する。サンプルの複雑さを$tildeOleftdcdotleft(log*|X|right)1.5right$に減らす新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-07-24T04:06:11Z)
Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings [15.122617358656539]
凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
論文参考訳（メタデータ） (2021-07-12T17:06:08Z)
Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints [94.76881135901753]
一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
論文参考訳（メタデータ） (2021-01-06T18:56:07Z)
An Algorithm for Learning Smaller Representations of Models With Scarce Data [0.0]
データセットが小さすぎるか、完全に代表的でない状況下で、二項分類問題を解くための欲求的アルゴリズムを提案する。それは、ゆるやかな精度の制約、反復的なハイパーパラメータプルーニング手順、新しいデータを生成するために使われる関数といった訓練されたモデルに依存している。
論文参考訳（メタデータ） (2020-10-15T19:17:51Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)
Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits [3.9919781077062497]
アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
論文参考訳（メタデータ） (2020-02-17T21:32:04Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。