論文の概要: Dimension-Free Decision Calibration for Nonlinear Loss Functions

• arxiv url: http://arxiv.org/abs/2504.15615v1
• Date: Tue, 22 Apr 2025 06:14:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-30 22:10:13.806478
• Title: Dimension-Free Decision Calibration for Nonlinear Loss Functions
• Title（参考訳）: 非線形損失関数に対する次元自由決定校正法
• Authors: Jingwu Tang, Jiayun Wu, Zhiwei Steven Wu, Jiahao Zhang,
• Abstract要約: 高次元予測結果空間のキャリブレーションには指数計算と統計的複雑さが必要である。 我々は、$mathrmpoly(|A|,1/epsilon)$サンプルを与えられたアルゴリズムを効率よく後処理し、精度を悪化させることなく決定キャリブレーションを満足するアルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 27.879384242436835
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When model predictions inform downstream decision making, a natural question is under what conditions can the decision-makers simply respond to the predictions as if they were the true outcomes. Calibration suffices to guarantee that simple best-response to predictions is optimal. However, calibration for high-dimensional prediction outcome spaces requires exponential computational and statistical complexity. The recent relaxation known as decision calibration ensures the optimality of the simple best-response rule while requiring only polynomial sample complexity in the dimension of outcomes. However, known results on calibration and decision calibration crucially rely on linear loss functions for establishing best-response optimality. A natural approach to handle nonlinear losses is to map outcomes $y$ into a feature space $\phi(y)$ of dimension $m$, then approximate losses with linear functions of $\phi(y)$. Unfortunately, even simple classes of nonlinear functions can demand exponentially large or infinite feature dimensions $m$. A key open problem is whether it is possible to achieve decision calibration with sample complexity independent of~$m$. We begin with a negative result: even verifying decision calibration under standard deterministic best response inherently requires sample complexity polynomial in~$m$. Motivated by this lower bound, we investigate a smooth version of decision calibration in which decision-makers follow a smooth best-response. This smooth relaxation enables dimension-free decision calibration algorithms. We introduce algorithms that, given $\mathrm{poly}(|A|,1/\epsilon)$ samples and any initial predictor~$p$, can efficiently post-process it to satisfy decision calibration without worsening accuracy. Our algorithms apply broadly to function classes that can be well-approximated by bounded-norm functions in (possibly infinite-dimensional) separable RKHS.
• Abstract（参考訳）: モデル予測が下流での意思決定を知らせるとき、自然な質問は、意思決定者が予測に、まるでそれが真の結果であるかのように応答できる条件の下にある。 キャリブレーションは、予測に対する単純なベストレスポンスが最適であることを保証するのに十分です。 しかし、高次元予測結果空間のキャリブレーションには指数計算と統計的複雑さが必要である。 決定キャリブレーション(Deciment calibration)として知られる最近の緩和は、結果の次元において多項式サンプルの複雑さのみを必要としながら、単純なベストレスポンスルールの最適性を保証する。 しかし、キャリブレーションと決定キャリブレーションの既知の結果は、最適応答性を確立するために線形損失関数に大きく依存している。 非線形損失を扱う自然なアプローチは、結果が$y$ を特徴空間 $\phi(y)$ 次元 $m$ に写像し、それから$\phi(y)$ の線型関数で近似損失を近似することである。 残念なことに、非線形関数の単純なクラスでさえ指数関数的に大きなあるいは無限の特徴次元を$m$で要求することができる。 鍵となる開問題は、–$m$から独立にサンプル複雑性で決定キャリブレーションを達成できるかどうかである。 標準決定論的最適応答の下で決定キャリブレーションを検証することさえも、本質的には–$m$のサンプル複雑性多項式を必要とする。 この下限により、意思決定者がスムーズな最良応答に従うような意思決定校正のスムーズなバージョンについて検討する。 このスムーズな緩和により、次元自由決定キャリブレーションアルゴリズムが実現される。 我々は、$\mathrm{poly}(|A|,1/\epsilon)$サンプルと任意の初期予測子~$p$を与えられたアルゴリズムを導入し、精度を悪化させることなく、決定校正を効率的に後処理することができる。 我々のアルゴリズムは、(無限次元の)分離可能な RKHS における有界ノルム関数によってよく近似できる関数クラスに広く適用される。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes [80.89852729380425]
  そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。 我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
  論文  参考訳（メタデータ） (2022-12-12T18:58:59Z)
• Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration [118.26862029820447]
  我々は、下流の意思決定者に対して、予測された分布と真の分布を区別不能にする必要がある新しい概念、即時校正を導入します。 決定キャリブレーションは、皮膚病変の判定と、現代のニューラルネットワークを用いたImageNet分類を改善する。
  論文  参考訳（メタデータ） (2021-07-12T20:17:28Z)
• Adiabatic Quantum Feature Selection for Sparse Linear Regression [0.17499351967216337]
  合成および実世界のデータセット上でQUBOソリューションの品質を定式化し比較する。 その結果, 最適解を求める上で, 提案した断熱量子コンピューティング手法の有効性が示された。
  論文  参考訳（メタデータ） (2021-06-04T09:14:01Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Extracting Optimal Solution Manifolds using Constrained Neural Optimization [6.800113407368289]
  制約付き最適化解アルゴリズムは点ベース解に制限される。 最適集合を近似として抽出する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-13T15:37:44Z)
• Tightly Robust Optimization via Empirical Domain Reduction [22.63829081634384]
  提案手法は,解が良好な目的値を持つようなスケールを決定するアルゴリズムである。 いくつかの規則性条件下では、我々のアルゴリズムで得られるスケールは$O(sqrtn)$、標準アプローチで得られるスケールは$O(sqrtd/n)$である。
  論文  参考訳（メタデータ） (2020-02-29T12:24:56Z)

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

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