論文の概要: Kernel Methods for Refined Prophet Inequalities

• arxiv url: http://arxiv.org/abs/2608.08662v1
• Date: Sun, 09 Aug 2026 12:08:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:36.910508
• Title: Kernel Methods for Refined Prophet Inequalities
• Title（参考訳）: 補間預言不等式に対するカーネル法
• Abstract要約: 単選択預言不等式は、独立した非負の値が逐次現れる標準的なオンライン選択問題である。 単項預言不等式に対する一般的なカーネル法を開発した。
• 参考スコア（独自算出の注目度）: 27.407082709350707
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irrevocably select at most one. Classical single-threshold guarantees are tight in the worst case, but the hard instances that prove tightness are highly irregular: the prophet's advantage is driven by rare, very large realizations of the maximum. We refine this worst-case picture by imposing a bound on the relative variance of the prophet's value, $\mathrm{Var}(\max_{i\in[n]}X_i)/\mathbb E[\max_{i\in[n]}X_i]^2$. This yields a nonparametric complexity measure that interpolates between deterministic instances, where the full prophet value can be recovered, and the unrestricted worst-case regime. Our main technical contribution is a general kernel method for single-threshold prophet inequalities. The method represents an instance by the quantile function of the maximum and rewrites the payoff of a threshold as a linear kernel functional of this quantile. This turns the worst-case analysis into an infinite-dimensional convex program, restores strong minimax duality in quantile space, and reduces the bounded-variance adversary's problem to a one-parameter variational family. Applying this framework, we obtain an exact characterization of the IID bounded-variance curve and asymptotically optimal finite-horizon thresholds, a closed-form expression for the fixed-order non-identical model, and a prophet-secretary lower-bound program together with a strict separation from the IID benchmark at every positive finite variance constraint. As a further application of the same kernel viewpoint, we derive an exact formula for IID random horizons under a convexity condition on the horizon pgf, which includes monotone-hazard-rate horizons, highlighting the broad applicability of this new technique for single threshold settings.
• Abstract（参考訳）: 単選択の預言者不平等は、独立した非負の値が連続的に届き、意思決定者は、ほとんどの場合、不可解に選択しなければならない、標準的なベイズオンライン選択問題である。 古典的な単一閾値保証は最悪の場合、厳密である。しかし、厳密性を証明する難しい事例は非常に不規則である:預言者の利点は、極大の稀で非常に大きな実現によって引き起こされる。 我々は、この最悪のケース図を、預言者の値の相対的分散($\mathrm{Var}(\max_{i\in[n]}X_i)/\mathbb E[\max_{i\in[n]}X_i]^2$)に限定することで洗練する。 これは非パラメトリックな複雑性尺度であり、完全な預言を回復できる決定論的インスタンスと、制限されない最悪の場合の状態を補間する。 我々の主な技術的貢献は、単一閾値の預言不等式に対する一般的なカーネル手法である。 この方法は最大値の量子関数でインスタンスを表現し、しきい値のペイオフをこの量子関数の線形カーネル関数として書き直す。 これにより、最悪のケース解析は無限次元凸プログラムに変換され、量子空間における強いミニマックス双対性を復元し、有界分散逆問題から1パラメータの変動族へと還元される。 この枠組みを適用すると、IIDの有界分散曲線と漸近的に最適な有限水平しきい値、固定階の非同一性モデルに対する閉形式表現、および全ての正の有限分散制約におけるIIDベンチマークからの厳密な分離を伴う預言的秘密的下界プログラムを正確に評価することができる。 同じカーネル視点のさらなる応用として、モノトーン・ハザードレートの地平線を含む水平pgf上の凸条件下でのIDDランダムな地平線の正確な式を導出し、この新手法の単一しきい値設定への適用性を強調した。

関連論文リスト

• A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition [39.146761527401424]
  本研究は,期待されるコストの和を最小化するための近位次法を導入する。 クルディカ・ロジャシエヴィチ(KL)特性を用いて、全軌道の1つの定常点への収束を保証する。
  論文  参考訳（メタデータ） (2026-08-05T23:07:27Z)
• Quadratic Objective Perturbation: Curvature-Based Differential Privacy [0.14323566945483496]
  擬似目的摂動(QOP)を導入し、ランダムな二次形式で目的を摂動する。 この摂動は強い凸性をもたらし、曲率によって問題の安定性を強制する。 この分析を近似解に拡張し、不正確な解決の下でプライバシ保証が保存されていることを示す。
  論文  参考訳（メタデータ） (2026-05-07T09:16:53Z)
• Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints [3.567855687957749]
  この研究は、一階法のみを用いた線形制約付き双レベル最適化に対する最初の有限時間収束保証を提供する。 線形制約、雑音、有限時間解析を両レベル最適化において同時に扱うという前例のない課題に対処する。
  論文  参考訳（メタデータ） (2025-11-13T00:59:20Z)
• Derivative-Free Sequential Quadratic Programming for Equality-Constrained Stochastic Optimization [3.2489082010225485]
  我々は、客観的で決定論的な等式制約で非線形最適化問題を解くことを検討する。 本稿では,DF-SSQP法を提案する。 標準仮定では,提案したDF-SSQP法を大域的にほぼ収束させる。
  論文  参考訳（メタデータ） (2025-10-25T23:51:20Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  演算子を期待値とする単調な包摂問題を考える。 分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。 本稿では,不確実性に対処する手法を提案する。
  論文  参考訳（メタデータ） (2020-08-26T02:33:27Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)

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

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