論文の概要: Approximation Guarantees of Local Search Algorithms via Localizability
of Set Functions
- arxiv url: http://arxiv.org/abs/2006.01400v1
- Date: Tue, 2 Jun 2020 05:37:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 01:15:11.325126
- Title: Approximation Guarantees of Local Search Algorithms via Localizability
of Set Functions
- Title（参考訳）: 集合関数の局所化による局所探索アルゴリズムの近似保証
- Authors: Kaito Fujii
- Abstract要約: 局所探索は基本的なアルゴリズムであり、様々な最適化問題に広く利用されている。
ローカライズ可能性の観点から,様々な制約の下で,標準的な局所探索アルゴリズムの近似保証を提供する。
本フレームワークの主な用途はスパース最適化であり, 強い凹凸や目的関数の滑らかさの制限は局所性を意味することを示す。
- 参考スコア（独自算出の注目度）: 9.89901717499058
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper proposes a new framework for providing approximation guarantees of
local search algorithms. Local search is a basic algorithm design technique and
is widely used for various combinatorial optimization problems. To analyze
local search algorithms for set function maximization, we propose a new notion
called localizability of set functions, which measures how effective local
improvement is. Moreover, we provide approximation guarantees of standard local
search algorithms under various combinatorial constraints in terms of
localizability. The main application of our framework is sparse optimization,
for which we show that restricted strong concavity and restricted smoothness of
the objective function imply localizability, and further develop accelerated
versions of local search algorithms. We conduct experiments in sparse
regression and structure learning of graphical models to confirm the practical
efficiency of the proposed local search algorithms.
- Abstract（参考訳）: 本稿では,局所探索アルゴリズムの近似保証を提供する新しい枠組みを提案する。
局所探索は基本的なアルゴリズム設計手法であり、様々な組合せ最適化問題に広く用いられている。
集合関数の最大化のための局所探索アルゴリズムを解析するために,集合関数の局所化可能性という新しい概念を提案する。
さらに,様々な組合せ制約下での標準局所探索アルゴリズムの近似保証を局所化可能性の観点から提供する。
本フレームワークの主な用途はスパース最適化であり, 目的関数の強い凹凸と制限された滑らかさが局所化可能性を示し, 局所探索アルゴリズムの高速化バージョンをさらに発展させることを示す。
提案する局所探索アルゴリズムの実用性を確認するため,グラフィカルモデルの疎回帰と構造学習の実験を行った。
関連論文リスト
- Characterization of Locality in Spin States and Forced Moves for
Optimizations [0.36868085124383626]
最適化問題において、エネルギーランドスケープにおける局所最小値の存在は、世界最小値を求めるために問題となる。
そこで我々は,局所最小値から効率よく抜け出すアルゴリズムを開発したが,正確なサンプリングは得られなかった。
提案アルゴリズムはリジェクションフリーなアルゴリズムに基づいているため,計算コストは低い。
論文 参考訳（メタデータ） (2023-12-05T07:21:00Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - New Characterizations and Efficient Local Search for General Integer
Linear Programming [17.80124240223163]
本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。
そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。
MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
論文 参考訳（メタデータ） (2023-04-29T07:22:07Z) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。
基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。
我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文 参考訳（メタデータ） (2022-09-27T17:51:31Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Flipping the switch on local exploration: Genetic Algorithms with
Reversals [0.0]
著者らは、勾配のない探索手法が離散領域における最適解を提供するのに適していることを示した。
また、複数のローカル検索を使用することで、ローカル検索のパフォーマンスが向上することを示した。
提案したGA変種は,提案した問題を含む全てのベンチマークにおいて,最小平均コストであり,ICが構成成分よりも優れた性能を発揮することが観察された。
論文 参考訳（メタデータ） (2022-02-02T08:27:11Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - Exploiting Local Optimality in Metaheuristic Search [0.0]
本稿では,適応型メモリメタヒューリスティックを用いて,ソリューション履歴の有用な特徴を特定し,活用するための戦略を導入する。
提案手法は指数外挿という構造に基づく新しい適応型メモリを用いる。
論文 参考訳（メタデータ） (2020-10-12T01:51:09Z) - Sequential Subspace Search for Functional Bayesian Optimization
Incorporating Experimenter Intuition [63.011641517977644]
本アルゴリズムは,実験者のガウス過程から引き出された一組の引き数で区切られた関数空間の有限次元ランダム部分空間列を生成する。
標準ベイズ最適化は各部分空間に適用され、次の部分空間の出発点(オリジン)として用いられる最良の解である。
シミュレーションおよび実世界の実験,すなわちブラインド関数マッチング,アルミニウム合金の最適析出強化関数の探索,深層ネットワークの学習速度スケジュール最適化において,本アルゴリズムを検証した。
論文 参考訳（メタデータ） (2020-09-08T06:54:11Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。