Fugu-MT 論文翻訳(概要): A One-Inclusion Graph Approach to Multi-Group Learning

論文の概要: A One-Inclusion Graph Approach to Multi-Group Learning

arxiv url: http://arxiv.org/abs/2603.23208v1
Date: Tue, 24 Mar 2026 13:52:25 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-25 19:53:37.509338
Title: A One-Inclusion Graph Approach to Multi-Group Learning
Title（参考訳）: 複数グループ学習のための一括グラフアプローチ
Authors: Noah Bergam, Samuel Deng, Daniel Hsu,
Abstract要約: 我々は、二部グラフの$b$-matchingの一般化を用いて、一括グラフ予測戦略を拡張した。グループ実現可能な設定では、アルゴリズムの$log n / n$収束率が一般に最適であることを示す下界を与える。
参考スコア（独自算出の注目度）: 8.394817466667677
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We prove the tightest-known upper bounds on the sample complexity of multi-group learning. Our algorithm extends the one-inclusion graph prediction strategy using a generalization of bipartite $b$-matching. In the group-realizable setting, we provide a lower bound confirming that our algorithm's $\log n / n$ convergence rate is optimal in general. If one relaxes the learning objective such that the group on which we are evaluated is chosen obliviously of the sample, then our algorithm achieves the optimal $1/n$ convergence rate under group-realizability.
Abstract（参考訳）: 我々は,多群学習におけるサンプルの複雑さについて,最もよく知られた上限を証明した。提案アルゴリズムは,2部分$b$-matchingの一般化を用いて,一括グラフ予測戦略を拡張した。グループ実現可能な設定では、アルゴリズムの$\log n / n$収束率が一般に最適であることを示す下界を与える。評価対象である群が標本から明白に選択されるように学習目標を緩和すると、アルゴリズムはグループ実現可能性の下で最適な1/n$収束率を達成する。

関連論文リスト

Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
論文参考訳（メタデータ） (2026-02-05T14:16:47Z)
Fair PCA, One Component at a Time [2.5056643038238504]
Min-Max Fair PCA問題では、グループ間で可能な限りバランスの取れたマルチグループデータの低ランクな表現を求める。この問題に対する既存のアプローチはランク-d$フェア部分空間を返すが、標準PCAの基本的な包含性は欠如している。フェアプライマリコンポーネントを,グループ単位の最大再構成誤差を最小限に抑える方向として定義する。このアプローチは、標準PCAの格納特性を保ち、単一のグループを持つデータに対する標準pcaに還元する。
論文参考訳（メタデータ） (2025-03-27T14:47:27Z)
Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文参考訳（メタデータ） (2024-04-24T18:39:18Z)
Efficient Algorithms for Empirical Group Distributional Robust Optimization and Beyond [15.664414751701718]
経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
論文参考訳（メタデータ） (2024-03-06T09:14:24Z)
Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文参考訳（メタデータ） (2023-12-13T11:08:25Z)
Agnostic Multi-Group Active Learning [24.97598179536084]
能動的学習の観点から,この問題の変種を考察し,学習者がコレクションの各分布からどの例をラベル付けするかを判断する権限を付与する。我々の主な課題は、不一致に基づくアクティブラーニングのような標準的なアクティブラーニング技術が、マルチグループラーニングの目的に直接適用されないことである。既存のアルゴリズムを改良し、多群学習の非依存的な定式化のための一貫した能動的学習アルゴリズムを提供する。
論文参考訳（メタデータ） (2023-06-02T21:24:13Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文参考訳（メタデータ） (2022-10-23T21:24:37Z)
On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文参考訳（メタデータ） (2022-10-22T19:07:26Z)

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