論文の概要: Computational complexity of Inexact Proximal Point Algorithm for Convex
Optimization under Holderian Growth
- arxiv url: http://arxiv.org/abs/2108.04482v1
- Date: Tue, 10 Aug 2021 07:15:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-11 14:19:07.867465
- Title: Computational complexity of Inexact Proximal Point Algorithm for Convex
Optimization under Holderian Growth
- Title（参考訳）: ホルダ拡大下における凸最適化のための不規則近点アルゴリズムの計算複雑性
- Authors: Andrei Patrascu, Paul Irofti
- Abstract要約: 近似点アルゴリズム(PPA)の計算複雑性を(近)勾配/下位反復の観点で評価する。
まず、凸関数を最小化するために、完全かつ不正確なPPAの漸近反復複雑性推定を導出する。
第二に、目的関数の成長に関する情報が得られない場合に利用可能な、不正確なPPAの再開版に、新しい計算複雑性が束縛されていることを示す。
- 参考スコア（独自算出の注目度）: 4.416484585765028
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several decades ago the Proximal Point Algorithm (PPA) started to gain much
attraction for both abstract operator theory and the numerical optimization
communities. Even in modern applications, researchers still use proximal
minimization theory to design scalable algorithms that overcome nonsmoothness
in high dimensional models. Several remarkable references as
\cite{Fer:91,Ber:82constrained,Ber:89parallel,Tom:11} analyzed the tight local
relations between the convergence rate of PPA and the regularity of the
objective function. However, without taking into account the concrete
computational effort paid for computing each PPA iteration, any iteration
complexity remains abstract and purely informative. In this manuscript we aim
to evaluate the computational complexity of practical PPA in terms of
(proximal) gradient/subgradient iterations, which might allow a fair
positioning of the famous PPA numerical performance in the class of first order
methods. First, we derive nonasymptotic iteration complexity estimates 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 exact PPA: finite convergence for sharp minima and linear
convergence for quadratic growth, even under presence of inexactness. Second,
assuming that an usual (proximal) gradient/subgradient method subroutine is
employed to compute inexact PPA iteration, we show novel computational
complexity bounds on a restarted variant of the 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
schemes.
- Abstract（参考訳）: 数十年前、PPA (Proximal Point Algorithm) は抽象演算子理論と数値最適化のコミュニティの両方に多くの注目を集め始めた。
現代の応用においても、研究者は高次元モデルにおける非滑らか性を克服するスケーラブルなアルゴリズムを設計するために、近位最小化理論を用いている。
\cite{fer:91,ber:82constrained,ber:89parallel,tom:11} は ppa の収束率と目的関数の正則性の間の密接な局所関係を分析した。
しかしながら、各PPAイテレーションの計算に費やされる具体的な計算労力を考慮せずに、イテレーションの複雑さは抽象的で純粋に有益である。
本論文は,PPAの計算複雑性を(近)勾配/下位反復の観点から評価することを目的としており,一階法のクラスにおける有名なPPA数値性能の公平な位置決めを可能にしている。
まず、完全かつ不正確な PPA の漸近的反復複雑性推定を導出し、凸関数を$\gamma-$Holderian growth: $\BigO{\log(1/\epsilon)}$ ($\gamma \in [1,2]$) と $\BigO{1/\epsilon^{\gamma - 2}}$ ($\gamma > 2$) で最小化する。
特に, 鋭い極小の有限収束と二次成長の線形収束という, 不正確性の存在下でもよく知られた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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。