論文の概要: The Space Complexity of Learning-Unlearning Algorithms

• arxiv url: http://arxiv.org/abs/2506.13048v1
• Date: Mon, 16 Jun 2025 02:31:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:47.317582
• Title: The Space Complexity of Learning-Unlearning Algorithms
• Title（参考訳）: 学習学習アルゴリズムの空間複雑性
• Authors: Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman, Ayush Sekhari, Abhishek Shetty,
• Abstract要約: ユーザに対して強力なデータ削除保証を提供する機械学習アルゴリズムのメモリ複雑性について検討する。 後で特定のトレーニングサンプルを削除するために、どれくらいのストレージが必要か尋ねます。
• 参考スコア（独自算出の注目度）: 18.44297364051363
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users. Formally, consider an algorithm for a particular learning task that initially receives a training dataset. Then, after learning, it receives data deletion requests from a subset of users (of arbitrary size), and the goal of unlearning is to perform the task as if the learner never received the data of deleted users. In this paper, we ask how many bits of storage are needed to be able to delete certain training samples at a later time. We focus on the task of realizability testing, where the goal is to check whether the remaining training samples are realizable within a given hypothesis class \(\mathcal{H}\). Toward that end, we first provide a negative result showing that the VC dimension is not a characterization of the space complexity of unlearning. In particular, we provide a hypothesis class with constant VC dimension (and Littlestone dimension), but for which any unlearning algorithm for realizability testing needs to store \(\Omega(n)\)-bits, where \(n\) denotes the size of the initial training dataset. In fact, we provide a stronger separation by showing that for any hypothesis class \(\mathcal{H}\), the amount of information that the learner needs to store, so as to perform unlearning later, is lower bounded by the \textit{eluder dimension} of \(\mathcal{H}\), a combinatorial notion always larger than the VC dimension. We complement the lower bound with an upper bound in terms of the star number of the underlying hypothesis class, albeit in a stronger ticketed-memory model proposed by Ghazi et al. (2023). Since the star number for a hypothesis class is never larger than its Eluder dimension, our work highlights a fundamental separation between central and ticketed memory models for machine unlearning.
• Abstract（参考訳）: ユーザに対して強力なデータ削除保証を提供する機械学習アルゴリズムのメモリ複雑性について検討する。 正式には、トレーニングデータセットを最初に受信する特定の学習タスクのためのアルゴリズムを考える。 そして、学習後、ユーザのサブセット(任意のサイズ)からデータ削除要求を受け取り、学習のゴールは、学習者が削除されたユーザのデータを受け取らなかったかのようにタスクを実行することである。 本稿では,あるトレーニングサンプルを後で削除するために,ストレージのビット数を問う。 そこでは, ある仮説クラス \(\mathcal{H}\) の中で, 残りのトレーニングサンプルが実現可能であるかどうかを確認することを目的とする。 その目的のために、まず、VC次元が未学習の空間複雑性の特徴づけではないことを示すネガティブな結果を提供する。 特に、一定のVC次元(およびリトルストーン次元)を持つ仮説クラスを提供するが、実現可能性テストのための任意の未学習アルゴリズムは、初期トレーニングデータセットのサイズを表す \(n\)-bits を格納する必要がある。 実際、任意の仮説クラス \(\mathcal{H}\) に対して、学習者が後で学習を行うために格納しなければならない情報の量は、VC次元よりも大きい組合せ概念である \(\mathcal{H}\) のtextit{eluder dimension} によって制限される。 我々は、Ghazi et al (2023) によって提唱されたより強力なチケット付きメモリモデルではあるものの、下界は、基礎となる仮説クラスの星数の観点から上界で補う。 仮説クラスのスター数はエルダー次元よりも大きくなることはないので、我々の研究は中央記憶モデルと切符付き記憶モデルとの根本的な分離を強調している。

関連論文リスト

• MUSE: Machine Unlearning Six-Way Evaluation for Language Models [109.76505405962783]
  言語モデル(LM)は、プライベートおよび著作権のあるコンテンツを含む大量のテキストデータに基づいて訓練される。 総合的な機械学習評価ベンチマークであるMUSEを提案する。 人気のある8つのアンラーニングアルゴリズムがハリー・ポッターの本やニュース記事をいかに効果的に解き放つかをベンチマークする。
  論文  参考訳（メタデータ） (2024-07-08T23:47:29Z)
• Active Learning with Simple Questions [20.239213248652376]
  ドメインXに属するn個のラベルのない例のプールSを学習者が提示する活発な学習環境を考える。 我々は、学習者がドメインTサブセットXとターゲットラベルyのサブセットを選択することができるような、より一般的な領域クエリについて研究する。 我々は、VC次元 d の任意の仮説クラス H が与えられたとき、VC次元 O(d) の領域クエリファミリー Q を設計でき、これは n 個の例の集合 S の部分集合 X と H のすべての h* に対して、学習者が Q から A への O(d log n) クエリを提出できることを示している。
  論文  参考訳（メタデータ） (2024-05-13T17:13:32Z)
• Deep Unlearning: Fast and Efficient Gradient-free Approach to Class Forgetting [9.91998873101083]
  学習モデルから特定のクラスを戦略的に除去する新しいクラスアンラーニングアルゴリズムを提案する。 我々のアルゴリズムは、メンバーシップ推論攻撃(MIA)に対する競争的アンラーニング性能とレジリエンスを示す。
  論文  参考訳（メタデータ） (2023-12-01T18:29:08Z)
• Ticketed Learning-Unlearning Schemes [57.89421552780526]
  そこで我々は,学習のためのチケット付きモデルを提案する。 広義のコンセプトクラスに対して,空間効率のよいチケット付き学習スキームを提供する。
  論文  参考訳（メタデータ） (2023-06-27T18:54:40Z)
• A Survey of Learning on Small Data: Generalization, Optimization, and Challenge [101.27154181792567]
  ビッグデータの一般化能力を近似した小さなデータについて学ぶことは、AIの究極の目的の1つである。 この調査はPACフレームワークの下でのアクティブサンプリング理論に従い、小さなデータにおける学習の一般化誤差とラベルの複雑さを分析した。 効率的な小さなデータ表現の恩恵を受けるかもしれない複数のデータアプリケーションについて調査する。
  論文  参考訳（メタデータ） (2022-07-29T02:34:19Z)
• Vertical Machine Unlearning: Selectively Removing Sensitive Information From Latent Feature Space [21.8933559159369]
  遅延特徴空間から機密情報のみを除去することを目的とした縦型アンラーニングモードについて検討する。 我々はこの非学習について直観的かつ形式的な定義を導入し、既存の水平的非学習との関係を示す。 厳密な理論的解析により上界の近似を推定する。
  論文  参考訳（メタデータ） (2022-02-27T05:25:15Z)
• Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
  メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。 MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。 提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
  論文  参考訳（メタデータ） (2021-11-19T04:10:18Z)
• Learning the hypotheses space from data through a U-curve algorithm: a statistically consistent complexity regularizer for Model Selection [0.0]
  本稿では, モデル選択に対するデータ駆動型, 一貫性, 非排他的アプローチを提案する。 我々の主な貢献は、$mathbbL(mathcalH)$上で正規化モデル選択を行うデータ駆動の一般学習アルゴリズムである。 このアプローチの顕著な結果は、$mathbbL(mathcalH)$の非排他的探索が最適解を返すことができる条件である。
  論文  参考訳（メタデータ） (2021-09-08T18:28:56Z)

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

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