論文の概要: 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)$という最適加速収束保証が導かれる。
我々のアルゴリズムと解析は、滑らかかつ強い凸集合のミンコフスキーゲージの新たな特徴付けに基づいているが、これは独立興味を持つかもしれない: ゲージは滑らかでも強凸でもないが、ゲージの平方形がその集合に存在する任意の構造を継承していることを示す。
関連論文リスト
- An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth
Nonconvex Stochastic Optimization [44.065130483176944]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
我々の分析は、最近の進歩を活用できる単純だが強力な集合に基づいている。
論文 参考訳(メタデータ) (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) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳(メタデータ) (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。