論文の概要: Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting
- arxiv url: http://arxiv.org/abs/2301.13395v4
- Date: Sat, 20 Jul 2024 03:49:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 06:06:15.106199
- Title: Differentiating Through Integer Linear Programs with Quadratic Regularization and Davis-Yin Splitting
- Title（参考訳）: 二次正則化と Davis-Yin 分割による整数線形プログラムの微分
- Authors: Daniel McKenzie, Samy Wu Fung, Howard Heaton,
- Abstract要約: 問題となるのがリニアプログラム(ILP)である場合について検討する。
結果のスキームが最近導入されたヤコビ自由バックプロパゲーション(JFB)と互換性があることを証明する。
提案手法は, 最短経路問題とクナップサック問題という2つの代表的なICPに対する実験により, 前方パス上のこの組み合わせDYS, 後方パス上のJFBが, 既存のスキームよりも高次元問題に対してより効果的にスケールするスキームを示す。
- 参考スコア（独自算出の注目度）: 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. We study the case where the problem in question is an Integer Linear Program (ILP). We propose applying a three-operator splitting technique, also known as Davis-Yin splitting (DYS), to the quadratically regularized continuous relaxation of the ILP. We prove that the resulting scheme is compatible with the recently introduced Jacobian-free backpropagation (JFB). Our experiments on two representative ILPs: the shortest path problem and the knapsack problem, demonstrate that this combination-DYS on the forward pass, JFB on the backward pass-yields a scheme which scales more effectively to high-dimensional problems than existing schemes. All code associated with this paper is available at github.com/mines-opt-ml/fpo-dys.
- Abstract（参考訳）: 多くの応用において、組合せ問題は類似しているが異なるパラメータで繰り返し解決されなければならない。
しかし、パラメータ$w$は直接観測されておらず、$w$と相関するコンテキストデータ$d$のみが利用可能である。
ニューラルネットワークを使って$d$の$w$を予測する傾向があります。
しかし、そのようなモデルをトレーニングするには、ニューラルネットワークのトレーニングに使用される勾配ベースのフレームワークと組み合わせ最適化の離散的な性質を調整する必要がある。
Integer Linear Program (ILP) が問題となる場合について検討する。
ILPの4次正規化連続緩和に対して,DYS(Davis-Yin splitting)と呼ばれる三元分割法を適用することを提案する。
得られたスキームは、最近導入されたヤコビ自由バックプロパゲーション(JFB)と互換性があることを証明する。
最短経路問題とクナップサック問題という2つの代表的なICPに関する実験により, この前方パス上の組み合わせ-DYS, 後方パス上のJFBは, 既存のスキームよりも高次元問題に対してより効果的にスケールするスキームを示す。
この論文に関連するすべてのコードはgithub.com/mines-opt-ml/fpo-dysで入手できる。
関連論文リスト
- 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 Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
プレイヤーが$d$ベースアイテムを含むセットのパワーセットから$P$アクションの中から選択する半帯域の問題に対処する。
提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2024-02-23T08:07:54Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。