論文の概要: SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems

• arxiv url: http://arxiv.org/abs/2210.12547v1
• Date: Sat, 22 Oct 2022 20:42:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-25 15:05:11.762138
• Title: SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems
• Title（参考訳）: SurCo:Learning Linearは、組合せ非線形最適化の問題に対処する
• Authors: Aaron Ferber, Taoan Huang, Daochen Zha, Martin Schubert, Benoit Steiner, Bistra Dilkina, Yuandong Tian
• Abstract要約: 本稿では、線形サロゲートコストを学習し、元の非線形最適化問題に対する良い解を出力するSurCoを提案する。 SurCo-zeroは個々の非線形問題で動作し、SurCo-priorは問題のシャードで線形サロゲート予測器を訓練し、SurCo-hybridはオフラインでトレーニングされたモデルを使用して、SurCo-zeroのオンライン問題解決を温める。
• 参考スコア（独自算出の注目度）: 43.95592587141054
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization problems with expensive nonlinear cost functions and combinatorial constraints appear in many real-world applications, but remain challenging to solve efficiently. Existing combinatorial solvers like Mixed Integer Linear Programming can be fast in practice but cannot readily optimize nonlinear cost functions, while general nonlinear optimizers like gradient descent often do not handle complex combinatorial structures, may require many queries of the cost function, and are prone to local optima. To bridge this gap, we propose SurCo that learns linear Surrogate costs which can be used by existing Combinatorial solvers to output good solutions to the original nonlinear combinatorial optimization problem, combining the flexibility of gradient-based methods with the structure of linear combinatorial optimization. We learn these linear surrogates end-to-end with the nonlinear loss by differentiating through the linear surrogate solver. Three variants of SurCo are proposed: SurCo-zero operates on individual nonlinear problems, SurCo-prior trains a linear surrogate predictor on distributions of problems, and SurCo-hybrid uses a model trained offline to warm start online solving for SurCo-zero. We analyze our method theoretically and empirically, showing smooth convergence and improved performance. Experiments show that compared to state-of-the-art approaches and expert-designed heuristics, SurCo obtains lower cost solutions with comparable or faster solve time for two realworld industry-level applications: embedding table sharding and inverse photonic design.
• Abstract（参考訳）: 高価な非線形コスト関数と組合せ制約による最適化問題は、多くの現実世界のアプリケーションに現れるが、効率的な解決は困難である。 混合整数線形計画のような既存の組合せソルバは、実際には高速であるが、容易に非線形コスト関数を最適化することはできないが、勾配降下のような一般的な非線形オプティマイザは複雑な組合せ構造を処理せず、コスト関数の多くのクエリを必要とし、局所的なオプティマに近づいた。 このギャップを埋めるため,既存のコンビネータによる線形サーロゲートコストを学習し,非線形組合せ最適化問題に対する優れた解を出力し,勾配に基づく手法の柔軟性と線形組合せ最適化の構造を組み合わせたSurCoを提案する。 線形サロゲート解法を微分することで, 非線形損失を伴う線形サロゲートを終端的に学習する。 SurCo-zeroは個々の非線形問題に対して動作し、SurCo-priorは問題の分布に関する線形サロゲート予測器を、SurCo-hybridはオフラインでトレーニングされたモデルを使用してSurCo-zeroのオンライン問題解決を温める。 提案手法を理論的,実証的に解析し,スムーズな収束と性能向上を示す。 実験によると、最先端のアプローチや専門家が設計したヒューリスティックスと比較して、SurCoは2つの業界レベルのアプリケーション(テーブルシャーディングと逆フォトニックデザイン)に対して、同等またはより高速な解決時間で低コストのソリューションを得る。

関連論文リスト

• Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints [10.047668792033033]
  本稿では,オンライン凸最適化(OCO)フレームワークの時間的逆制約による一般化について検討する。 この問題では、凸判定セットから実行可能な動作を選択した後、各ラウンドのコスト関数とともに凸制約関数を$X,$とする。 我々は,一ラウンドに1回,線形プログラム(LP)ソルバに1回コールする*プロジェクションフリー*オンラインポリシーを提案する。
  論文  参考訳（メタデータ） (2025-01-28T13:04:32Z)
• Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information [48.784330281177446]
  学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。 本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。 このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
  論文  参考訳（メタデータ） (2023-07-18T04:29:16Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [56.92236659731376]
  本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。 決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
  論文  参考訳（メタデータ） (2023-02-07T22:09:20Z)
• Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting [5.199570417938866]
  問題となるのがリニアプログラム(ILP)である場合について検討する。 結果のスキームが最近導入されたヤコビ自由バックプロパゲーション(JFB)と互換性があることを証明する。 提案手法は, 最短経路問題とクナップサック問題という2つの代表的なICPに対する実験により, 前方パス上のこの組み合わせDYS, 後方パス上のJFBが, 既存のスキームよりも高次元問題に対してより効果的にスケールするスキームを示す。
  論文  参考訳（メタデータ） (2023-01-31T04:03:28Z)
• Polynomial Optimization: Enhancing RLT relaxations with Conic Constraints [0.0]
  円錐最適化は、非スケール問題に対するトラクタブルで保証されたアルゴリズムを設計するための強力なツールとして登場した。 最適化問題に対するRLT緩和の強化について,9種類の制約を加えて検討する。 我々は、これらの変種とその性能を、互いに、そして標準RCT緩和に関してどのように設計するかを示す。
  論文  参考訳（メタデータ） (2022-08-11T02:13:04Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。 有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。 我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
  論文  参考訳（メタデータ） (2020-07-13T16:30:47Z)

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

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