論文の概要: Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
- arxiv url: http://arxiv.org/abs/2502.12564v1
- Date: Tue, 18 Feb 2025 06:01:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-19 14:05:44.901962
- Title: Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses
- Title(参考訳): 非線形損失に対する試料有効オムニディクションと下流スワップレグレット
- Authors: Jiuyao Lu, Aaron Roth, Mirah Shi,
- Abstract要約: 「決定スワップ後悔」は、下流スワップ後悔と全滅の予測を一般化する。
また、オンライン逆数設定において、任意の多次元リプシッツ損失関数に対してそれを得るアルゴリズムも提供する。
- 参考スコア(独自算出の注目度): 4.509643050721454
- License:
- Abstract: We define "decision swap regret" which generalizes both prediction for downstream swap regret and omniprediction, and give algorithms for obtaining it for arbitrary multi-dimensional Lipschitz loss functions in online adversarial settings. We also give sample complexity bounds in the batch setting via an online-to-batch reduction. When applied to omniprediction, our algorithm gives the first polynomial sample-complexity bounds for Lipschitz loss functions -- prior bounds either applied only to linear loss (or binary outcomes) or scaled exponentially with the error parameter even under the assumption that the loss functions were convex. When applied to prediction for downstream regret, we give the first algorithm capable of guaranteeing swap regret bounds for all downstream agents with non-linear loss functions over a multi-dimensional outcome space: prior work applied only to linear loss functions, modeling risk neutral agents. Our general bounds scale exponentially with the dimension of the outcome space, but we give improved regret and sample complexity bounds for specific families of multidimensional functions of economic interest: constant elasticity of substitution (CES), Cobb-Douglas, and Leontief utility functions.
- Abstract(参考訳): そこで我々は,下流スワップ・リフレクションの予測を一般化した「決定スワップ・リフレクション」を定義し,オンライン環境において任意の多次元リプシッツ損失関数を求めるアルゴリズムを提案する。
また、オンライン・ツー・バッチ・リダクションによるバッチ設定の複雑さのサンプルも提供します。
このアルゴリズムは、リプシッツの損失関数に対する最初の多項式サンプル-複素性境界を与える -- 以前の境界は、損失関数が凸である仮定下であっても、線形損失(または二項結果)にのみ適用されるか、誤差パラメータと指数関数的にスケールする。
多次元の損失関数を持つ下流エージェントに対して, 線形損失関数にのみ適用される前の作業, リスク中立エージェントをモデル化する。
我々の一般境界は結果空間の次元と指数関数的にスケールするが、経済利害の多次元関数の特定の族、すなわち置換の定数弾性(CES)、コブ・ダグラス、レオンティーフユーティリティ関数に対して改善された後悔とサンプルの複雑さ境界を与える。
関連論文リスト
- Refined Risk Bounds for Unbounded Losses via Transductive Priors [58.967816314671296]
線形回帰の逐次変分を2乗損失、ヒンジ損失の分類問題、ロジスティック回帰で再検討する。
我々の鍵となるツールは、慎重に選択された導出先を持つ指数重み付けアルゴリズムに基づいている。
論文 参考訳(メタデータ) (2024-10-29T00:01:04Z) - LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。
我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
論文 参考訳(メタデータ) (2024-08-12T17:08:31Z) - Generalization Analysis for Contrastive Representation Learning [80.89690821916653]
既存の一般化誤差境界は負の例の数$k$に線形に依存する。
対数項まで$k$に依存しないコントラスト学習のための新しい一般化境界を確立する。
論文 参考訳(メタデータ) (2023-02-24T01:03:56Z) - Omnipredictors for Constrained Optimization [5.969079530101132]
本稿では,制約付き最適化問題に対するオムニプレクタの獲得方法を示す。
また、使用する制約がいわゆる群フェアネスの概念である場合に、この概念がもたらす意味についても検討する。
論文 参考訳(メタデータ) (2022-09-15T17:04:49Z) - Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for
Full-Batch GD [31.80268332522017]
我々は、スムーズな損失(おそらく非Lipschitz)に対するフルバッチグラディエントデセント(GD)に対して、鋭い経路依存および過大なエラー保証を提供する。
我々の全バッチ一般化誤差と過剰リスク境界は、損失が滑らかである(しかし、おそらく非リプシッツ)GDの既存の境界よりもかなり厳密である。
論文 参考訳(メタデータ) (2022-04-26T17:05:57Z) - Sparsest Univariate Learning Models Under Lipschitz Constraint [31.28451181040038]
一次元回帰問題に対する連続領域定式化を提案する。
リプシッツ定数をユーザ定義上界を用いて明示的に制御する。
いずれの問題も、連続的かつ断片的線形なグローバル最小化を許容していることが示される。
論文 参考訳(メタデータ) (2021-12-27T07:03:43Z) - Reinforcement Learning in Linear MDPs: Constant Regret and
Representation Selection [136.4014229319618]
線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。
まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
論文 参考訳(メタデータ) (2021-10-27T22:07:08Z) - Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。
主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。
このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
論文 参考訳(メタデータ) (2021-05-08T11:43:49Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
我々はReLU回帰の根本的な問題を考察する。
目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
論文 参考訳(メタデータ) (2020-05-26T16:26:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。