論文の概要: Lyapunov function approach for approximation algorithm design and
analysis: with applications in submodular maximization
- arxiv url: http://arxiv.org/abs/2205.12442v1
- Date: Wed, 25 May 2022 02:09:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-28 21:11:43.027110
- Title: Lyapunov function approach for approximation algorithm design and
analysis: with applications in submodular maximization
- Title（参考訳）: リアプノフ関数による近似アルゴリズムの設計と解析:-部分モジュラー最大化への応用
- Authors: Donglei Du
- Abstract要約: Lyapunov関数を用いた近似アルゴリズムの設計と解析のための2段階の体系化フレームワークを提案する。
第1フェーズは、証明可能な近似比を持つ連続時間アルゴリズムを設計するためのガイドラインとして、リアプノフ関数を使用する。
次に、第2フェーズは、連続時間アルゴリズムを同じ近似比と証明可能な時間で離散時間アルゴリズムに変換する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a two-phase systematical framework for approximation algorithm
design and analysis via Lyapunov function. The first phase consists of using
Lyapunov function as a guideline to design a continuous-time algorithm with
provable approximation ratio. The second phase then converts the
continuous-time algorithm to a discrete-time algorithm with the same
approximation ratio and a provable time complexity. Some immediate benefits of
the Lyapunov function approach include: (i) unifying many existing algorithms;
(ii) providing a guideline to design and analyze new algorithms; and (iii)
offer new perspectives to potentially improve existing algorithms. We use
various submodular maximization problems as running examples to illustrate our
framework.
- Abstract（参考訳）: リアプノフ関数を用いた近似アルゴリズム設計と解析のための二相系統的枠組みを提案する。
第1フェーズは、証明可能な近似比を持つ連続時間アルゴリズムを設計するためのガイドラインとしてリアプノフ関数を使用する。
2番目のフェーズでは、連続時間アルゴリズムを同じ近似比と証明可能な時間複雑性を持つ離散時間アルゴリズムに変換する。
Lyapunov関数のアプローチの直接的な利点は以下のとおりである。
(i)既存の多くのアルゴリズムを統一すること。
(ii)新しいアルゴリズムを設計・分析するためのガイドラインの提供
(iii) 既存のアルゴリズムを改善する新しい視点を提供する。
フレームワークを例示するために、様々な部分モジュラー最大化問題を例に挙げる。
関連論文リスト
- Optimization Algorithm Design via Electric Circuits [13.101300549333297]
本稿では,電気RCC回路のアイデアを用いた凸最適化アルゴリズムの設計手法を提案する。
この手法の第一段階は、連続時間ダイナミクスが目の前の最適化問題の解に収束する適切な電気回路を設計することである。
第2段階は、連続時間力学のコンピュータ支援による自動離散化であり、証明可能な収束離散時間アルゴリズムをもたらす。
論文 参考訳（メタデータ） (2024-11-04T20:10:59Z) - Deterministic Trajectory Optimization through Probabilistic Optimal Control [3.2771631221674333]
離散時間決定論的有限水平非線形最適制御問題に対する2つの新しいアルゴリズムを提案する。
どちらのアルゴリズムも確率論的最適制御として知られる新しい理論パラダイムにインスパイアされている。
このアルゴリズムの適用により、決定論的最適ポリシーに収束する確率的ポリシーの定点が得られることを示す。
論文 参考訳（メタデータ） (2024-07-18T09:17:47Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Reinforcement Learning with Unbiased Policy Evaluation and Linear
Function Approximation [11.345796608258434]
マルコフ決定プロセスを制御するためのシミュレーションベースのポリシーイテレーションの変種に対して,性能保証を提供する。
第一のアルゴリズムは最小二乗アプローチを伴い、各反復において、特徴ベクトルに関連する新しい重みの集合が少なくとも二乗によって得られる。
第2のアルゴリズムは、最小二乗解への勾配降下を数ステップ行う2段階の近似アルゴリズムを含む。
論文 参考訳（メタデータ） (2022-10-13T20:16:19Z) - Two-Timescale Stochastic Approximation for Bilevel Optimisation Problems
in Continuous-Time Models [0.0]
本研究では,連続時間モデルにおける二段階最適化問題に対する連続時間2時間スケール近似アルゴリズムの特性を解析する。
我々はこのアルゴリズムの弱収束率を中心極限定理の形で得る。
論文 参考訳（メタデータ） (2022-06-14T17:12:28Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - A Unifying View of Optimism in Episodic Reinforcement Learning [18.73198634652064]
本稿では,楽観的な強化学習アルゴリズムの設計,解析,実装のためのフレームワークを提供する。
楽観的なMDPを構成する任意のモデル最適化アルゴリズムは、値最適化動的プログラミングアルゴリズムとして等価な表現を持つ。
論文 参考訳（メタデータ） (2020-07-03T18:10:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。