論文の概要: Mini-batch Submodular Maximization

• arxiv url: http://arxiv.org/abs/2401.12478v2
• Date: Wed, 02 Oct 2024 09:02:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-03 15:17:46.210895
• Title: Mini-batch Submodular Maximization
• Title（参考訳）: ミニバッチ部分モジュラ最大化
• Authors: Gregory Schwartzman,
• Abstract要約: 単調デコンポーザブルな部分モジュラ関数,$F=sum_i=1N fi$ を制約の下で最大化する,最初のミニバッチアルゴリズムを提案する。 我々は、一様と重み付けの2つのサンプリング手法を検討する。 意外なことに, 実験結果から, 均一サンプリングは加重サンプリングよりも優れていることが示された。
• 参考スコア（独自算出の注目度）: 5.439020425819001
• License:
• Abstract: We present the first mini-batch algorithm for maximizing a non-negative monotone decomposable submodular function, $F=\sum_{i=1}^N f^i$, under a set of constraints. We consider two sampling approaches: uniform and weighted. We first show that mini-batch with weighted sampling improves over the state of the art sparsifier based approach both in theory and in practice. Surprisingly, our experimental results show that uniform sampling is superior to weighted sampling. However, it is impossible to explain this using worst-case analysis. Our main contribution is using smoothed analysis to provide a theoretical foundation for our experimental results. We show that, under very mild assumptions, uniform sampling is superior for both the mini-batch and the sparsifier approaches. We empirically verify that these assumptions hold for our datasets. Uniform sampling is simple to implement and has complexity independent of $N$, making it the perfect candidate to tackle massive real-world datasets.
• Abstract（参考訳）: 我々は,非負のモノトン分解可能部分モジュラ函数,$F=\sum_{i=1}^N f^i$ を制約の下で最大化する,最初のミニバッチアルゴリズムを提案する。 我々は、一様と重み付けの2つのサンプリング手法を検討する。 まず, 加重サンプリングによるミニバッチは, 理論と実際の両方において, 最先端のスパリファイアに基づくアプローチよりも改善されていることを示す。 意外なことに, 実験結果から, 均一サンプリングは加重サンプリングよりも優れていることが示された。 しかし、最悪のケース分析では説明できない。 我々の主な貢献は、スムーズな解析を用いて、実験結果の理論的基礎を提供することである。 非常に軽度な仮定の下では、一様サンプリングはミニバッチとスパシファイアアプローチの両方において優れていることを示す。 これらの仮定がデータセットに当てはまることを実証的に検証します。 均一サンプリングは実装が簡単で、N$とは無関係に複雑さがあり、大規模な現実世界のデータセットに取り組むのに最適な候補となる。

関連論文リスト

• Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel [10.840582511203024]
  我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでのみ実行できるように並列化可能であることを示す。 また、我々のアルゴリズムは、$widetilde O(log2 d)$ parallel roundsでしか実行できないことを示す。
  論文  参考訳（メタデータ） (2024-06-03T01:34:34Z)
• Simple and effective data augmentation for compositional generalization [64.00420578048855]
  MRをサンプリングし,それらを逆翻訳するデータ拡張法は,合成一般化に有効であることを示す。 注目すべきは、一様分布からのサンプリングは、テスト分布からのサンプリングとほぼ同等に実行されることである。
  論文  参考訳（メタデータ） (2024-01-18T09:13:59Z)
• Improved Active Learning via Dependent Leverage Score Sampling [8.400581768343804]
  本研究では,非依存的(逆方向雑音)環境下での能動学習手法の改善方法について述べる。 エンフェボタルサンプリングアルゴリズムに基づく簡単な実装法を提案する。 独立サンプリングと比較して,本手法は,所定の目標精度に到達するために必要なサンプル数を最大50%削減する。
  論文  参考訳（メタデータ） (2023-10-08T01:51:30Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling [156.7248383178991]
  コラボレーティブ・メトリック・ラーニング(CML)パラダイムはレコメンデーション・システム(RS)分野に広く関心を集めている。 負のサンプリングが一般化誤差のバイアス付き推定に繋がることがわかった。 そこで我々は,SFCML (textitSampling-Free Collaborative Metric Learning) という名前のCMLに対して,負のサンプリングを伴わない効率的な手法を提案する。
  論文  参考訳（メタデータ） (2022-06-23T08:50:22Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification [28.128464387420216]
  マイノリティグループサンプルの欠如によって学習が根本的に制約されていることを示す。 特にラベルシフトの場合、最小値のアンダーサンプリングアルゴリズムが常に存在することを示す。
  論文  参考訳（メタデータ） (2022-05-26T00:35:11Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  粒子フィルタリングは複素系の優れた非線形推定を計算するために用いられる。 粒子フィルタは様々なシナリオにおいて良好な推定値が得られることを示す。
  論文  参考訳（メタデータ） (2021-10-06T16:58:34Z)
• Is Simple Uniform Sampling Effective for Center-Based Clustering with Outliers: When and Why? [14.757827466271209]
  本稿では,3つの中心型クラスタリングを外乱問題で解くための簡易な一様サンプリングフレームワークを提案する。 我々の分析は、以前の(一様で非一様)サンプリングに基づく考え方と根本的に異なる。
  論文  参考訳（メタデータ） (2021-02-28T16:43:37Z)
• Learning Entangled Single-Sample Distributions via Iterative Trimming [28.839136703139225]
  そこで本研究では, 反復トリミング標本に基づいて, 簡便かつ効率的な手法を解析し, トリミング標本集合上のパラメータを再推定する。 対数反復法では, 誤差が$lceil alpha n rceil$-th ノイズ点の雑音レベルにのみ依存する推定値が出力されることを示す。
  論文  参考訳（メタデータ） (2020-04-20T18:37:43Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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