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

• arxiv url: http://arxiv.org/abs/2210.12547v2
• Date: Wed, 19 Jul 2023 16:16:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-20 18:02:48.967714
• 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要約: 私たちは、$textbfSurCo$が既存の$underlinetextCo$mbinatorialソルバで使用できる線形$underlinetextSur$rogateコストを学習していることを示します。 実験によると、$textttSurCo$は最先端のドメインエキスパートアプローチよりも高速なソリューションを見つける。
• 参考スコア（独自算出の注目度）: 43.95592587141054
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimization problems with nonlinear cost functions and combinatorial constraints appear in many real-world applications but remain challenging to solve efficiently compared to their linear counterparts. To bridge this gap, we propose $\textbf{SurCo}$ that learns linear $\underline{\text{Sur}}$rogate costs which can be used in existing $\underline{\text{Co}}$mbinatorial solvers to output good solutions to the original nonlinear combinatorial optimization problem. The surrogate costs are learned end-to-end with nonlinear loss by differentiating through the linear surrogate solver, combining the flexibility of gradient-based methods with the structure of linear combinatorial optimization. We propose three $\texttt{SurCo}$ variants: $\texttt{SurCo}-\texttt{zero}$ for individual nonlinear problems, $\texttt{SurCo}-\texttt{prior}$ for problem distributions, and $\texttt{SurCo}-\texttt{hybrid}$ to combine both distribution and problem-specific information. We give theoretical intuition motivating $\texttt{SurCo}$, and evaluate it empirically. Experiments show that $\texttt{SurCo}$ finds better solutions faster than state-of-the-art and domain expert approaches in real-world optimization problems such as embedding table sharding, inverse photonic design, and nonlinear route planning.
• Abstract（参考訳）: 非線形コスト関数と組合せ制約の最適化問題は、多くの実世界のアプリケーションに現れるが、線形の計算よりも効率的に解くことは困難である。 このギャップを埋めるために、既存の$\underline{\text{co}}$mbinatorialソルバで使用できる線形$\underline{\text{sur}}$rogateコストを学習する$\textbf{surco}$を提案する。 線形サロゲート解法を微分することで、勾配法と線形組合せ最適化の構造を組み合わせることで、非線形損失を伴う終末のサロゲートコストを学習する。 我々は、個々の非線形問題に対して$\texttt{surco}-\texttt{zero}$、問題分布に対して$\texttt{surco}-\texttt{prior}$、分散と問題固有の情報を組み合わせる$\texttt{surco}-\texttt{hybrid}$という3つの変種を提案する。 理論的直観が$\texttt{SurCo}$を動機付け、それを経験的に評価する。 実験によると、$\texttt{SurCo}$は、組込みテーブルシャーディング、逆フォトニックデザイン、非線形経路計画のような実世界の最適化問題において、最先端のドメインエキスパートアプローチよりも高速な解を見つける。

関連論文リスト

• 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 Optimization Methods for Extreme Similarity Learning with Nonlinear Embeddings [12.119973339250848]
  すべての可能なペアからの非線形埋め込みモデルを用いて類似性を学習する問題を考察する。 本稿では, 一般非線形埋め込みの結果を拡張することを目的としている。
  論文  参考訳（メタデータ） (2020-10-26T12:09:09Z)
• 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)

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

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