論文の概要: Learning-augmented smooth integer programs with PAC-learnable oracles

• arxiv url: http://arxiv.org/abs/2602.02505v1
• Date: Thu, 22 Jan 2026 05:55:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 02:03:42.408617
• Title: Learning-augmented smooth integer programs with PAC-learnable oracles
• Title（参考訳）: PAC学習可能なオラクルを用いた学習補助スムーズ整数プログラム
• Authors: Hao-Yuan He, Ming Li,
• Abstract要約: 予測オラクルを組み込んだフレームワークを導入し、目的の線形サロゲートを構築し、線形プログラミングによって解決する。 提案手法は,古典的な高密度政権から近距離政権へ効果的にトラクタブル近似を拡張できることを実証する。 帰納的アルゴリズムが有界擬似次元を持つことを証明し、ほぼ最適性能のオラクルを学習できるようにする。
• 参考スコア（独自算出の注目度）: 6.4126799144358975
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper investigates learning-augmented algorithms for smooth integer programs, covering canonical problems such as MAX-CUT and MAX-k-SAT. We introduce a framework that incorporates a predictive oracle to construct a linear surrogate of the objective, which is then solved via linear programming followed by a rounding procedure. Crucially, our framework ensures that the solution quality is both consistent and smooth against prediction errors. We demonstrate that this approach effectively extends tractable approximations from the classical dense regime to the near-dense regime. Furthermore, we go beyond the assumption of oracle existence by establishing its PAC-learnability. We prove that the induced algorithm class possesses a bounded pseudo-dimension, thereby ensuring that an oracle with near-optimal expected performance can be learned with polynomial samples.
• Abstract（参考訳）: 本稿では, MAX-CUT や MAX-k-SAT などの標準問題をカバーするスムーズな整数プログラムの学習拡張アルゴリズムについて検討する。 予測オラクルを組み込んだフレームワークを導入し,対象の線形サロゲートを構築する。 重要なことは、我々のフレームワークは、ソリューションの品質が予測エラーに対して一貫性があり、スムーズであることを保証する。 提案手法は,古典的な高密度政権から近距離政権へ効果的にトラクタブル近似を拡張できることを実証する。 さらに、私たちはPAC学習可能性を確立することで、オラクルの存在を仮定する超越した。 帰納的アルゴリズムクラスが有界擬似次元を持つことを証明し、多項式サンプルを用いてほぼ最適性能のオラクルを学べるようにした。

関連論文リスト

• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  等式制約と不等式制約を持つ2次最適化問題の解に対するオンライン統計的推測について検討した。 これらの問題を解決するための逐次プログラミング(SSQP)手法を開発し、目的の近似と制約の線形近似を逐次実行することでステップ方向を計算する。 本手法は,Hjek と Le Cam の意味での最適原始双対制限行列を用いて局所正規性を示す。
  論文  参考訳（メタデータ） (2025-11-27T06:16:17Z)
• Learning based convex approximation for constrained parametric optimization [11.379408842026981]
  本稿では、制約付き最適化問題を解決するために、入力ニューラルネットワーク(ICNN)に基づく自己教師付き学習フレームワークを提案する。 厳密な収束解析を行い、このフレームワークが元の問題のKKT近似点に収束することを示す。 提案手法は精度,実現可能性,計算効率の両立を実現している。
  論文  参考訳（メタデータ） (2025-05-07T00:33:14Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
  従来のアルゴリズムの近似保証よりも高い精度で予測を行う。 我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。 この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
  論文  参考訳（メタデータ） (2024-11-25T17:31:34Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models [6.54203362045253]
  本研究では,連続観測データから有向非巡回グラフを学習する問題について検討する。 中規模の問題を学習するための混合整数プログラミングフレームワークを開発した。 提案手法は最先端のアルゴリズムより優れ,ノイズの不均一性に対して頑健である。
  論文  参考訳（メタデータ） (2024-04-19T02:42:13Z)
• Learning-Augmented Algorithms for Online Linear and Semidefinite Programming [9.849604820019394]
  Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。 SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。 予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
  論文  参考訳（メタデータ） (2022-09-21T19:16:29Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)

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

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