Fugu-MT 論文翻訳(概要): A New Branch-and-Bound Pruning Framework for $\ell

論文の概要: A New Branch-and-Bound Pruning Framework for $\ell_0$-Regularized Problems

arxiv url: http://arxiv.org/abs/2406.03504v1
Date: Mon, 3 Jun 2024 19:40:06 GMT
ステータス: 処理完了
システム内更新日: 2024-06-07 19:34:24.435554
Title: A New Branch-and-Bound Pruning Framework for $\ell_0$-Regularized Problems
Title（参考訳）: $\ell_0$-regularized問題に対する分岐境界更新フレームワーク
Authors: Theo Guyard, Cédric Herzet, Clément Elvira, Ayşe-Nur Arslan,
Abstract要約: 我々は $ell_$-regularized problem のジェネリックファミリーに対してプルーニングテストを実装する代替案を提案する。提案手法により,複数の領域の同時評価が可能となった。数値シミュレーションにより,BnBプロシージャの解法時間を桁違いに改善できることを示す。
参考スコア（独自算出の注目度）: 8.03303585542693
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider the resolution of learning problems involving $\ell_0$-regularization via Branch-and-Bound (BnB) algorithms. These methods explore regions of the feasible space of the problem and check whether they do not contain solutions through "pruning tests". In standard implementations, evaluating a pruning test requires to solve a convex optimization problem, which may result in computational bottlenecks. In this paper, we present an alternative to implement pruning tests for some generic family of $\ell_0$-regularized problems. Our proposed procedure allows the simultaneous assessment of several regions and can be embedded in standard BnB implementations with a negligible computational overhead. We show through numerical simulations that our pruning strategy can improve the solving time of BnB procedures by several orders of magnitude for typical problems encountered in machine-learning applications.
Abstract（参考訳）: 本稿では,ブランチ・アンド・バウンド(BnB)アルゴリズムによる$\ell_0$-regularizationを含む学習問題の解決について考察する。これらの手法は、問題の実現可能な空間の領域を探索し、それらが「プルーニングテスト」によって解を含まないかどうかを確認する。標準的な実装では、プルーニングテストの評価には凸最適化の問題が解決され、計算ボトルネックが発生する可能性がある。本稿では,$\ell_0$-regularized問題に対するプルーニングテストの実装方法を提案する。提案手法により,複数の領域の同時評価が可能となり,計算オーバーヘッドが無視できる標準BnB実装に組み込むことができる。我々は,機械学習アプリケーションで発生する典型的な問題に対して,BnBプロシージャの解法時間を桁違いに改善できることを数値シミュレーションにより示す。

関連論文リスト

Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文参考訳（メタデータ） (2023-10-08T23:39:38Z)
FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
FastDiagは、競合を事前に決定せずに診断計算をサポートする典型的な直接診断アルゴリズムである。本稿では,投機的プログラミングのアイデアに基づく新しいアルゴリズムであるFastDiagPを提案する。このメカニズムは、高速な回答で一貫性チェックを提供し、アルゴリズムのランタイムパフォーマンスを高めるのに役立つ。
論文参考訳（メタデータ） (2023-05-11T16:26:23Z)
A Sequential Deep Learning Algorithm for Sampled Mixed-integer Optimisation Problems [0.3867363075280544]
混合整数最適化問題に対する2つの効率的なアルゴリズムを導入,解析する。両アルゴリズムが最適解に対して有限時間収束を示すことを示す。 3つの数値実験により,これらのアルゴリズムの有効性を定量的に確立する。
論文参考訳（メタデータ） (2023-01-25T17:10:52Z)
A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming [0.0]
我々は,小問題インスタンスのSBCを解釈可能な一階制約の集合に引き上げる,新しいモデル指向アンサーセットプログラミングを導入する。簡単な問題をターゲットにして,先進的な意思決定問題にも適用できるように拡張することを目指している。
論文参考訳（メタデータ） (2022-08-05T10:50:03Z)
Efficient lifting of symmetry breaking constraints for complex combinatorial problems [9.156939957189502]
この作業は、Answer Set Programmingのためのモデルベースのアプローチの学習フレームワークと実装を拡張します。 Inductive Logic Programming System ILASPに新たなコンフリクト解析アルゴリズムを組み込む。
論文参考訳（メタデータ） (2022-05-14T20:42:13Z)
Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文参考訳（メタデータ） (2022-01-28T05:53:28Z)
Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
論文参考訳（メタデータ） (2021-12-22T11:27:48Z)
Parallelizing Contextual Linear Bandits [82.65675585004448]
並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
論文参考訳（メタデータ） (2021-05-21T22:22:02Z)
Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文参考訳（メタデータ） (2021-05-05T18:28:42Z)
Multi-armed Bandits with Cost Subsidy [1.6631602844999724]
本稿では、インテリジェントSMSルーティング問題と広告オーディエンス最適化問題という2つのアプリケーションを提案する。既存のMABアルゴリズムの素早い一般化は、この問題に対してうまく機能しないことを示す。また,このアルゴリズムに対して,探索定理の簡単な変種を提示し,ほぼ最適な後悔境界を定めている。
論文参考訳（メタデータ） (2020-11-03T05:38:42Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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