論文の概要: Complexity Bounds for Smooth Convex Multiobjective Optimization

• arxiv url: http://arxiv.org/abs/2509.13550v1
• Date: Tue, 16 Sep 2025 21:33:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-18 18:41:50.658592
• Title: Complexity Bounds for Smooth Convex Multiobjective Optimization
• Title（参考訳）: 滑らか凸多目的最適化のための複素境界
• Authors: Phillipe R. Sampaio,
• Abstract要約: 目的値$m$の滑らかな多目的最適化において,$varepsilon$-Pareto定常点を求める際のオラクルの複雑さについて検討する。 強い凸目的に対して、任意の一階法は、$exp(-Theta(T/sqrtkappa)$ after $T$ oracle call よりも早く線形収束を示す。 適応スカラー化を伴う凸問題や一般スパン法に対して、最終イテレートの勾配ノルムに1/T2$の普遍的下界を確立する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the oracle complexity of finding $\varepsilon$-Pareto stationary points in smooth multiobjective optimization with $m$ objectives. The progress metric is the Pareto stationarity gap $\mathcal{G}(x)$ (the norm of an optimal convex combination of gradients). Our contributions are fourfold. (i) For strongly convex objectives, any span first-order method (iterates lie in the span of past gradients) exhibits linear convergence no faster than $\exp(-\Theta(T/\sqrt{\kappa}))$ after $T$ oracle calls, where $\kappa$ is the condition number, implying $\Theta(\sqrt{\kappa}\log(1/\varepsilon))$ iterations; this matches classical accelerated upper bounds. (ii) For convex problems and oblivious one-step methods (a fixed scalarization with pre-scheduled step sizes), we prove a lower bound of order $1/T$ on the best gradient norm among the first $T$ iterates. (iii) Although accelerated gradient descent is outside this restricted class, it is an oblivious span method and attains the same $1/T$ upper rate on a fixed scalarization. (iv) For convex problems and general span methods with adaptive scalarizations, we establish a universal lower bound of order $1/T^{2}$ on the gradient norm of the final iterate after $T$ steps, highlighting a gap between known upper bounds and worst-case guarantees. All bounds hold on non-degenerate instances with distinct objectives and non-singleton Pareto fronts; rates are stated up to universal constants and natural problem scaling.
• Abstract（参考訳）: 目的量$m$の滑らかな多目的最適化において,$\varepsilon$-Pareto定常点を求めるというオラクルの複雑さについて検討する。 進行距離はパレート定常ギャップ$\mathcal{G}(x)$(勾配の最適凸結合のノルム)である。 私たちの貢献は4倍です。 (i) 強い凸目的に対して、任意のスパン一階法(過去の勾配の範囲内にある項目)は、$\exp(-\Theta(T/\sqrt{\kappa}))$の後の線形収束を示し、$T$ oracleコールでは$\kappa$は条件番号であり、$\Theta(\sqrt{\kappa}\log(1/\varepsilon)$の反復を暗示する。 (II) 凸問題や難解な一段階法(事前スケジュールされたステップサイズによる固定スカラー化)に対して、最初の$T$イテレートのうちの最高の勾配ノルムに対して1/T$の下位境界を証明する。 3) 勾配勾配の加速は, この制限されたクラスの外にあるが, 不可避なスパン法であり, 固定スカラー化において同じ1/T$の上限値に達する。 (4) 適応スカラー化を伴う凸問題や一般スパン法に対しては, 既知上界と最悪の場合の保証とのギャップを浮き彫りにして, 最終イテレートの勾配ノルムに1/T^{2}$の普遍的下界を定めている。 すべての境界は、異なる目的と非シングルトンパレートフロントを持つ非退化インスタンスに成り立つ; 速度は普遍定数と自然問題スケーリングに比例する。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
  本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。 線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
  論文  参考訳（メタデータ） (2024-06-18T16:41:21Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  この楽観的な手法は凸凹点問題の解法として人気が高まっている。 我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
  論文  参考訳（メタデータ） (2022-02-19T20:31:05Z)
• Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
  線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
  論文  参考訳（メタデータ） (2021-12-30T20:31:46Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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