論文の概要: Scalable Projection-Free Optimization
- arxiv url: http://arxiv.org/abs/2105.03527v1
- Date: Fri, 7 May 2021 22:27:18 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-11 14:40:07.617662
- Title: Scalable Projection-Free Optimization
- Title(参考訳): スケーラブルプロジェクションフリー最適化
- Authors: Mingrui Zhang
- Abstract要約: プロジェクションフリーのアルゴリズムとして、FW(Frank-Wolfe)は機械学習コミュニティで注目されている。
まず、イテレーションごとに1つのサンプルのみを必要とするスケーラブルなプロジェクションフリー最適化方法を提案します。
次に、凸関数と非客観的関数の両方に対応する分散Frank-Wolfe(FW)フレームワークを開発します。
- 参考スコア(独自算出の注目度): 7.170441928038049
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As a projection-free algorithm, Frank-Wolfe (FW) method, also known as
conditional gradient, has recently received considerable attention in the
machine learning community. In this dissertation, we study several topics on
the FW variants for scalable projection-free optimization.
We first propose 1-SFW, the first projection-free method that requires only
one sample per iteration to update the optimization variable and yet achieves
the best known complexity bounds for convex, non-convex, and monotone
DR-submodular settings. Then we move forward to the distributed setting, and
develop Quantized Frank-Wolfe (QFW), a general communication-efficient
distributed FW framework for both convex and non-convex objective functions. We
study the performance of QFW in two widely recognized settings: 1) stochastic
optimization and 2) finite-sum optimization. Finally, we propose Black-Box
Continuous Greedy, a derivative-free and projection-free algorithm, that
maximizes a monotone continuous DR-submodular function over a bounded convex
body in Euclidean space.
- Abstract(参考訳): プロジェクションフリーなアルゴリズムとして、frank-wolfe(fw)法は条件勾配としても知られ、機械学習コミュニティで最近注目されている。
本稿では,スケーラブルなプロジェクションフリー最適化のためのfw変種について,いくつかのトピックについて検討する。
最初に提案する1-SFWは,1回に1回のサンプルしか必要とせず,コンベックス,非凸,モノトンDR-サブモジュラー設定において最もよく知られた複雑性境界を実現する。
次に、分散設定に向けて前進し、凸関数と非凸関数の両方を対象とした一般的な通信効率の分散FWフレームワークであるQuantized Frank-Wolfe (QFW) を開発した。
1)確率的最適化と2)有限サム最適化の2つの広く認識されている環境でのQFWの性能について検討する。
最後に, ユークリッド空間上の有界凸体上の単調連続DR-部分モジュラ関数を最大化する, 微分自由かつ投影自由なアルゴリズムであるBlack-Box Continuous Greedyを提案する。
関連論文リスト
- Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳(メタデータ) (2024-02-16T16:35:18Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates
and Practical Features [79.39965431772626]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳(メタデータ) (2023-04-23T20:05:09Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Minibatch and Momentum Model-based Methods for Stochastic Non-smooth
Non-convex Optimization [3.4809730725241597]
モデルベース手法に対する2つの重要な拡張を行う。
まず,各イテレーションのモデル関数を近似するために,サンプルの集合を用いる新しいミニバッチを提案する。
第二に、運動量法の成功により、新しい凸モデルを提案する。
論文 参考訳(メタデータ) (2021-06-06T05:31:57Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Accelerated Algorithms for Convex and Non-Convex Optimization on
Manifolds [9.632674803757475]
距離における凸問題と非最適化問題の解法を提案する。
提案アルゴリズムは,目的関数における複雑性のレベルに適応する。
論文 参考訳(メタデータ) (2020-10-18T02:48:22Z) - Projection-Free Adaptive Gradients for Large-Scale Optimization [22.0439695290991]
フランク=ウルフアルゴリズムは、目的から近似した一階情報のみをクエリすることで、両方の計算負担を軽減するため、ユニークな位置を占める。
本手法は,制約付き最適化のための適応アルゴリズムの性能を向上させることができることを示す。
論文 参考訳(メタデータ) (2020-09-29T15:56:12Z) - 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) - Self-Concordant Analysis of Frank-Wolfe Algorithms [3.3598755777055374]
ポアソン逆問題 (Poisson inverse problem) や量子状態トモグラフィー (quantum state tomography) など、多くの応用において、損失は非有界曲率を持つ自己協和関数 (SC) によって与えられる。
SC関数の理論を用いて、FW法の新たな適応ステップサイズを提供し、k反復後の大域収束率 O(1/k) を証明する。
論文 参考訳(メタデータ) (2020-02-11T11:30:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。