論文の概要: Frank-Wolfe with a Nearest Extreme Point Oracle

• arxiv url: http://arxiv.org/abs/2102.02029v1
• Date: Wed, 3 Feb 2021 12:20:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-04 17:38:53.935724
• Title: Frank-Wolfe with a Nearest Extreme Point Oracle
• Title（参考訳）: Frank-Wolfe が Oracle に近づいた
• Authors: Dan Garber, Noam Wolf
• Abstract要約: 制約付き滑らかな凸性に対する古典的フランク・ウルフアルゴリズムの変種を考察する。 多くの実効性のある集合に対して、そのようなオラクルは標準的な線形最適化オラクルと同じ複雑さで実装可能であることを示す。 我々は、最適面の次元にのみ依存し、周囲次元に依存しない速度で、最初の線型収束不変量を得る。
• 参考スコア（独自算出の注目度）: 25.944852633880068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider variants of the classical Frank-Wolfe algorithm for constrained smooth convex minimization, that instead of access to the standard oracle for minimizing a linear function over the feasible set, have access to an oracle that can find an extreme point of the feasible set that is closest in Euclidean distance to a given vector. We first show that for many feasible sets of interest, such an oracle can be implemented with the same complexity as the standard linear optimization oracle. We then show that with such an oracle we can design new Frank-Wolfe variants which enjoy significantly improved complexity bounds in case the set of optimal solutions lies in the convex hull of a subset of extreme points with small diameter (e.g., a low-dimensional face of a polytope). In particular, for many $0\text{--}1$ polytopes, under quadratic growth and strict complementarity conditions, we obtain the first linearly convergent variant with rate that depends only on the dimension of the optimal face and not on the ambient dimension.
• Abstract（参考訳）: 制約付き滑らかな凸最小化のための古典的なフランク・ウルフアルゴリズムの変種を考えると、実現可能集合上の線型関数を最小化するための標準オラクルにアクセスする代わりに、与えられたベクトルとユークリッド距離で最も近い実現可能集合の極端点を見つけることができるオラクルにアクセスする。 まず、多くの実効性のある集合に対して、そのようなオラクルは標準的な線形最適化オラクルと同じ複雑さで実装できることを示す。 すると、そのようなオラクルを用いて、最適解の集合が小径の極小点の部分集合(例えばポリトープの低次元面)の凸包にある場合の複雑性境界を著しく改善したフランク=ウルフ多様体を設計できることを示す。 特に、多くの$0\text{--}1$ポリトープにおいて、2次成長と厳密な相補性条件の下で、最適な面の次元のみに依存し、周囲次元に依存しない最初の線形収束型が得られる。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• 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)
• First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
  合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。 本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
  論文  参考訳（メタデータ） (2023-07-14T19:59:18Z)
• Riemannian Projection-free Online Learning [5.918057694291832]
  プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。 これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。 本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:22:09Z)
• Efficient Projection-Free Online Convex Optimization with Membership Oracle [11.745866777357566]
  ユークリッド球上で定義された任意のアルゴリズムAを、球に含まれる制約付き集合 C 上のアルゴリズムに変換する新しい還元法を提案する。 我々の削減には、O(T log T) を T ラウンド後に C 上で Oracle に呼び出しる必要があり、C 上の線形最適化は不要である。
  論文  参考訳（メタデータ） (2021-11-10T17:22:29Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method [54.93433440034386]
  実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。 提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
  論文  参考訳（メタデータ） (2020-10-05T08:16:56Z)
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity [19.24470467199451]
  フランク=ウルフのアルゴリズムは最適面の次元にのみ依存する速度で線形に収束することを示す。 ノイズに対する最適解の疎結合性を示すことを証明して、厳密な相補性を動機づける。
  論文  参考訳（メタデータ） (2020-05-31T16:48:10Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

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

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