論文の概要: Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

• arxiv url: http://arxiv.org/abs/2609.24423v1
• Date: Mon, 21 Sep 2026 11:17:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:01.264097
• Title: Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
• Title（参考訳）: 複合凸最適化のための弱近位オラクル法の複雑さ
• Abstract要約: 滑らかあるいは非滑らかな目的関数を持つ標準合成凸最適化問題を考える。 決定論的手法とランダム化手法の両方に対して下位境界を確立することで、負の答えを与える。
• 参考スコア（独自算出の注目度）: 10.491266065801982
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.
• Abstract（参考訳）: 滑らかあるいは非滑らかな目的関数と二次成長下での標準凸合成最適化問題を考察する。 近年では、いくつかの研究が、厳密なprox演算に依存する(部分的な)漸進的(proximal)な方法に本質的に一致する、textit{weak proximal oracle} (WPO) に基づくアルゴリズムを与えている。 重要なことは、標準的なprox演算子の強い最適条件を緩和するそのようなWPOは、最適解がスパース構造を持つ場合、実行時の観点からはるかに効率的な実装を認めるかもしれない。 そのような WPO ベースの手法が(ネステロフの加速勾配という意味で)加速できるかという疑問が残った。 この研究において、決定論的手法とランダム化手法の両方に対して下位境界を確立することにより、負の答えを与える。 したがって、WPOは個々のオラクル呼び出しのコストを大幅に削減できるが、これはオラクルの複雑さに固有の損失をもたらす。 また,WPOをベースとした非平滑凸複合最適化のための上界法も提案する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization [55.115992622028685]
  以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。 最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
  論文  参考訳（メタデータ） (2023-10-26T19:56:52Z)
• Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization [12.84152722535866]
  目的関数が弱凸あるいは弱凸である非制約最適化問題を考える。 そこで本研究では,一階調律であり,実装が容易な段階的手法について考察する。
  論文  参考訳（メタデータ） (2023-01-30T22:13:14Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• The Minimax Complexity of Distributed Optimization [0.0]
  分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。 私は「間欠的コミュニケーション設定」の具体例に焦点をあてる コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
  論文  参考訳（メタデータ） (2021-09-01T15:18:33Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)

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

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