論文の概要: Locally-Adaptive Nonparametric Online Learning
- arxiv url: http://arxiv.org/abs/2002.01882v2
- Date: Sun, 1 Nov 2020 14:37:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 21:01:11.172013
- Title: Locally-Adaptive Nonparametric Online Learning
- Title(参考訳): 局所適応型非パラメトリックオンライン学習
- Authors: Ilja Kuzborskij, Nicol\`o Cesa-Bianchi
- Abstract要約: 任意のデータシーケンスに適応する効率的なオンラインアルゴリズムを導入する。
木の専門家をベースとした手法を用いて、このような刈り取りと効率的に競合する。
我々の手法は、以前のアプローチで証明されたものよりもはるかに優れた後悔の限界を提供する。
- 参考スコア(独自算出の注目度): 12.018422134251384
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the main strengths of online algorithms is their ability to adapt to
arbitrary data sequences. This is especially important in nonparametric
settings, where performance is measured against rich classes of comparator
functions that are able to fit complex environments. Although such hard
comparators and complex environments may exhibit local regularities, efficient
algorithms, which can provably take advantage of these local patterns, are
hardly known. We fill this gap by introducing efficient online algorithms
(based on a single versatile master algorithm) each adapting to one of the
following regularities: (i) local Lipschitzness of the competitor function,
(ii) local metric dimension of the instance sequence, (iii) local performance
of the predictor across different regions of the instance space. Extending
previous approaches, we design algorithms that dynamically grow hierarchical
$\epsilon$-nets on the instance space whose prunings correspond to different
"locality profiles" for the problem at hand. Using a technique based on tree
experts, we simultaneously and efficiently compete against all such prunings,
and prove regret bounds each scaling with a quantity associated with a
different type of local regularity. When competing against "simple" locality
profiles, our technique delivers regret bounds that are significantly better
than those proven using the previous approach. On the other hand, the time
dependence of our bounds is not worse than that obtained by ignoring any local
regularities.
- Abstract(参考訳): オンラインアルゴリズムの主な強みの1つは、任意のデータシーケンスに適応する能力である。
これは、複雑な環境に適合する豊富なコンパレータ関数のクラスに対してパフォーマンスを測定する非パラメトリックな設定において特に重要である。
このようなハードコンパレータや複雑な環境は局所規則性を示すかもしれないが、これらの局所パターンを確実に活用できる効率的なアルゴリズムはほとんど知られていない。
このギャップを埋めるために、より効率的なオンラインアルゴリズム(単一の汎用マスターアルゴリズムに基づく)を導入する。
(i)競合関数の局所リプシッツ性
(ii)インスタンスシーケンスの局所計量次元
(iii)インスタンス空間の異なる領域にまたがる予測器の局所的性能。
以前のアプローチを拡張して、問題に対してプラニングが異なる「局所性プロファイル」に対応するインスタンス空間上の階層的$\epsilon$-netを動的に拡張するアルゴリズムを設計する。
木の専門家を基盤とした手法を駆使して,すべてのプルーニングと同時かつ効率的に競い合い,各スケーリングに異なる局所正則性を伴う量で後悔の限界を証明した。
単純な"局所性プロファイルと競合する場合、我々の手法は、以前のアプローチで証明されたよりもはるかに良い後悔の限界を提供する。
一方、我々の境界の時間依存は、局所正規性を無視して得られるものよりも悪くはない。
関連論文リスト
- Local Sample-weighted Multiple Kernel Clustering with Consensus
Discriminative Graph [73.68184322526338]
マルチカーネルクラスタリング(MKC)は、ベースカーネルの集合から最適な情報融合を実現するためにコミットされる。
本稿では,新しい局所サンプル重み付きマルチカーネルクラスタリングモデルを提案する。
実験により, LSWMKCはより優れた局所多様体表現を有し, 既存のカーネルやグラフベースのクラスタリングアルゴリズムよりも優れていた。
論文 参考訳(メタデータ) (2022-07-05T05:00:38Z) - Spatially Adaptive Online Prediction of Piecewise Regular Functions [12.18340575383456]
オンライン環境における部分的正規関数推定の問題点を考察する。
我々は、最近開発された睡眠専門家集約アルゴリズムと呼ばれるオンライン学習アルゴリズムの修正版を提案する。
論文 参考訳(メタデータ) (2022-03-30T18:15:56Z) - Flipping the switch on local exploration: Genetic Algorithms with
Reversals [0.0]
著者らは、勾配のない探索手法が離散領域における最適解を提供するのに適していることを示した。
また、複数のローカル検索を使用することで、ローカル検索のパフォーマンスが向上することを示した。
提案したGA変種は,提案した問題を含む全てのベンチマークにおいて,最小平均コストであり,ICが構成成分よりも優れた性能を発揮することが観察された。
論文 参考訳(メタデータ) (2022-02-02T08:27:11Z) - Clustered Federated Learning via Generalized Total Variation
Minimization [83.26141667853057]
本研究では,分散ネットワーク構造を持つローカルデータセットの局所的(あるいはパーソナライズされた)モデルを学習するための最適化手法について検討する。
我々の主要な概念的貢献は、総変動最小化(GTV)としてフェデレーション学習を定式化することである。
私たちのアルゴリズムの主な貢献は、完全に分散化されたフェデレーション学習アルゴリズムです。
論文 参考訳(メタデータ) (2021-05-26T18:07:19Z) - AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods [7.486132958737807]
適応性に対する暗黙的アプローチによる適応分散低減手法を提案する。
有限サム最小化問題に対する収束保証を提供し,局所幾何が許せばサラよりも高速に収束できることを示す。
このアルゴリズムはステップサイズを暗黙的に計算し、関数の局所リプシッツ滑らかさを効率的に推定する。
論文 参考訳(メタデータ) (2021-02-19T01:17:15Z) - Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。
本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。
実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
論文 参考訳(メタデータ) (2020-07-20T12:07:48Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。
クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
論文 参考訳(メタデータ) (2020-05-22T23:07:42Z) - Stochastic batch size for adaptive regularization in deep network
optimization [63.68104397173262]
ディープラーニングフレームワークにおける機械学習問題に適用可能な適応正規化を取り入れた一階最適化アルゴリズムを提案する。
一般的なベンチマークデータセットに適用した従来のネットワークモデルに基づく画像分類タスクを用いて,提案アルゴリズムの有効性を実証的に実証した。
論文 参考訳(メタデータ) (2020-04-14T07:54:53Z) - Multi-View Optimization of Local Feature Geometry [70.18863787469805]
本研究では,複数視点からの局所像の特徴の幾何を,未知のシーンやカメラの幾何を伴わずに精査する問題に対処する。
提案手法は,従来の特徴抽出とマッチングのパラダイムを自然に補完する。
本手法は,手作りと学習の両方の局所的特徴に対して,三角測量とカメラのローカライゼーション性能を常に向上することを示す。
論文 参考訳(メタデータ) (2020-03-18T17:22:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。