論文の概要: Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets

• arxiv url: http://arxiv.org/abs/2303.05037v1
• Date: Thu, 9 Mar 2023 05:05:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 16:02:03.407581
• Title: Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets
• Title（参考訳）: 滑らか・強凸集合上のゲージと加速最適化
• Authors: Ning Liu, Benjamin Grimmer
• Abstract要約: 我々は、滑らかかつ/または強い凸集合上で定義される実現可能性および制約付き最適化問題を考察する。 これらの設定において,新しい拡張性,プロジェクションフリー,アクセラレーションファーストオーダー手法を提案する。
• 参考スコア（独自算出の注目度）: 5.2293965497039165
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider feasibility and constrained optimization problems defined over smooth and/or strongly convex sets. These notions mirror their popular function counterparts but are much less explored in the first-order optimization literature. We propose new scalable, projection-free, accelerated first-order methods in these settings. Our methods avoid linear optimization or projection oracles, only using cheap one-dimensional linesearches and normal vector computations. Despite this, we derive optimal accelerated convergence guarantees of $O(1/T)$ for strongly convex problems, $O(1/T^2)$ for smooth problems, and accelerated linear convergence given both. Our algorithms and analysis are based on novel characterizations of the Minkowski gauge of smooth and/or strongly convex sets, which may be of independent interest: although the gauge is neither smooth nor strongly convex, we show the gauge squared inherits any structure present in the set.
• Abstract（参考訳）: 滑らかかつ強凸集合上で定義される実現可能性と制約付き最適化問題を考える。 これらの概念は一般的な関数を反映しているが、一階最適化の文献では明らかに研究されていない。 これらの設定において,新しい拡張性,プロジェクションフリー,アクセラレーションファーストオーダー手法を提案する。 提案手法は,安価な一次元線形探索と通常のベクトル計算のみを用いて,線形最適化や射影オラクルを回避する。 それにもかかわらず、強凸問題に対しては$o(1/t)$、滑らかな問題では$o(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)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Algorithm for Constrained Linear Inverse Problems [5.0490573482829335]
  我々は、ある原子ノルムが2次制約の下で最小化される制約付き線形逆問題(LIP)を考える。 凸正則性を改善した制約付きLIPの2つの等価な再構成を提案する。 FLIPSの2成分選択,圧縮センシング,画像デノーミングの古典的問題に対する性能を実証する。
  論文  参考訳（メタデータ） (2022-12-02T10:12:14Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。 この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。 滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
  論文  参考訳（メタデータ） (2020-10-22T22:54:54Z)
• 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)

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

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