論文の概要: Omnipredictors for Constrained Optimization
- arxiv url: http://arxiv.org/abs/2209.07463v1
- Date: Thu, 15 Sep 2022 17:04:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-16 13:45:42.000720
- Title: Omnipredictors for Constrained Optimization
- Title（参考訳）: 制約付き最適化のためのOmnipredictors
- Authors: Lunjia Hu, Inbal Livni-Navon, Omer Reingold, Chutong Yang
- Abstract要約: 本稿では,制約付き最適化問題に対するオムニプレクタの獲得方法を示す。
本稿では, 従来のマルチキャリブレーションに類似したマルチキャリブレーションの変種によって, オムニプレクタがどのような意味を持つかを示す。
また、制約が群フェアネスの概念である場合についても検討する。
- 参考スコア（独自算出の注目度）: 5.969079530101132
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The notion of omnipredictors (Gopalan, Kalai, Reingold, Sharan and Wieder
ITCS 2021), suggested a new paradigm for loss minimization. Rather than
learning a predictor based on a known loss function, omnipredictors can easily
be post-processed to minimize any one of a rich family of loss functions
compared with the loss of a class $C$. It has been shown that such
omnipredictors exist and are implied (for all convex and Lipschitz loss
functions) by the notion of multicalibration from the algorithmic fairness
literature. Nevertheless, it is often the case that the action selected must
obey some additional constraints (such as capacity or parity constraints). In
itself, the original notion of omnipredictors does not apply in this
well-motivated and heavily studied the context of constrained loss
minimization.
In this paper, we introduce omnipredictors for constrained optimization and
study their complexity and implications. The notion that we introduce allows
the learner to be unaware of the loss function that will be later assigned as
well as the constraints that will be later imposed, as long as the
subpopulations that are used to define these constraints are known.
The paper shows how to obtain omnipredictors for constrained optimization
problems, relying on appropriate variants of multicalibration. For some
interesting constraints and general loss functions and for general constraints
and some interesting loss functions, we show how omnipredictors are implied by
a variant of multicalibration that is similar in complexity to standard
multicalibration. We demonstrate that in the general case, standard
multicalibration is insufficient and show that omnipredictors are implied by
multicalibration with respect to a class containing all the level sets of
hypotheses in $C$. We also investigate the implications when the constraints
are group fairness notions.
- Abstract（参考訳）: オムニプレクタ(Gopalan, Kalai, Reingold, Sharan, Wieder ITCS 2021)の概念は、損失最小化のための新しいパラダイムを提唱した。
既知の損失関数に基づいて予測子を学習する代わりに、omnipredictorは、クラス$c$の損失と比較して、損失関数の豊富な族のいずれかを最小化するために、後処理が容易である。
そのような全方位予測子は、アルゴリズム的公正文学からの多重校正の概念により(すべての凸関数とリプシッツ損失関数に対して)存在することが示されている。
それでも、選択されたアクションがいくつかの追加の制約(キャパシティやパリティの制約など)に従う必要がある場合が多い。
それ自体、Omnipredictor の本来の概念は、このよく動機づけられた、制約された損失最小化の文脈を深く研究するには適用されない。
本稿では,制約付き最適化のためのomnipredictorを導入し,その複雑性と影響について検討する。
私たちが導入する概念により、学習者は、後に割り当てられる損失関数と、これらの制約を定義するために使用されるサブポピュレーションが分かっている限り、後から課される制約を知らないことができる。
本論文は,制約付き最適化問題に対する全予測器の獲得方法を示す。
いくつかの興味深い制約と一般損失関数、および一般的な制約といくつかの興味深い損失関数について、標準多重化と複雑に類似した多重化の変種によって、omnipredictorがどのように含んでいるかを示す。
一般の場合、標準の多重校正は不十分であり、すべての仮説のレベルセットを$C$で含むクラスに対して、全単項述語が多重校正によって暗示されることを示す。
また,制約がグループフェアネス概念である場合の意味についても検討する。
関連論文リスト
- Swap Agnostic Learning, or Characterizing Omniprediction via
Multicalibration [6.91367883100748]
我々は,Swap Agnostic Learningを導入し,研究する。
敵の強みにも拘わらず,あらゆる凸損失に対するスワップ・アグノスティック・ラーニングの実現可能性を示す。
論文 参考訳（メタデータ） (2023-02-13T22:25:53Z) - Loss Minimization through the Lens of Outcome Indistinguishability [11.709566373491619]
我々は凸損失と最近のOmnipredictionの概念について新しい視点を提示する。
設計上、Los OIは直感的かつ直感的に全滅を意味する。
一般化モデルから生じる損失の重要な集合に対する損失 OI は、完全な多重校正を必要としないことを示す。
論文 参考訳（メタデータ） (2022-10-16T22:25:27Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。
本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。
実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文 参考訳（メタデータ） (2022-02-22T18:37:23Z) - Lazy Lagrangians with Predictions for Online Learning [24.18464455081512]
オンライン凸最適化における時間的差分制約による一般的な問題について考察する。
Follow-The-Regularized-Leaderイテレーションと予測適応動的ステップを組み合わせることで、新しい原始双対アルゴリズムを設計する。
我々の研究は、この制約されたOCO設定のためのFTRLフレームワークを拡張し、各最先端のグレディベースのソリューションより優れています。
論文 参考訳（メタデータ） (2022-01-08T21:49:10Z) - Omnipredictors [19.735769148626588]
ロス最小化は機械学習において支配的なパラダイムである。
我々は家族の損失を最適化するために使用できる$mathcalL,mathcalC$)-omnipredictorの概念を紹介した。
このような「余分な知識」の学習は、多重校正とのつながりを通して実現可能であることを示す。
論文 参考訳（メタデータ） (2021-09-11T23:28:49Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds
for Episodic Reinforcement Learning [50.44564503645015]
有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。
楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
論文 参考訳（メタデータ） (2021-07-02T20:36:05Z) - Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。
主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。
このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
論文 参考訳（メタデータ） (2021-05-08T11:43:49Z) - PAC-Bayes unleashed: generalisation bounds with unbounded losses [12.078257783674923]
非有界損失関数を持つ学習問題に対する新しいPAC-Bayesian一般化法を提案する。
これにより、PAC-Bayes学習フレームワークの妥当性と適用性が拡張される。
論文 参考訳（メタデータ） (2020-06-12T15:55:46Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
我々はReLU回帰の根本的な問題を考察する。
目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
論文 参考訳（メタデータ） (2020-05-26T16:26:17Z) - Excursion Search for Constrained Bayesian Optimization under a Limited
Budget of Failures [62.41541049302712]
本稿では,所定の予算の失敗の関数として探索において許容されるリスクの量を制御する制御理論に基づく新しい意思決定者を提案する。
本アルゴリズムは, 種々の最適化実験において, 故障予算をより効率的に利用し, 一般に, 最先端の手法よりも, 後悔度を低くする。
論文 参考訳（メタデータ） (2020-05-15T09:54:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。