論文の概要: On Socially Fair Low-Rank Approximation and Column Subset Selection

• arxiv url: http://arxiv.org/abs/2412.06063v1
• Date: Sun, 08 Dec 2024 20:34:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-10 14:56:50.650398
• Title: On Socially Fair Low-Rank Approximation and Column Subset Selection
• Title（参考訳）: 社会的に公平な低ランク近似とカラムサブセット選択について
• Authors: Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou,
• Abstract要約: 低ランク近似と列サブセット選択は、豊富な機械学習アプリケーションに適用される2つの基本的および関連する問題である。 驚くべきことに、一定要素の近似であっても、特定の標準複雑性仮説の下では指数時間を必要とすることが示される。 一定の数の群と一定要素の精度で、na"ive $ntextpoly(k)$ではなく2textpoly(k)$ timeで実行されるような、公平な低ランク近似のアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 62.44413238556872
• License:
• Abstract: Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. In this paper, we study the question of socially fair low-rank approximation and socially fair column subset selection, where the goal is to minimize the loss over all sub-populations of the data. We show that surprisingly, even constant-factor approximation to fair low-rank approximation requires exponential time under certain standard complexity hypotheses. On the positive side, we give an algorithm for fair low-rank approximation that, for a constant number of groups and constant-factor accuracy, runs in $2^{\text{poly}(k)}$ time rather than the na\"{i}ve $n^{\text{poly}(k)}$, which is a substantial improvement when the dataset has a large number $n$ of observations. We then show that there exist bicriteria approximation algorithms for fair low-rank approximation and fair column subset selection that run in polynomial time.
• Abstract（参考訳）: 低ランク近似と列サブセット選択は、豊富な機械学習アプリケーションに適用される2つの基本的および関連する問題である。 本稿では,社会的に公平な低ランク近似と社会的に公平な列サブセット選択の課題について考察する。 驚くべきことに、一定の標準複雑性仮説の下では、公平な低ランク近似に対する定数近似でさえ指数時間を必要とすることが示される。 正の面では、一定数の群と一定要素の精度に対して、na\"{i}ve $n^{\text{poly}(k)}$よりも2^{\text{poly}(k)}$時間で実行されるような、公平な低ランク近似のアルゴリズムを与える。 そこで,両基準近似アルゴリズムが,多項式時間で動作する等高階近似および等高列部分集合選択に対して存在することを示す。

関連論文リスト

• Minimax and Communication-Efficient Distributed Best Subset Selection with Oracle Property [0.358439716487063]
  大規模データの爆発はシングルマシンシステムの処理能力を上回っている。 分散推論への伝統的なアプローチは、高次元データセットにおいて真の疎性を達成するのにしばしば苦労する。 そこで本稿では,これらの問題に対処する2段階分散ベストサブセット選択アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-08-30T13:22:08Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• 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)
• Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
  大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。 分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。 十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
  論文  参考訳（メタデータ） (2022-02-05T01:59:09Z)
• Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error [0.3997680012976965]
  目標は、最悪の予測エラーを最小限に抑える推定器を設計することである。 Chen, Valiant および Valiant は、データ値が $ell_infty$-normalized の場合、平均の推定値を計算する時間アルゴリズムが存在することを示した。 本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-12-27T18:47:25Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Predict then Interpolate: A Simple Algorithm to Learn Stable Classifiers [59.06169363181417]
  Predict then Interpolate (PI) は環境全体にわたって安定な相関関係を学習するためのアルゴリズムである。 正しい予測と間違った予測の分布を補間することにより、不安定な相関が消えるオラクル分布を明らかにすることができる。
  論文  参考訳（メタデータ） (2021-05-26T15:37:48Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。 我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
  論文  参考訳（メタデータ） (2021-05-13T18:24:30Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)

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

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