論文の概要: Oracle Efficient Online Multicalibration and Omniprediction
- arxiv url: http://arxiv.org/abs/2307.08999v1
- Date: Tue, 18 Jul 2023 06:34:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-19 16:12:08.591529
- Title: Oracle Efficient Online Multicalibration and Omniprediction
- Title（参考訳）: oracleの効率的なオンラインマルチカリブレーションとomniprediction
- Authors: Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth
- Abstract要約: オンライン逆境設定における全方位予測について検討する。
我々は、無限ベンチマーククラス$F$に対してよく定義された新しいオンラインマルチキャリブレーションアルゴリズムを開発した。
我々は、我々のレートが改善できる範囲について、上と下の境界を示す。
- 参考スコア（独自算出の注目度）: 15.476402844435704
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A recent line of work has shown a surprising connection between
multicalibration, a multi-group fairness notion, and omniprediction, a learning
paradigm that provides simultaneous loss minimization guarantees for a large
family of loss functions. Prior work studies omniprediction in the batch
setting. We initiate the study of omniprediction in the online adversarial
setting. Although there exist algorithms for obtaining notions of
multicalibration in the online adversarial setting, unlike batch algorithms,
they work only for small finite classes of benchmark functions $F$, because
they require enumerating every function $f \in F$ at every round. In contrast,
omniprediction is most interesting for learning theoretic hypothesis classes
$F$, which are generally continuously large.
We develop a new online multicalibration algorithm that is well defined for
infinite benchmark classes $F$, and is oracle efficient (i.e. for any class
$F$, the algorithm has the form of an efficient reduction to a no-regret
learning algorithm for $F$). The result is the first efficient online
omnipredictor -- an oracle efficient prediction algorithm that can be used to
simultaneously obtain no regret guarantees to all Lipschitz convex loss
functions. For the class $F$ of linear functions, we show how to make our
algorithm efficient in the worst case. Also, we show upper and lower bounds on
the extent to which our rates can be improved: our oracle efficient algorithm
actually promises a stronger guarantee called swap-omniprediction, and we prove
a lower bound showing that obtaining $O(\sqrt{T})$ bounds for
swap-omniprediction is impossible in the online setting. On the other hand, we
give a (non-oracle efficient) algorithm which can obtain the optimal
$O(\sqrt{T})$ omniprediction bounds without going through multicalibration,
giving an information theoretic separation between these two solution concepts.
- Abstract（参考訳）: 近年の研究は、多群フェアネスの概念であるマルチカリブレーションと、多数の損失関数に対する同時損失最小化保証を提供する学習パラダイムであるomnipredictionの間に驚くべき関連性を示している。
先行研究は、バッチ設定における全合成の研究である。
我々は,オンライン・アドバーサル・セッティングにおける全量予測の研究を開始する。
オンラインの逆境設定で多重化の概念を得るアルゴリズムは存在するが、バッチアルゴリズムとは異なり、各ラウンドごとに$f \in f$の関数を列挙する必要があるため、ベンチマーク関数の小さな有限クラスに対してのみ動作する。
対照的に、オムニプレディクションは、一般に連続的に大きい理論仮説クラス$F$を学ぶのに最も興味深い。
私たちは、無限ベンチマーククラス$f$でよく定義された新しいオンラインマルチキャリブレーションアルゴリズムを開発し、oracleの効率的(すなわち、どのクラス$f$に対して、このアルゴリズムは、非レグレット学習アルゴリズムを$f$で効率良く還元する形式を持つ)である。
これはoracleの効率的な予測アルゴリズムであり、すべてのリプシッツ凸損失関数に対する後悔の保証を同時に得ることなく利用できる。
線形関数のクラス$f$については、最悪の場合にアルゴリズムを効率的にする方法を示します。
oracleの効率的なアルゴリズムは、実際にはswap-omnipredictionと呼ばれるより強力な保証を約束しており、swap-omnipredictionの$o(\sqrt{t})$バウンドを取得することはオンライン環境では不可能であることを示す下限を示します。
一方、最適の$O(\sqrt{T})$ omniprediction界を多重校正を経ずに得ることができる(非オラクル効率)アルゴリズムを与え、これらの2つの解概念間の情報理論的な分離を与える。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees [21.30065439295409]
オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。
提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。
我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
論文 参考訳（メタデータ） (2022-02-09T20:56:16Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。