論文の概要: Deterministic Coreset Construction via Adaptive Sensitivity Trimming
- arxiv url: http://arxiv.org/abs/2508.18340v1
- Date: Mon, 25 Aug 2025 17:19:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-27 17:42:38.536391
- Title: Deterministic Coreset Construction via Adaptive Sensitivity Trimming
- Title（参考訳）: 適応感度トリミングによる決定論的コアセット構築
- Authors: Faruk Alpay, Taylan Alpay,
- Abstract要約: 実証的リスク最小化のための決定論的コアセット構築のためのフレームワークを開発する。
我々の中心的な貢献は、適応決定論的一様重みトリミング(ADUWT)アルゴリズムである。
我々は,インスタンス最適オラクル,決定論的ストリーミング,公平性に制約されたEMMについて,オープンな問題で結論付けた。
- 参考スコア（独自算出の注目度）: 0.2864713389096699
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop a rigorous framework for deterministic coreset construction in empirical risk minimization (ERM). Our central contribution is the Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm, which constructs a coreset by excising points with the lowest sensitivity bounds and applying a data-dependent uniform weight to the remainder. The method yields a uniform $(1\pm\varepsilon)$ relative-error approximation for the ERM objective over the entire hypothesis space. We provide complete analysis, including (i) a minimax characterization proving the optimality of the adaptive weight, (ii) an instance-dependent size analysis in terms of a \emph{Sensitivity Heterogeneity Index}, and (iii) tractable sensitivity oracles for kernel ridge regression, regularized logistic regression, and linear SVM. Reproducibility is supported by precise pseudocode for the algorithm, sensitivity oracles, and evaluation pipeline. Empirical results align with the theory. We conclude with open problems on instance-optimal oracles, deterministic streaming, and fairness-constrained ERM.
- Abstract（参考訳）: 経験的リスク最小化(ERM)における決定論的コアセット構築のための厳密な枠組みを開発する。
我々の中心的な貢献は、アダプティブ決定論的一様重み付け(ADUWT)アルゴリズムであり、最小感度境界を持つ点を抽出し、残りにデータ依存の一様重みを適用することでコアセットを構築する。
この方法では、仮説空間全体に対するERMの目的に対する相対誤差近似が一様である(1\pm\varepsilon)$ となる。
完全な分析も行います。
(i)適応重量の最適性を証明するミニマックス特性
(ii) \emph{Sensitivity Heterogeneity Index} の観点からのインスタンス依存のサイズ解析、及び
3)カーネルリッジレグレッション,正規化ロジスティックレグレッション,線形SVMのためのトラクタブル感度オラクル。
再現性は、アルゴリズム、感度オラクル、評価パイプラインの正確な擬似コードによってサポートされている。
実証的な結果は理論と一致している。
我々は,インスタンス最適オラクル,決定論的ストリーミング,公平性に制約されたEMMについて,オープンな問題で結論付けた。
関連論文リスト
- Enhancing Distributional Robustness in Principal Component Analysis by Wasserstein Distances [7.695578200868269]
主成分分析(PCA)の分布ロバスト最適化(DRO)モデルについて,基礎となる確率分布の不確実性を考慮する。
結果の定式化は非滑らかな制約付き min-max 最適化問題につながり、曖昧性集合はタイプ2$ワッサーシュタイン距離で分布の不確かさを捉える。
この明示的な特徴付けは、元の DRO モデルを、複雑な非滑らかな項を持つスティーフェル多様体上の最小化問題に同値に再構成する。
論文 参考訳（メタデータ） (2025-03-04T11:00:08Z) - Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳（メタデータ） (2024-11-21T10:26:17Z) - Structured Optimal Variational Inference for Dynamic Latent Space Models [16.531262817315696]
動的ネットワークの潜在空間モデルについて検討し、その目的は、ペアの内積と潜在位置のインターセプトを推定することである。
後部推論と計算スケーラビリティのバランスをとるために、構造的平均場変動推論フレームワークを検討する。
論文 参考訳（メタデータ） (2022-09-29T22:10:42Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳（メタデータ） (2021-12-24T17:21:04Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Optimal Sampling Density for Nonparametric Regression [5.3219212985943924]
本稿では,モデルに依存しない,モデルミスマッチに対する頑健な回帰学習戦略を提案する。
我々は、平均積分誤差(MISE)を一般化基準として採用し、MISEの挙動と局所的に最適な帯域幅を用いる。
提案手法のほとんどモデルフリーな性質は、対象問題の生特性を符号化し、堅牢でモデルに依存しない能動的学習戦略を提供する。
論文 参考訳（メタデータ） (2021-05-25T14:52:17Z) - Neural Stochastic Contraction Metrics for Learning-based Control and
Estimation [13.751135823626493]
NSCMフレームワークにより、自律エージェントは最適な安定制御と推定ポリシーをリアルタイムで近似することができる。
これは、状態依存リカティ方程式、反復LQR、EKF、神経収縮など、既存の非線形制御と推定技術より優れている。
論文 参考訳（メタデータ） (2020-11-06T03:04:42Z) - Neural Control Variates [71.42768823631918]
ニューラルネットワークの集合が、積分のよい近似を見つけるという課題に直面していることを示す。
理論的に最適な分散最小化損失関数を導出し、実際に安定したオンライントレーニングを行うための代替の複合損失を提案する。
具体的には、学習した光場近似が高次バウンスに十分な品質であることを示し、誤差補正を省略し、無視可能な可視バイアスのコストでノイズを劇的に低減できることを示した。
論文 参考訳（メタデータ） (2020-06-02T11:17:55Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。