論文の概要: Correlated Mutations for Integer Programming

• arxiv url: http://arxiv.org/abs/2506.22526v1
• Date: Fri, 27 Jun 2025 08:24:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-01 21:27:53.449756
• Title: Correlated Mutations for Integer Programming
• Title（参考訳）: 整数プログラミングにおける関連突然変異
• Authors: Ofer M. Shir, Michael Emmerich,
• Abstract要約: 本研究は、進化戦略(IESs)の基盤を確立することを目的としている。 IESはすでにIP処理に優れていますが、離散化や高度なパッチを連続演算子に適用することで実現しています。 整数決定変数の突然変異分布に着目した。 エントロピー関数を含むそれらの理論的性質を考察し、拡張性のある相関突然変異分布を生成する方法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Even with the recent theoretical advancements that dramatically reduced the complexity of Integer Programming (IP), heuristics remain the dominant problem-solvers for this difficult category. This study seeks to establish the groundwork for Integer Evolution Strategies (IESs), a class of randomized search heuristics inherently designed for continuous spaces. IESs already excel in treating IP in practice, but accomplish it via discretization and by applying sophisticated patches to their continuous operators, while persistently using the $\ell_2$-norm as their operation pillar. We lay foundations for discrete search, by adopting the $\ell_1$-norm, accounting for the suitable step-size, and questioning alternative measures to quantify correlations over the integer lattice. We focus on mutation distributions for unbounded integer decision variables. We briefly discuss a couple of candidate discrete probabilities induced by the uniform and binomial distributions, which we show to possess less appealing theoretical properties, and then narrow down to the Truncated Normal (TN) and Double Geometric (DG) distributions. We explore their theoretical properties, including entropy functions, and propose a procedure to generate scalable correlated mutation distributions. Our investigations are accompanied by extensive numerical simulations, which consistently support the claim that the DG distribution is better suited for unbounded integer search. We link our theoretical perspective to empirical evidence indicating that an IES with correlated DG mutations outperformed other strategies over non-separable quadratic IP. We conclude that while the replacement of the default TN distribution by the DG is theoretically justified and practically beneficial, the truly crucial change lies in adopting the $\ell_1$-norm over the $\ell_2$-norm.
• Abstract（参考訳）: 整数プログラミング(IP)の複雑さを劇的に減らした最近の理論的進歩にもかかわらず、ヒューリスティックスは依然としてこの難解なカテゴリーの主要な問題解決者である。 本研究では,連続空間に固有のランダムな探索ヒューリスティックのクラスであるInteger Evolution Strategies(IESs)の基盤を確立することを目的とする。 IESはすでにIP処理に優れていますが、離散化や、継続演算子に高度なパッチを適用することで実現しています。 我々は、$\ell_1$-normを採用し、適切なステップサイズを考慮し、整数格子上の相関を定量化するための代替手段を問うことによって、離散探索の基礎を定めている。 非有界整数決定変数の突然変異分布に着目する。 均一分布と二項分布によって引き起こされる2つの離散確率について簡単に論じるが、これはより魅力的でない理論的性質を持つことを示すものであり、TN(Trncated Normal)分布とDouble Geometric(DG)分布に狭められている。 エントロピー関数を含むそれらの理論的性質を考察し、拡張性のある相関突然変異分布を生成する方法を提案する。 我々の研究は、DG分布が非有界整数探索に適しているという主張を一貫して支持する広範な数値シミュレーションを伴っている。 我々は、DG変異が相関しているIESが非分離2次IPに対して他の戦略よりも優れていることを示す実証的な証拠と理論的な視点をリンクする。 DG によるデフォルトの TN 分布の置き換えは理論的には正当化され、実際は有益であるが、真に重要な変更は $\ell_1$-norm を $\ell_2$-norm ではなく $\ell_1$-norm を採用することである。

関連論文リスト

• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  本稿では、多様体制約データ分布のクラスにおける段階的領域適応の課題に対処する。 本稿では,適応的なワッサースタイン半径を持つ分布ロバスト最適化(DRO)を基礎とした手法を提案する。 我々のバウンダリは、新たに導入されたそれとの互換性尺度に依存しており、シーケンスに沿ったエラー伝搬のダイナミクスを完全に特徴付けています。
  論文  参考訳（メタデータ） (2024-10-17T22:07:25Z)
• Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
  平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。 我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。 我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
  論文  参考訳（メタデータ） (2023-10-04T17:24:45Z)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  一般化Schr"odinger Bridge (GSB) 問題設定は、機械学習の内外を問わず、多くの科学領域で一般的である。 我々は最近の進歩に触発された新しいマッチングアルゴリズムである一般化シュリンガーブリッジマッチング(GSBM)を提案する。 このような一般化は条件最適制御の解法として、変分近似を用いることができることを示す。
  論文  参考訳（メタデータ） (2023-10-03T17:42:11Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements [19.524063429548278]
  Extragradient (SEG) と Gradient Descent Ascent (SGDA) は min-max 最適化と変分不等式問題に対する優越アルゴリズムである。 これらのアルゴリズムに固有の本質的な構造を定量化し定量化するための我々の取り組み。 定数のステップサイズSEG/SGDAを時間同質マルコフ連鎖として再キャストすることにより、大数の第一種法則と中心極限定理を確立する。
  論文  参考訳（メタデータ） (2023-06-28T18:50:07Z)
• Probable Domain Generalization via Quantile Risk Minimization [90.15831047587302]
  ドメインの一般化は、目に見えないテスト分布でうまく機能する予測子を求める。 我々はDGのための新しい確率的フレームワークを提案し、高い確率でよく動作する予測器を学習することを目指している。
  論文  参考訳（メタデータ） (2022-07-20T14:41:09Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。 本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。 理論的にも経験的にも二重降下現象を観察する。
  論文  参考訳（メタデータ） (2021-10-13T17:47:39Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
  本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。 統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。 また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
  論文  参考訳（メタデータ） (2020-02-05T00:24:53Z)

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

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