論文の概要: Learning to Solve Integer Linear Programs with Davis-Yin Splitting

• arxiv url: http://arxiv.org/abs/2301.13395v3
• Date: Thu, 21 Mar 2024 13:16:27 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-22 20:39:25.455612
• Title: Learning to Solve Integer Linear Programs with Davis-Yin Splitting
• Title（参考訳）: Davis-Yin 分割による整数線形プログラムの解法
• Authors: Daniel McKenzie, Samy Wu Fung, Howard Heaton,
• Abstract要約: 現代の凸最適化のアイデアに基づいて、何千もの変数の問題に懸命にスケールするネットワークとトレーニングスキームを設計する。 提案手法は,最短経路問題とknapsack問題という2つの代表的な問題に対して,計算上の優位性を検証した。
• 参考スコア（独自算出の注目度）: 5.199570417938866
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In many applications, a combinatorial problem must be repeatedly solved with similar, but distinct parameters. Yet, the parameters $w$ are not directly observed; only contextual data $d$ that correlates with $w$ is available. It is tempting to use a neural network to predict $w$ given $d$. However, training such a model requires reconciling the discrete nature of combinatorial optimization with the gradient-based frameworks used to train neural networks. When the problem in question is an Integer Linear Program (ILP), one approach to overcome this training issue is to consider a continuous relaxation of the combinatorial problem. While existing methods utilizing this approach have shown to be highly effective on small problems, they do not always scale well to large problems. In this work, we draw on ideas from modern convex optimization to design a network and training scheme which scales effortlessly to problems with thousands of variables. Our experiments verify the computational advantage our proposed method enjoys on two representative problems, namely the shortest path problem and the knapsack problem.
• Abstract（参考訳）: 多くの応用において、組合せ問題は類似しているが異なるパラメータで繰り返し解決されなければならない。 しかし、パラメータ$w$は直接観測されておらず、$w$と相関するコンテキストデータ$d$のみが利用可能である。 ニューラルネットワークを使って$d$の$w$を予測する傾向があります。 しかし、そのようなモデルをトレーニングするには、ニューラルネットワークのトレーニングに使用される勾配ベースのフレームワークと組み合わせ最適化の離散的な性質を調整する必要がある。 問題となるのが整数線形プログラム(ILP)の場合、このトレーニング問題を克服するための一つのアプローチは、組合せ問題の継続的な緩和を考えることである。 このアプローチを利用した既存の手法は、小さな問題に対して非常に効果的であることが示されているが、必ずしも大きな問題に対してうまくスケールするとは限らない。 本研究では,最新の凸最適化から,数千の変数を扱う問題に対して無駄にスケールするネットワークとトレーニングスキームを設計するためのアイデアを導出する。 提案手法は,最短経路問題とknapsack問題という2つの代表的な問題に対して,計算上の優位性を検証した。

関連論文リスト

• Self-Ensembling Gaussian Splatting for Few-Shot Novel View Synthesis [55.561961365113554]
  3D Gaussian Splatting (3DGS) は新規ビュー合成(NVS)に顕著な効果を示した しかし、3DGSモデルはスパースポーズビューで訓練すると過度に適合する傾向にあり、その一般化能力は新規ビューに制限される。 オーバーフィッティング問題を緩和するために,Self-Ensembling Gaussian Splatting (SE-GS) アプローチを提案する。 提案手法は,NVSの品質向上に寄与し,既存の最先端手法よりも優れる。
  論文  参考訳（メタデータ） (2024-10-31T18:43:48Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis [36.646876613637325]
  マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。 本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T08:18:47Z)
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
  この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。 また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
  論文  参考訳（メタデータ） (2023-03-03T18:03:49Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• An efficient projection neural network for $\ell_1$-regularized logistic regression [10.517079029721257]
  本稿では, $ell_$-regularized logistics regression のための単純な投影ニューラルネットワークを提案する。 提案したニューラルネットワークは、余分な補助変数や滑らかな近似を必要としない。 また、リアプノフ理論を用いて、提案したニューラルネットワークの収束について検討し、任意の初期値を持つ問題の解に収束することを示す。
  論文  参考訳（メタデータ） (2021-05-12T06:13:44Z)
• Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization [6.037383467521294]
  我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。 私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。 実装をツールキットL0BnBでオープンソースにしています。
  論文  参考訳（メタデータ） (2020-04-13T18:45:29Z)

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

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