論文の概要: Frank Wolfe Meets Metric Entropy
- arxiv url: http://arxiv.org/abs/2205.08634v1
- Date: Tue, 17 May 2022 21:23:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-19 22:24:14.068020
- Title: Frank Wolfe Meets Metric Entropy
- Title（参考訳）: Frank Wolfe氏がMetric Entropyについて語る
- Authors: Suhas Vijaykumar
- Abstract要約: フランク=ウルフの領域固有かつ容易に推定できる下界を確立する手法を提案する。
次元自由線型上界は、最悪の場合だけでなく、Emph平均の場合も失敗しなければならないことを示す。
また、核標準球にもこの現象が成立する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Frank-Wolfe algorithm has seen a resurgence in popularity due to its
ability to efficiently solve constrained optimization problems in machine
learning and high-dimensional statistics. As such, there is much interest in
establishing when the algorithm may possess a "linear" $O(\log(1/\epsilon))$
dimension-free iteration complexity comparable to projected gradient descent.
In this paper, we provide a general technique for establishing domain
specific and easy-to-estimate lower bounds for Frank-Wolfe and its variants
using the metric entropy of the domain. Most notably, we show that a
dimension-free linear upper bound must fail not only in the worst case, but in
the \emph{average case}: for a Gaussian or spherical random polytope in
$\mathbb{R}^d$ with $\mathrm{poly}(d)$ vertices, Frank-Wolfe requires up to
$\tilde\Omega(d)$ iterations to achieve a $O(1/d)$ error bound, with high
probability. We also establish this phenomenon for the nuclear norm ball.
The link with metric entropy also has interesting positive implications for
conditional gradient algorithms in statistics, such as gradient boosting and
matching pursuit. In particular, we show that it is possible to extract
fast-decaying upper bounds on the excess risk directly from an analysis of the
underlying optimization procedure.
- Abstract（参考訳）: フランク=ウルフのアルゴリズムは、機械学習と高次元統計学における制約付き最適化問題を効率的に解く能力により、人気が回復した。
このように、アルゴリズムが「線形」$o(\log(1/\epsilon))$次元フリーの反復複雑性を持つ場合の確立には多くの関心がある。
本稿では,frank-wolfeとその変種に対して,領域の計量エントロピーを用いて,ドメイン固有かつ評価容易な下限を定式化する一般的な手法を提案する。
最も注目すべきは、次元のない線形上界は、最悪の場合だけでなく、 \emph{average case} において失敗することである: $\mathbb{r}^d$ で$\mathrm{poly}(d)$ 頂点を持つガウスあるいは球状ランダムポリトープに対して、frank-wolfe は$o(1/d)$ の誤差境界を達成するために最大$\tilde\omega(d)$ の反復が必要である。
また、核標準球にもこの現象が成立する。
計量エントロピーとのリンクはまた、勾配強化やマッチング追従のような統計学における条件付き勾配アルゴリズムに興味深いポジティブな意味を持つ。
特に、基礎となる最適化手順の分析から直接、過剰なリスクの高速決定上限を抽出することが可能であることを示す。
関連論文リスト
- High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
最適解への初期距離に依存する有界収束を示す。
AdaGrad-Normのハイバウンドが得られることを示す。
論文 参考訳（メタデータ） (2023-02-28T18:42:11Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Parameter-free Regret in High Probability with Heavy Tails [45.11667443216861]
非有界領域に対するオンライン凸最適化のための新しいアルゴリズムを提案する。
高確率のパラメータフリーな後悔は、潜在的に重み付き下次推定にのみアクセス可能である。
論文 参考訳（メタデータ） (2022-10-25T21:43:44Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization [7.197233473373693]
2つの凸関数の和を最小化する問題を考える。
1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。
我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
論文 参考訳（メタデータ） (2022-05-25T13:01:09Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Boosting Frank-Wolfe by Chasing Gradients [26.042029798821375]
本稿では,降下方向をサブルーチンによる負勾配に整合させることにより,Frank-Wolfeアルゴリズムの高速化を提案する。
我々は、一連の計算実験において、反復時間とCPU時間の両方において、その競争上の優位性を実証する。
論文 参考訳（メタデータ） (2020-03-13T16:29:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。