論文の概要: 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) - A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria
for Robust Phase Retrieval [6.407536646154451]
本稿では,非平滑かつ非最適化問題であるロバスト検索問題を考察する。
本稿では,2つのコントリビューションでサブプロブレムを解くことを目的とした,新しい不正確な近位線形アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-25T02:29:33Z) - A Sequential Quadratic Programming Method with High Probability
Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.535271349350579]
制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。
1次定常性を近似するためにアルゴリズムの反復複雑性に縛られる高い確率が導出される。
論文 参考訳(メタデータ) (2023-01-01T21:46:50Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (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) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。