論文の概要: High Probability Bounds for Stochastic Continuous Submodular
Maximization
- arxiv url: http://arxiv.org/abs/2303.11937v1
- Date: Mon, 20 Mar 2023 17:20:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-22 14:20:23.302870
- Title: High Probability Bounds for Stochastic Continuous Submodular
Maximization
- Title（参考訳）: 確率的連続部分モジュラ最大化のための高確率境界
- Authors: Evan Becker, Jingdong Gao, Ted Zadouri, Baharan Mirzasoleiman
- Abstract要約: 単調連続部分モジュラ函数の戻り特性の低下を考える。
最悪の場合においても、PGAは$OPT/2$に収束し、PGA、SCG、SCG++は$(1 - 1/e)OPT$に収束するが、期待するソリューションよりも遅い速度で収束する。
- 参考スコア（独自算出の注目度）: 5.362258158646462
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider maximization of stochastic monotone continuous submodular
functions (CSF) with a diminishing return property. Existing algorithms only
guarantee the performance \textit{in expectation}, and do not bound the
probability of getting a bad solution. This implies that for a particular run
of the algorithms, the solution may be much worse than the provided guarantee
in expectation. In this paper, we first empirically verify that this is indeed
the case. Then, we provide the first \textit{high-probability} analysis of the
existing methods for stochastic CSF maximization, namely PGA, boosted PGA, SCG,
and SCG++. Finally, we provide an improved high-probability bound for SCG,
under slightly stronger assumptions, with a better convergence rate than that
of the expected solution. Through extensive experiments on non-concave
quadratic programming (NQP) and optimal budget allocation, we confirm the
validity of our bounds and show that even in the worst-case, PGA converges to
$OPT/2$, and boosted PGA, SCG, SCG++ converge to $(1 - 1/e)OPT$, but at a
slower rate than that of the expected solution.
- Abstract（参考訳）: 確率的単調連続部分モジュラ関数 (CSF) の最大化について検討した。
既存のアルゴリズムは、パフォーマンス \textit{in expectation} のみを保証し、悪い解決策を得る確率を制限しない。
これは、特定のアルゴリズムを実行する場合、提案された保証よりも解がはるかに悪いことを意味する。
本稿では,これが事実であることを実証的に検証する。
次に,既存の確率的csf最大化法であるpga, boosted pga, scg, scg++について,最初の \textit{high-probability}解析を行う。
最後に,scgの高確率バウンドを若干強い仮定の下で改善し,期待解よりも収束率を向上させる。
非コンケーブ二次計画法(NQP)と最適予算配分に関する広範な実験を通じて、我々の限界の妥当性を確認し、最悪の場合においても、PGAは$OPT/2$に収束し、PGA、SCG、SCG++は$(1 - 1/e)OPT$に収束するが、予想されるソリューションよりも遅い速度で収束することを示す。
関連論文リスト
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。