論文の概要: RECAPP: Crafting a More Efficient Catalyst for Convex Optimization

• arxiv url: http://arxiv.org/abs/2206.08627v1
• Date: Fri, 17 Jun 2022 08:40:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-20 15:47:19.452025
• Title: RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
• Title（参考訳）: RECAPP: より効率的なコンベックス最適化触媒の開発
• Authors: Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
• Abstract要約: 加速近位点(RECAPP)のための新しい緩和誤差基準を提案する。 有限サムと最大構造最小化という2つの標準問題にRECAPPを適用する。 有限サム問題に対しては、以前に慎重に設計された問題固有アルゴリズムで得られた最もよく知られた複雑性と一致する。
• 参考スコア（独自算出の注目度）: 39.4418415953014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The accelerated proximal point algorithm (APPA), also known as "Catalyst", is a well-established reduction from convex optimization to approximate proximal point computation (i.e., regularized minimization). This reduction is conceptually elegant and yields strong convergence rate guarantees. However, these rates feature an extraneous logarithmic term arising from the need to compute each proximal point to high accuracy. In this work, we propose a novel Relaxed Error Criterion for Accelerated Proximal Point (RECAPP) that eliminates the need for high accuracy subproblem solutions. We apply RECAPP to two canonical problems: finite-sum and max-structured minimization. For finite-sum problems, we match the best known complexity, previously obtained by carefully-designed problem-specific algorithms. For minimizing $\max_y f(x,y)$ where $f$ is convex in $x$ and strongly-concave in $y$, we improve on the best known (Catalyst-based) bound by a logarithmic factor.
• Abstract（参考訳）: 加速近点アルゴリズム (appa) は「触媒」としても知られ、凸最適化から近似近点計算(つまり正規化最小化)への確立された還元である。 この還元は概念的にはエレガントであり、強い収束率を保証する。 しかしながら、これらの速度は、各近位点を高い精度で計算する必要から生じる対数項が特徴である。 本稿では, 高精度なサブプロブレム解の必要性を解消する新しいRelaxed Error Criterion for Accelerated Proximal Point (RECAPP)を提案する。 有限サムと最大構造最小化という2つの標準問題にRECAPPを適用する。 有限サム問題の場合、我々は最もよく知られた複雑性にマッチする。 ここで$f$が$x$で凸であり、$y$で強凹である$\max_y f(x,y)$を最小化するために、対数係数によって縛られる最もよく知られた(触媒ベースの)ものを改善する。

関連論文リスト

• Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
  離散メモリレスソースに対するRDPF(Ralse-Distortion-Perception Function)の計算について検討した。 最適パラメトリック解を特徴付ける。 歪みと知覚制約について十分な条件を提供する。
  論文  参考訳（メタデータ） (2024-08-27T12:50:12Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [14.719077076351377]
  本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。 Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
  論文  参考訳（メタデータ） (2022-08-11T16:55:26Z)
• Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
  コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。 数値実験では, 既存の再起動バージョンよりも改善が見られた。
  論文  参考訳（メタデータ） (2021-08-10T07:15:07Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization [25.73397307080647]
  本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。 本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。 我々は,新しい数値スケール問題の有効性を実証する。
  論文  参考訳（メタデータ） (2020-10-23T05:24:05Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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