論文の概要: Data Debugging is NP-hard for Classifiers Trained with SGD
- arxiv url: http://arxiv.org/abs/2408.01365v1
- Date: Fri, 2 Aug 2024 16:17:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-05 12:48:28.964125
- Title: Data Debugging is NP-hard for Classifiers Trained with SGD
- Title（参考訳）: データデバッグはSGDで訓練された分類器のNPハードである
- Authors: Zizheng Guo, Pengyu Chen, Yanzhang Fu, Dongjing Miao,
- Abstract要約: Debuggableという問題の計算複雑性について検討する。
損失関数とモデルの次元が固定されていなければ、Debuggableは訓練順序に関係なくNP完全である。
- 参考スコア（独自算出の注目度）: 8.449687092741604
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Data debugging is to find a subset of the training data such that the model obtained by retraining on the subset has a better accuracy. A bunch of heuristic approaches are proposed, however, none of them are guaranteed to solve this problem effectively. This leaves an open issue whether there exists an efficient algorithm to find the subset such that the model obtained by retraining on it has a better accuracy. To answer this open question and provide theoretical basis for further study on developing better algorithms for data debugging, we investigate the computational complexity of the problem named Debuggable. Given a machine learning model $\mathcal{M}$ obtained by training on dataset $D$ and a test instance $(\mathbf{x}_\text{test},y_\text{test})$ where $\mathcal{M}(\mathbf{x}_\text{test})\neq y_\text{test}$, Debuggable is to determine whether there exists a subset $D^\prime$ of $D$ such that the model $\mathcal{M}^\prime$ obtained by retraining on $D^\prime$ satisfies $\mathcal{M}^\prime(\mathbf{x}_\text{test})=y_\text{test}$. To cover a wide range of commonly used models, we take SGD-trained linear classifier as the model and derive the following main results. (1) If the loss function and the dimension of the model are not fixed, Debuggable is NP-complete regardless of the training order in which all the training samples are processed during SGD. (2) For hinge-like loss functions, a comprehensive analysis on the computational complexity of Debuggable is provided; (3) If the loss function is a linear function, Debuggable can be solved in linear time, that is, data debugging can be solved easily in this case. These results not only highlight the limitations of current approaches but also offer new insights into data debugging.
- Abstract（参考訳）: データデバッギングは、トレーニングデータのサブセットを見つけることであり、サブセットで再トレーニングしたモデルの方が精度が高い。
しかし、多くのヒューリスティックなアプローチが提案されているが、この問題を効果的に解決することは保証されていない。
このことは、再トレーニングによって得られたモデルの方が精度が良いような、より効率的なアルゴリズムが存在するかどうかという未解決の問題を残している。
このオープンな疑問に答え、データデバッギングのためのより良いアルゴリズムを開発するための理論的基礎を提供するために、Debuggableという問題の計算複雑性について検討する。
データセット $D$ とテストインスタンス $(\mathbf{x}_\text{test},y_\text{test})$ where $\mathcal{M}(\mathbf{x}_\text{test})\neq y_\text{test}$, Debuggable が与えられたら、$D$ のサブセット $D^\prime$ が存在して、モデル $D^\prime$ が $D^\prime$ のトレーニングによって得られる$D^\prime$ が $\mathcal{M}^\prime(\mathbf{x}_\text{test})=y\text{test}$ となる。
広く使われているモデルをカバーするため,SGD学習線形分類器をモデルとし,以下の主な結果を導出する。
1) 損失関数とモデルの寸法が固定されていなければ、デバッジャブルはSGD中に全てのトレーニングサンプルが処理される訓練順序にかかわらずNP完全である。
2) ヒンジライクな損失関数に対しては,デバッジャブルの計算複雑性を包括的に解析し,(3) 損失関数が線形関数であれば,デバッジャブルは線形時間で解ける。
これらの結果は、現在のアプローチの限界を浮き彫りにするだけでなく、データデバッギングに関する新たな洞察を提供する。
関連論文リスト
- Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models [10.603378323312809]
我々は、制約された最も予測可能な説明(CMPE)問題に対して、ほぼ最適解を出力することを学ぶディープニューラルネットワークを訓練する。
提案手法の特性を解析し,その有効性をいくつかのベンチマーク問題で実験的に実証する。
論文 参考訳（メタデータ） (2024-04-17T17:55:17Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - 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) - Easy Differentially Private Linear Regression [16.325734286930764]
本研究では,指数関数機構を用いて,非プライベート回帰モデルの集合からタキー深度の高いモデルを選択するアルゴリズムについて検討する。
このアルゴリズムは、データリッチな設定において、強い経験的性能を得る。
論文 参考訳（メタデータ） (2022-08-15T17:42:27Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳（メタデータ） (2022-02-08T12:58:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。