論文の概要: Computational complexity of Inexact Proximal Point Algorithm for Convex
Optimization under Holderian Growth
- arxiv url: http://arxiv.org/abs/2108.04482v3
- Date: Thu, 12 Aug 2021 10:44:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-13 11:27:16.005050
- Title: Computational complexity of Inexact Proximal Point Algorithm for Convex
Optimization under Holderian Growth
- Title（参考訳）: ホルダ拡大下における凸最適化のための不規則近点アルゴリズムの計算複雑性
- Authors: Andrei Patrascu, Paul Irofti
- Abstract要約: Proximal Point Algorithm (PPA) は、抽象演算子理論と数値最適化のコミュニティの双方にとって長期の魅力があると述べた。
コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近反復複雑性を導出する。
目的関数の成長に関する情報が得られない場合に利用可能な,再活性化された不正確なPPA上の新しい計算複雑性境界を示す。
- 参考スコア（独自算出の注目度）: 4.416484585765028
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: \noindent Several decades ago the Proximal Point Algorithm (PPA) stated to
gain a long-lasting attraction for both abstract operator theory and numerical
optimization communities. Even in modern applications, researchers still use
proximal minimization theory to design scalable algorithms that overcome
nonsmoothness. Remarkable works as
\cite{Fer:91,Ber:82constrained,Ber:89parallel,Tom:11} established tight
relations between the convergence behaviour of PPA and the regularity of the
objective function. In this manuscript we derive nonasymptotic iteration
complexity of exact and inexact PPA to minimize convex functions under
$\gamma-$Holderian growth: $\BigO{\log(1/\epsilon)}$ (for $\gamma \in [1,2]$)
and $\BigO{1/\epsilon^{\gamma - 2}}$ (for $\gamma > 2$). In particular, we
recover well-known results on PPA: finite convergence for sharp minima and
linear convergence for quadratic growth, even under presence of inexactness.
However, without taking into account the concrete computational effort paid for
computing each PPA iteration, any iteration complexity remains abstract and
purely informative. Therefore, using an inner (proximal) gradient/subgradient
method subroutine that computes inexact PPA iteration, we secondly show novel
computational complexity bounds on a restarted inexact PPA, available when no
information on the growth of the objective function is known. In the numerical
experiments we confirm the practical performance and implementability of our
framework.
- Abstract（参考訳）: 数十年前、PPA (Proximal Point Algorithm) は抽象演算子理論と数値最適化のコミュニティの両方に長期の魅力をもたらすと表明した。
現代の応用においても、研究者は非滑らかさを克服するスケーラブルなアルゴリズムを設計するために近位最小化理論を用いる。
Fer:91,Ber:82constrained,Ber:89parallel,Tom:11} は PPA の収束挙動と目的関数の正則性の間の密接な関係を確立した。
この写本では、完全かつ不正確なPPAの漸近反復複雑性を導出し、凸関数を$\gamma-$Holderian growth: $\BigO{\log(1/\epsilon)}$($\gamma \in [1,2]$)および$\BigO{1/\epsilon^{\gamma - 2}}$($\gamma > 2$)で最小化する。
特に, ppa における有限収束と二次成長に対する線形収束について, 不正確性の存在下でもよく知られた結果が得られた。
しかしながら、各PPAイテレーションの計算に費やされる具体的な計算労力を考慮せずに、イテレーションの複雑さは抽象的で純粋に有益である。
したがって、不正確なPPA反復を計算する内部(近)勾配/下位のメソッドサブルーチンを用いて、第二に、目的関数の成長に関する情報がない場合に利用可能な、再実行された不正確なPPA上の新しい計算複雑性境界を示す。
数値実験により,本フレームワークの実用的性能と実装性を確認した。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文 参考訳（メタデータ） (2023-05-23T15:26:36Z) - A relaxed proximal gradient descent algorithm for convergent
plug-and-play with proximal denoiser [6.2484576862659065]
本稿では,新しいコンバーゼントなPlug-and-fidelity Descent (Play)アルゴリズムを提案する。
このアルゴリズムは、より広い範囲の通常の凸化パラメータに収束し、画像のより正確な復元を可能にする。
論文 参考訳（メタデータ） (2023-01-31T16:11:47Z) - On efficient algorithms for computing near-best polynomial
approximations to high-dimensional, Hilbert-valued functions from limited
samples [1.0650780147044159]
スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。
本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
論文 参考訳（メタデータ） (2022-03-25T20:56:07Z) - Escaping Saddle-Points Faster under Interpolation-like Conditions [19.9471360853892]
過度なパラメータ化の下では、いくつかの標準的な最適化アルゴリズムがサドルポイントを回避し、局所最小化器に収束する。
本稿では、PSGDアルゴリズムの1次オラクル複雑性について論じ、$epsilon$ localminimizerに到達した。
次に、Cubic-Regularized Newton (SCRN)アルゴリズムのアンダーライクな条件を分析し、局所最小化剤アンダーライクな条件に到達するためのオラクルの複雑さが$tildemathcalO (1/epsilon2.5)であることを示す。
論文 参考訳（メタデータ） (2020-09-28T02:15:18Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳（メタデータ） (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。