論文の概要: Complexity-Theoretic Implications of Multicalibration

• arxiv url: http://arxiv.org/abs/2312.17223v2
• Date: Mon, 29 Jul 2024 12:14:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-31 00:26:37.275578
• Title: Complexity-Theoretic Implications of Multicalibration
• Title（参考訳）: 複雑度理論による多重校正の意義
• Authors: Sílvia Casacuberta, Cynthia Dwork, Salil Vadhan,
• Abstract要約: 多精度予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。 この複雑性理論的正則性レンマは、異なる領域に影響を及ぼすことが知られている。 すべての函数(その硬さによらず)が不随伴なハードコア集合の小さな集合を持つことが示される。
• 参考スコア（独自算出の注目度）: 8.315801422499863
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors are correct in expectation on each member of an arbitrary collection of pre-specified sets. Multicalibrated predictors satisfy a stronger condition: they are calibrated on each set in the collection. Multiaccuracy is equivalent to a regularity notion for functions defined by Trevisan, Tulsiani, and Vadhan (2009). They showed that, given a class $F$ of (possibly simple) functions, an arbitrarily complex function $g$ can be approximated by a low-complexity function $h$ that makes a small number of oracle calls to members of $F$, where the notion of approximation requires that $h$ cannot be distinguished from $g$ by members of $F$. This complexity-theoretic Regularity Lemma is known to have implications in different areas, including in complexity theory, additive number theory, information theory, graph theory, and cryptography. Starting from the stronger notion of multicalibration, we obtain stronger and more general versions of a number of applications of the Regularity Lemma, including the Hardcore Lemma, the Dense Model Theorem, and the equivalence of conditional pseudo-min-entropy and unpredictability. For example, we show that every boolean function (regardless of its hardness) has a small collection of disjoint hardcore sets, where the sizes of those hardcore sets are related to how balanced the function is on corresponding pieces of an efficient partition of the domain.
• Abstract（参考訳）: 本稿では,予測アルゴリズムの多群公正性に関する最近の文献と計算複雑性の古典的結果との関連性を示す。 多精度予測器は、あらかじめ特定された集合の任意の集合の各々のメンバに対して正しい。 多重校正予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。 多重精度はトレビサン、タルシアニ、ヴァダン(2009)によって定義される函数の正則性の概念と等価である。 彼らは、クラス$F$(おそらく単純な)関数が与えられたとき、任意の複素関数$g$は、$F$のメンバに少数のオラクル呼び出しを行う低複雑さ関数$h$によって近似できることを示した。 この複雑性理論の正則性補題は、複雑性理論、加法数論、情報理論、グラフ理論、暗号学など、様々な分野に影響を及ぼすことが知られている。 多重校正というより強い概念から、Hardcore Lemma、Dense Model Theorem、条件付き擬似ミニエントロピーと予測不能の同値性など、正規性補題の多くの応用のより強くより一般的なバージョンを得る。 例えば、すべてのブール関数(その硬さによらず)が小さな不随伴ハードコア集合の集合を持つことを示し、これらのハードコア集合のサイズは、その函数がドメインの効率的な分割の対応する部分上でどのようにバランス付けられたかに関係している。

関連論文リスト

• Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
  平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。 我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。 我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
  論文  参考訳（メタデータ） (2023-10-04T17:24:45Z)
• Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity [14.93584434176082]
  擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。 我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
  論文  参考訳（メタデータ） (2021-08-19T15:50:41Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• Learning Aggregation Functions [78.47770735205134]
  任意の濃度の集合に対する学習可能なアグリゲータであるLAF(Learning Aggregation Function)を紹介する。 半合成および実データを用いて,LAFが最先端の和(max-)分解アーキテクチャより優れていることを示す実験を報告する。
  論文  参考訳（メタデータ） (2020-12-15T18:28:53Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Quantum Ensemble for Classification [2.064612766965483]
  機械学習のパフォーマンスを改善する強力な方法は、複数のモデルの予測を組み合わせたアンサンブルを構築することである。 量子重ね合わせ,絡み合い,干渉を利用して分類モデルのアンサンブルを構築する新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-02T11:26:54Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURFは分布を断片的に近似するアルゴリズムである。 実験では最先端のアルゴリズムよりも優れています。
  論文  参考訳（メタデータ） (2020-02-22T01:03:33Z)

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

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