論文の概要: Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2605.14019v1
• Date: Wed, 13 May 2026 18:32:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-15 21:45:34.45581
• Title: Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization
• Title（参考訳）: Regret Equals Covariance:確率最適化のためのクローズドフォームキャラクタリゼーション
• Authors: Irene Aldridge,
• Abstract要約: 後悔の定量化はアルゴリズムによる意思決定の不確実性のコストである。 本稿では,任意の最適化問題における期待された後悔が,正確な分解を許容することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regret is the cost of uncertainty in algorithmic decision-making. Quantifying regret typically requires computationally expensive simulation via Sample Average Approximation (SAA), with complexity $\mathcal{O}(Bn^{2}d^{3})$ in the number of scenarios $B$, variables $n$, and constraints $d$. % This paper proves that expected regret in any stochastic optimization problem admits the exact decomposition % \begin{equation*} \mathrm{Regret}(c) = \mathrm{Cov}(c,\,π^{*}(c)) + R(c), \end{equation*} % where $c$ is the vector of uncertain parameters, $π^{*}(c)$ is the optimal decision, and $R(c)$ is a residual whose magnitude we bound explicitly under Lipschitz, smooth, and strongly convex conditions. % For linear programs and unconstrained quadratic programs, including the classical Markowitz portfolio problem, we prove $R(c)=0$ exactly, so that $\mathrm{Regret}(c) = \mathrm{Cov}(c,π^{*}(c))$ holds without approximation. % When historical cost-decision pairs $\{(c_i, π^*(c_i))\}$ are available, the covariance can be estimated in $\mathcal{O}(nd^{2})$ time, which is orders of magnitude faster than SAA. The estimation is performed by a single pass through the data. % We derive concentration bounds, a central limit theorem, and an asymptotically unbiased residual estimator, and we validate all results on synthetic LP, QP, and integer programming instances and on a rolling-window portfolio experiment using ten years of CRSP equity data.
• Abstract（参考訳）: レグレト(Regret)とは、アルゴリズムによる意思決定における不確実性のコストである。 後悔の定量化には、通常、Sample Average Approximation (SAA) による計算コストのかかるシミュレーションが必要であり、複雑さは$\mathcal{O}(Bn^{2}d^{3})$で、シナリオの数は$B$、変数$n$、制約$d$である。 % 確率最適化問題における期待された後悔は、 % \begin{equation*} \mathrm{Regret}(c) = \mathrm{Cov}(c,\,π^{*}(c)) + R(c), \end{equation*} % であることを証明する。 % 古典的マルコウィッツポートフォリオ問題を含む線形プログラムや非制約二次プログラムに対して、$R(c)=0$を正確に証明し、$\mathrm{Regret}(c) = \mathrm{Cov}(c,π^{*}(c))$が近似なしで成り立つようにする。 % 歴史的コスト決定対 $\{(c_i, π^*(c_i))\}$ が利用可能であれば、共分散は $\mathcal{O}(nd^{2})$ time で推定できる。 推定は、データを1回のパスで行う。 % 濃度境界, 中心極限定理, 漸近的に偏りのない残差推定器を導出し, 合成LP, QP, 整数プログラミングインスタンスおよび10年間のCRSPエクイティデータを用いたロールウインドウポートフォリオ実験の結果を検証した。

関連論文リスト

• Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization [0.6015898117103067]
  我々は,条件付き予測を共同で推定し,外的目的を最適化する同時学習最適化アルゴリズムを解析する。 我々は,この手法が次数$mathcalObig (1/sqrtNbig)$の収束率を達成することを証明した。
  論文  参考訳（メタデータ） (2026-03-13T14:53:35Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
  実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。 さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
  論文  参考訳（メタデータ） (2023-11-09T14:29:25Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
  論文  参考訳（メタデータ） (2022-06-30T02:17:11Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates [0.0]
  コンパクト部分集合 $mathcal X$ of $mathbb Rd$ 上で定義されるリプシッツ関数 $f$ のゼロ次(ブラックボックス)最適化の問題を研究する。 我々は、任意のリプシッツ関数 $f$ の評価の最適な個数を特徴付け、精度$varepsilon$ で$f$ の近似器を見つけて証明する。
  論文  参考訳（メタデータ） (2021-02-03T09:51:03Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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