論文の概要: 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上の新しい計算複雑性境界を示す。
数値実験により,本フレームワークの実用的性能と実装性を確認した。
関連論文リスト
- 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 [29.56022052936922]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。
ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
論文 参考訳(メタデータ) (2023-05-23T15:26:36Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳(メタデータ) (2023-02-22T20:21:25Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - On the Complexity of Finding Small Subgradients in Nonsmooth
Optimization [31.714928102950584]
決定論的アルゴリズムにより次元自由度を達成できないことを示す。
関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
論文 参考訳(メタデータ) (2022-09-21T13:30:00Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳(メタデータ) (2020-09-18T02:18:44Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Reinforcement Learning with General Value Function Approximation:
Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。
我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。
我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
論文 参考訳(メタデータ) (2020-05-21T17:36:09Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳(メタデータ) (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。