Fugu-MT 論文翻訳(概要): Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth

論文の概要: Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth

arxiv url: http://arxiv.org/abs/2108.04482v6
Date: Tue, 28 May 2024 14:09:53 GMT
ステータス: 処理完了
システム内更新日: 2024-05-30 05:05:50.148514
Title: Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth
Title（参考訳）: ホールダー成長を伴う凸関数最小化のための非接触近点アルゴリズムの複雑さ
Authors: Andrei Pătraşcu, Paul Irofti,
Abstract要約: コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。数値実験では, 既存の再起動バージョンよりも改善が見られた。
参考スコア（独自算出の注目度）: 1.9643748953805935
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Several decades ago the Proximal Point Algorithm (PPA) started 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 deterministic noise. Moreover, when a simple Proximal Subgradient Method is recurrently called as an inner routine for computing each IPPA iterate, novel computational complexity bounds are obtained for Restarting Inexact PPA. Our numerical tests show improvements over existing restarting versions of the Subgradient Method.
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上のよく知られた結果を回復する。さらに、各IPPAを反復的に計算するための内部ルーチンとして、単純な近位次法をリカレントに呼び出すと、不正確な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)

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

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