論文の概要: Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator

• arxiv url: http://arxiv.org/abs/2206.09370v1
• Date: Sun, 19 Jun 2022 10:24:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-22 15:22:05.260406
• Title: Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator
• Title（参考訳）: フランクウルフに基づくタイラーのm推定器近似アルゴリズム
• Authors: Lior Danon, Dan Garber
• Abstract要約: 1つの変種はフランク=ウルフの標準的なステップを使用し、もう1つはテキスト・ウェイ・ステップ(AFW)も考慮している。 3つ目は AFW (GAFW) のテキストジオデシック版である
• 参考スコア（独自算出の注目度）: 19.24470467199451
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tyler's M-estimator is a well known procedure for robust and heavy-tailed covariance estimation. Tyler himself suggested an iterative fixed-point algorithm for computing his estimator however, it requires super-linear (in the size of the data) runtime per iteration, which may be prohibitive in large scale. In this work we propose, to the best of our knowledge, the first Frank-Wolfe-based algorithms for computing Tyler's estimator. One variant uses standard Frank-Wolfe steps, the second also considers \textit{away-steps} (AFW), and the third is a \textit{geodesic} version of AFW (GAFW). AFW provably requires, up to a log factor, only linear time per iteration, while GAFW runs in linear time (up to a log factor) in a large $n$ (number of data-points) regime. All three variants are shown to provably converge to the optimal solution with sublinear rate, under standard assumptions, despite the fact that the underlying optimization problem is not convex nor smooth. Under an additional fairly mild assumption, that holds with probability 1 when the (normalized) data-points are i.i.d. samples from a continuous distribution supported on the entire unit sphere, AFW and GAFW are proved to converge with linear rates. Importantly, all three variants are parameter-free and use adaptive step-sizes.
• Abstract（参考訳）: タイラーのM-推定器は、頑健で重み付き共分散推定のためのよく知られた手順である。 タイラー自身は、彼の推定値を計算するために反復固定点アルゴリズムを提案したが、それはイテレーション毎の超線形(データのサイズ)ランタイムを必要とする。 この研究では、我々の知る限りでは、タイラーの推定値を計算する最初のフランクウルフベースのアルゴリズムを提案する。 1つの変種は標準的なフランク=ウルフステップを使用し、もう1つは \textit{away-steps} (afw)、もう1つは afw (gafw) の \textit{geodesic} バージョンである。 AFWは、ログファクタまで、イテレーション毎の線形時間しか必要とせず、GAFWは大規模な$n$(データポイントの数)で線形時間(ログファクタまで)で動作する。 3つの変種は、根底にある最適化問題は凸や滑らかではないにもかかわらず、標準仮定の下で、最適解に正に準線形率で収束することが示される。 さらに、(正規化された)データポイントが単位球全体に支持される連続分布からのサンプルであるとき、確率 1 で成り立つ仮定では、AFW とGAFW は線形速度に収束することが証明される。 重要なことに、これら3つのバリエーションはパラメータフリーであり、適応ステップサイズを使用する。

関連論文リスト

• Highly Adaptive Ridge [84.38107748875144]
  直交可積分な部分微分を持つ右連続函数のクラスにおいて,$n-2/3$自由次元L2収束率を達成する回帰法を提案する。 Harは、飽和ゼロオーダーテンソル積スプライン基底展開に基づいて、特定のデータ適応型カーネルで正確にカーネルリッジレグレッションを行う。 我々は、特に小さなデータセットに対する最先端アルゴリズムよりも経験的性能が優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-03T17:06:06Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Frank Wolfe Meets Metric Entropy [0.0]
  フランク=ウルフの領域固有かつ容易に推定できる下界を確立する手法を提案する。 次元自由線型上界は、最悪の場合だけでなく、Emph平均の場合も失敗しなければならないことを示す。 また、核標準球にもこの現象が成立する。
  論文  参考訳（メタデータ） (2022-05-17T21:23:36Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps [66.88729048402082]
  一般化自己一致は、多くの学習問題の目的関数に存在する重要な特性である。 検討対象の領域が一様凸あるいは多面体である場合など,様々な症例に対する収束率の改善を示す。
  論文  参考訳（メタデータ） (2021-05-28T15:26:36Z)
• Enhancing Parameter-Free Frank Wolfe with an Extra Subproblem [75.83472151564185]
  この研究では、ExtraFWと呼ばれるFrank Wolfe(FW)アルゴリズムの変種を導入し、分析する。 ExtraFWは、予測補正(PC)フォーマットで決定変数が更新されるため、イテレーション毎に活用される勾配のペアである。 他のパラメータフリーなFW変種と比較すると、同じ問題でより高速なレートを持つが、ExtraFWはPCのアップデートによって速度ときめ細かい分析を改善している。
  論文  参考訳（メタデータ） (2020-12-09T19:47:24Z)
• Revisiting Projection-free Online Learning: the Strongly Convex Case [21.30065439295409]
  射影のない最適化アルゴリズムは主に古典的フランク・ウルフ法に基づいている。 オンラインFrank-Wolfe法は、強い凸関数上でのO(T2/3)$の高速化を実現する。
  論文  参考訳（メタデータ） (2020-10-15T07:45:01Z)
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization [30.980431848476925]
  線形予測・構造を一般化した制約付き有限滑らかサム最小化アルゴリズムを提案する。 提案手法は実装が簡単で,ステップサイズチューニングを必要としない。 オープンソースパッケージで検討されたすべてのメソッドの実装を提供する。
  論文  参考訳（メタデータ） (2020-02-27T00:47:21Z)
• 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)

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

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