論文の概要: Eigenvalue-Decomposition Cost Denoising as an Alternative to Predict-then-Optimize for Shortest-Path Problems
- arxiv url: http://arxiv.org/abs/2609.15111v1
- Date: Mon, 14 Sep 2026 06:41:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 07:15:06.12121
- Title: Eigenvalue-Decomposition Cost Denoising as an Alternative to Predict-then-Optimize for Shortest-Path Problems
- Title（参考訳）: 最短パス問題に対する予測最適化の代替としての固有値分解コスト
- Abstract要約: 具体的だが一般的な設定に対して,構造的に異なる治療法を提案し,評価する。
意思決定者が同じコストプロセスの多くのノイズを観測すると、実現されたコスト自体をノイズ信号として扱うことができる。
k=2$の固有ベクトルしか持たず、実際の信号を破棄し、ノイズの多いコストベースラインでさえ過小評価する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Predict-then-optimize methods such as Smart "Predict, then Optimize" (SPO+) of Elmachtoub and Grigas (2022) learn a mapping from contextual features to unknown edge costs and then solve the induced combinatorial problem on the predicted costs. This approach is powerful but relies on the predictive model being well specified: when the true cost-generating process is nonlinear in the features and the predictor is linear, SPO+'s performance degrades as the misspecification grows. We propose and evaluate a structurally different remedy for a specific but common setting: when the decision-maker observes many noisy realizations of the same underlying cost process, the realized cost vectors themselves can be treated as a noisy signal and denoised directly, via eigenvalue decomposition (equivalently, Principal Component Analysis) of their covariance matrix, before ever invoking a predictive model. We instantiate this idea on the $5\times5$ grid shortest-path benchmark introduced by Elmachtoub and Grigas (2022), retaining only the top-$k$ eigenvectors of the training cost covariance matrix and projecting new noisy cost observations onto that subspace prior to solving with Dijkstra's (1959) algorithm. We find that the choice of $k$ is decisive: keeping only $k{=}2$ eigenvectors discards real signal and underperforms even the naive noisy-cost baseline, while setting $k{=}5$ to match the true latent feature dimension makes eigenvalue-denoised Dijkstra the best-performing method at every misspecification level tested, outperforming SPO+ by a wide margin under high misspecification.
- Abstract（参考訳）: Elmachtoub と Grigas (2022) の Smart "Predict, then Optimize" (SPO+) のような予測最適化手法は、文脈的特徴から未知のエッジコストへのマッピングを学習し、予測コストに関する帰納的組合せ問題を解く。
真のコスト発生過程が特徴において非線形であり、予測器が線形であるとき、SPO+の性能は、誤特定が大きくなるにつれて劣化する。
決定者が同じコストプロセスの多くのノイズを観測すると、実現されたコストベクトル自体がノイズ信号として扱われ、それらの共分散行列の固有値分解(主成分分析)を介して直接分解され、予測モデルが起動される。
このアイデアを、Elmachtoub と Grigas (2022) が導入した 5\times5$ grid shortest-path ベンチマーク(英語版) 上でインスタンス化し、トレーニングコスト共分散行列の上位 k$ eigenvector のみを保持し、ダイクストラ (1959) アルゴリズムで解く前に、その部分空間に新しいノイズの多いコスト観測を投影する。
k{=}2$ eigenvectors は実信号を捨て、ノイズの多いコストのベースラインでさえ過小評価されるのに対して、$k{=}5$ は真の潜在特徴次元と一致するように設定し、固有値をデノベートした Dijkstra は、テストされたすべての不特定度において最高のパフォーマンスの方法となり、SPO+ を高い不特定度で上回ります。
関連論文リスト
- Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback [14.912614425471915]
決定中心学習(DFL)は、スタンドアロンの予測精度よりも下流の意思決定品質を最適化することで予測モデルを訓練する。
文脈線形最適化では、既存のDFL法は対象ベクトルの完全な観測をオフラインで行う。
条件分布モデルを更新するための2成分ハイブリッド推定器を提案する。
論文 参考訳（メタデータ） (2026-05-31T07:58:28Z) - Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
我々は、この問題を*予算付きヘテロスケダティックなマルチジャッジ推定*として定式化する。
K$のプロンプト-レスポンスペア、J$の既知のコストと未知のクエリ-ジャッジ分散が与えられた場合、目標は、$ell_p$-errorを最小化しながら、有界スコアベクトルを推定することである。
EST-IVWEは,予算の低次項までのオラクルIVWEレートと一致していることを示す。
論文 参考訳（メタデータ） (2026-05-22T08:26:08Z) - Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを考察する。
鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。
我々は、$(sqrtmathbbE[S_T])$としてスケールする情報理論の下限を確立し、最も達成可能な予測適応的後悔の基本的な特徴を提供する。
論文 参考訳（メタデータ） (2026-05-21T08:57:38Z) - Model Compression with Exact Budget Constraints via Riemannian Manifolds [39.54576236079211]
トータルコスト予算の下で各NグループにKオプションの1つを割り当てることは、効率的なAIにおいて繰り返し発生する問題である。
我々は、ソフトマックス緩和の下で、予算制約がロジット空間における滑らかなリーマン多様体を異常に単純な幾何学で定義することを示す新しいアプローチを示す。
これらの特性に基づいて、接射影、二分探索リトラクション、運動量輸送を標準とするリーマン制約最適化(RCO)を提案する。
論文 参考訳（メタデータ） (2026-05-01T13:30:23Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳（メタデータ） (2026-02-19T17:21:15Z) - Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs [3.1269598124014264]
ランダムで未知のコストでBOCVS問題を拡張するための新しいアルゴリズムを提案する。
提案アルゴリズムは,BOCVS問題の目的を従来よりも効果的に解決し,品質的後悔とコスト的後悔の両面において,サブ線形率を達成する。
論文 参考訳（メタデータ） (2024-12-20T13:00:39Z) - Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization [27.33243506775655]
凸とリプシッツ損失関数の基本的な場合に焦点を当てる。
本稿では,この問題の複雑さと関連する学習モデルとの関連性に光を当てた,いくつかの新たな理論的結果を示す。
結果は,ベクトル値線形予測の設定を,広範に研究されている2つの異なる学習モデル間のブリッジングとして表現した。
論文 参考訳（メタデータ） (2024-12-05T15:56:54Z) - Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
線形回帰の逐次変分を2乗損失、ヒンジ損失の分類問題、ロジスティック回帰で再検討する。
我々の鍵となるツールは、慎重に選択された導出先を持つ指数重み付けアルゴリズムに基づいている。
論文 参考訳（メタデータ） (2024-10-29T00:01:04Z) - Contextual Linear Optimization with Partial Feedback [35.38485630117593]
本研究では,異なるタイプのフィードバックを持つ文脈線形最適化(CLO)のためのオフライン学習アルゴリズムのクラスを提案する。
我々は,IERMに対して,不特定モデルクラスとフレキシブルな推定方法の選択を可能にする,新しい高速遅延境界を提供する。
論文 参考訳（メタデータ） (2024-05-26T13:27:27Z) - Transformers as Support Vector Machines [54.642793677472724]
自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。
勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。
これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
論文 参考訳（メタデータ） (2023-08-31T17:57:50Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Estimating Principal Components under Adversarial Perturbations [25.778123431786653]
本研究では,高次元統計的推定問題に対するロバストネスの自然なモデルについて検討する。
我々のモデルは、低精度機械学習や対人訓練といった新しいパラダイムによって動機付けられている。
論文 参考訳（メタデータ） (2020-05-31T20:27:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。