論文の概要: Smooth Quasar-Convex Optimization with Constraints

• arxiv url: http://arxiv.org/abs/2510.01943v1
• Date: Thu, 02 Oct 2025 12:07:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 14:32:17.26979
• Title: Smooth Quasar-Convex Optimization with Constraints
• Title（参考訳）: 制約付き滑らかな擬似凸最適化
• Authors: David Martínez-Rubio,
• Abstract要約: 一般凸制約付き擬似t滑らか関数について検討した。 一般制約付きクエーサー-t滑らか関数の1次法について述べる。
• 参考スコア（独自算出の注目度）: 4.1288208387994905
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current nearly optimal algorithms work only in affine spaces due to the loss of one degree of freedom when working with general convex constraints. Obtaining an accelerated algorithm that makes nearly optimal $\widetilde{O}(1/(\gamma\sqrt{\epsilon}))$ first-order queries to a $\gamma$-quasar convex smooth function \emph{with constraints} was independently asked as an open problem in Mart\'inez-Rubio (2022); Lezane, Langer, and Koolen (2024). In this work, we solve this question by designing an inexact accelerated proximal point algorithm that we implement using a first-order method achieving the aforementioned rate and, as a consequence, we improve the complexity of the accelerated geodesically Riemannian optimization solution in Mart\'inez-Rubio (2022). We also analyze projected gradient descent and Frank-Wolfe algorithms in this constrained quasar-convex setting. To the best of our knowledge, our work provides the first analyses of first-order methods for quasar-convex smooth functions with general convex constraints.
• Abstract（参考訳）: 準凸函数は、線型力学系、一般化線型モデル、リーマン最適化などに応用される広い非凸類を形成する。 現在の近似アルゴリズムは、一般凸制約を扱う際に一自由度が失われるため、アフィン空間でのみ機能する。 ほぼ最適に$\widetilde{O}(1/(\gamma\sqrt{\epsilon}))$ 1次クエリを$\gamma$-quasar convex smooth function \emph{with constraints} に生成する加速アルゴリズムの取得は、Mart\'inez-Rubio (2022), Lezane, Langer, Koolen (2024), の開問題として独立に求められた。 本研究では、上記の速度を達成する一階法を用いて実装した不正確な加速近位点アルゴリズムを設計し、その結果、Mart\inez-Rubio (2022) における加速された測地的リーマン最適化解の複雑さを改善する。 また、この制約付き準凸設定において、射影勾配降下とフランク・ウルフアルゴリズムを解析する。 我々の知識を最大限に活用するために、我々の研究は、一般凸制約付き準凸滑らかな関数に対する一階法を初めて分析する。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.1044138971639734]
  強い凸関数制約を受ける凸関数を最小化するために,高速化された原始双対アルゴリズムを導入する。 特にGoogleのパーソナライズされたPageRank問題では、スパシティ誘導最適化におけるメソッドのパフォーマンスが優れています。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• 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)

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

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