論文の概要: Tight Generalization Bounds for Noiseless Inverse Optimization

• arxiv url: http://arxiv.org/abs/2605.08866v1
• Date: Sat, 09 May 2026 10:33:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:49.940415
• Title: Tight Generalization Bounds for Noiseless Inverse Optimization
• Title（参考訳）: ノイズレス逆最適化のためのタイト一般化境界
• Abstract要約: 逆最適化(IO)は、観測されたコンテキスト-アクションデータから意思決定者の目的のパラメータを推測する。 誘導されたアクションセットに対して高確率の$O(fracdT)$boundを提供し、$d$は未知のパラメータの数で、$T$はトレーニングデータセットのサイズです。 我々は、$O(fracdT)$レートが、ここで考慮されたすべての一貫した推定値に対して厳密であることを示し、その結果を、即時および累積的後悔の両方に拡張する。
• 参考スコア（独自算出の注目度）: 20.72173263660803
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inverse optimization (IO) seeks to infer the parameters of a decision-maker's objective from observed context--action data. We study noiseless IO, where demonstrations are generated by a ground-truth objective. We provide a high-probability ${O}(\frac{d}{T})$ generalization bound for the induced action set, where $d$ is the number of unknown parameters and $T$ is the size of the training dataset. We strengthen these guarantees under additional conditions that ensure uniqueness of the chosen action, bringing our IO guarantees in line with best-arm identification results in the bandit literature. We further show that the ${O}(\frac{d}{T})$ rate is tight over all consistent estimators considered here, and extend the result to both instantaneous and cumulative regret. Notably, the resulting regret lower bound matches the corresponding upper bounds in the adversarial setting, indicating that the stochastic IO setting is effectively adversarial for the class of estimators studied here. Finally, we propose a parameter-free algorithm with lower per-iteration complexity than generic solvers. Experiments validate the predicted rates and illustrate the tightness of our bounds.
• Abstract（参考訳）: 逆最適化(IO)は、観測されたコンテキスト-アクションデータから意思決定者の目的のパラメータを推測する。 本研究では,実演を地上目標から生成するノイズレスIOについて検討する。 高確率${O}(\frac{d}{T})$ generalization bound for the induced action set, where $d$ is the number of unknown parameters and $T$ is the size of the training dataset。 我々は,これらの保証を,選択した行動の独特性を保証する追加条件の下で強化し,盗賊文学における最高の武器識別結果と一致したIO保証を実現する。 さらに、${O}(\frac{d}{T})$ はここで考慮された全ての一貫した推定値に対して厳密であることを示し、その結果を即時および累積的後悔に拡張する。 特に、結果として生じる後悔の下位境界は、逆向きの設定における対応する上界と一致し、確率的IO設定がここで研究される推定値のクラスに対して効果的に逆であることを示す。 最後に,一般解法よりも解数毎の複雑性が低いパラメータフリーアルゴリズムを提案する。 実験は予測された速度を検証し、境界の厳密さを示す。

関連論文リスト

• Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
  ブラックボックス最適化は勾配が利用できない場合に適用され、客観的評価は高価なシミュレーションに依存する。 本稿では, オラクル型, ノイズモデル, 最適化方式の選択が, アルゴリズムパラメータに対する壁面最適選択をいかに引き起こすかを示す。
  論文  参考訳（メタデータ） (2026-05-29T14:24:54Z)
• DARTS: Targeting Prognostic Covariates in Budget-Constrained Sequential Experiments [47.61857875238484]
  我々はトンプソンサンプリング(DARTS)による動的適応的ランダム化を導入する。 DARTSは、共変量取得を設計に基づく因果推論タスクに埋め込まれた逐次最適化問題として扱う。 我々は,最小限の値と対数的因子とを一致させる獲得層に対してベイズリスクを導出する。
  論文  参考訳（メタデータ） (2026-05-07T17:27:51Z)
• Estimation of Toeplitz Covariance Matrices using Overparameterized Gradient Descent [1.7188280334580195]
  単純降下レンズ(GD)によるToeplitz共分散推定の再検討 K = P$ のとき、GD は準最適解に収束する。 本稿では,振幅と周波数の学習率の異なる高速なGD変種を提案する。
  論文  参考訳（メタデータ） (2025-11-03T14:07:53Z)
• Constrained Linear Thompson Sampling [39.724313550777715]
  Constrained Linear Thompson Sampling (COLTS)は、摂動線形プログラムを解くことでアクションを選択するサンプリングベースのフレームワークである。 S-COLTSはゼロリスクと$widetildeO(sqrtd3 T)を許容するが、R-COLTSは$widetildeO(sqrtd3 T)を許容する。
  論文  参考訳（メタデータ） (2025-03-03T20:44:58Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Adaptive importance sampling for heavy-tailed distributions via $\alpha$-divergence minimization [2.879807093604632]
  提案手法は,学生の提案分布からターゲットを近似するAISアルゴリズムを提案する。 我々は、目標と提案の護衛モーメントを一致させて、位置とスケールパラメータを適応させる。 これらの更新は、ターゲットと提案の間の$alpha$-divergenceを最小化し、変動推論と接続する。
  論文  参考訳（メタデータ） (2023-10-25T14:07:08Z)
• Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
  文脈的包帯では、エージェントは過去の経験に基づいた時間依存アクションセットから順次アクションを行う。 そこで本稿では,文脈的包帯のためのオンライン連続型ハイパーパラメータチューニングフレームワークを提案する。 理論上はサブ線形の後悔を達成でき、合成データと実データの両方において既存のすべての手法よりも一貫して優れた性能を発揮することを示す。
  論文  参考訳（メタデータ） (2023-02-18T23:31:20Z)
• Adaptive Noisy Data Augmentation for Regularized Estimation and Inference in Generalized Linear Models [15.817569026827451]
  一般化線形モデル(GLM)の推定と推定を規則化するAdaPtive Noise Augmentation (PANDA) 手法を提案する。 シミュレーションおよび実生活データにおいて,同一タイプの正則化器の既存手法に対して,PANDAが優れているか類似した性能を示す。
  論文  参考訳（メタデータ） (2022-04-18T22:02:37Z)
• Partial Identification with Noisy Covariates: A Robust Optimization Approach [94.10051154390237]
  観測データセットからの因果推論は、しばしば共変量の測定と調整に依存する。 このロバストな最適化手法により、広範囲な因果調整法を拡張し、部分的同定を行うことができることを示す。 合成および実データセット全体で、このアプローチは既存の手法よりも高いカバレッジ確率でATEバウンダリを提供する。
  論文  参考訳（メタデータ） (2022-02-22T04:24:26Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Adversarial Robustness Guarantees for Gaussian Processes [22.403365399119107]
  ガウス過程(GP)は、モデルの不確実性の原理的計算を可能にし、安全性に重要なアプリケーションに魅力的です。 境界付き摂動に対するモデル決定の不変性として定義されるGPの対向的堅牢性を分析するためのフレームワークを提案する。 我々は境界を洗練し、任意の$epsilon > 0$に対して、我々のアルゴリズムが有限個の反復で実際の値に$epsilon$-closeの値に収束することを保証していることを示す分岐とバウンドのスキームを開発する。
  論文  参考訳（メタデータ） (2021-04-07T15:14:56Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。 LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
  論文  参考訳（メタデータ） (2021-03-19T13:10:47Z)
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards [24.983866845065926]
  我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。 本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。 提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
  論文  参考訳（メタデータ） (2020-10-24T10:44:02Z)

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

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