論文の概要: Linear Convergence of Stochastic Primal Dual Methods for Linear Programming Using Variance Reduction and Restarts

• arxiv url: http://arxiv.org/abs/2111.05530v1
• Date: Wed, 10 Nov 2021 04:56:38 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-11 15:24:50.656575
• Title: Linear Convergence of Stochastic Primal Dual Methods for Linear Programming Using Variance Reduction and Restarts
• Title（参考訳）: 分散還元と再スタートを用いた線形計画のための確率的原始双対法の線形収束
• Authors: Haihao Lu, Jinwen Yang
• Abstract要約: 提案手法は,確率の高い鋭いインスタンスに対して線形収束率を示す。 さらに,制約のない双線形フロップ問題に対する効率的な座標に基づくオラクルを提案する。
• 参考スコア（独自算出の注目度）: 8.211107836178083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There is a recent interest on first-order methods for linear programming (LP). In this paper, we propose a stochastic algorithm using variance reduction and restarts for solving sharp primal-dual problems such as LP. We show that the proposed stochastic method exhibits a linear convergence rate for sharp instances with a high probability, which improves the complexity of the existing deterministic and stochastic algorithms. In addition, we propose an efficient coordinate-based stochastic oracle for unconstrained bilinear problems, which has $\mathcal O(1)$ per iteration cost and improves the total flop counts to reach a certain accuracy.
• Abstract（参考訳）: 近年,線形プログラミング(LP)における一階法への関心が高まっている。 本稿では,lpのような鋭い素対問題を解くために分散還元と再スタートを用いた確率的アルゴリズムを提案する。 提案手法は,高確率のシャープインスタンスに対して線形収束率を示し,既存の決定論的・確率的アルゴリズムの複雑性を向上できることを示す。 さらに,非制約双線形問題に対する効率的な座標ベースの確率オラクルを提案する。これは反復コストが$\mathcal O(1)$であり,フロップ数全体の精度が向上し,精度が向上する。

関連論文リスト

• Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approach [4.422315636150272]
  離散時間線形擬似レギュレータ(LQR)問題に対する$epsilon$-approximateソリューションの学習問題について検討する。 本手法は,二ループ分散推定アルゴリズムにおいて,一点推定と二点推定を併用する。
  論文  参考訳（メタデータ） (2023-09-19T15:03:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.3814052021083354]
  制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。 1次定常性を近似するためにアルゴリズムの反復複雑性に縛られる高い確率が導出される。
  論文  参考訳（メタデータ） (2023-01-01T21:46:50Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
  計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。 予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
  論文  参考訳（メタデータ） (2021-06-22T07:24:17Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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