論文の概要: 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を動的に拡張するアルゴリズムを設計する。
木の専門家を基盤とした手法を駆使して,すべてのプルーニングと同時かつ効率的に競い合い,各スケーリングに異なる局所正則性を伴う量で後悔の限界を証明した。
単純な"局所性プロファイルと競合する場合、我々の手法は、以前のアプローチで証明されたよりもはるかに良い後悔の限界を提供する。
一方、我々の境界の時間依存は、局所正規性を無視して得られるものよりも悪くはない。
関連論文リスト
- Locally Adaptive One-Class Classifier Fusion with Dynamic $\ell$p-Norm Constraints for Robust Anomaly Detection [17.93058599783703]
局所的なデータ特性に基づいて,融合重みを動的に調整するフレームワークを提案する。
本手法は,計算効率を大幅に向上させる内部点最適化手法を取り入れたものである。
計算効率を維持しながらローカルなデータパターンに適応できるフレームワークの能力は、リアルタイムアプリケーションに特に有用である。
論文 参考訳(メタデータ) (2024-11-10T09:57:13Z) - Minimax Adaptive Boosting for Online Nonparametric Regression [10.138723409205497]
本稿では,非パラメトリック回帰に対するパラメータフリーオンライン勾配向上アルゴリズムを提案する。
連鎖木への応用は、リプシッツ関数と競合する際の極小極小後悔を達成できることを示す。
論文 参考訳(メタデータ) (2024-10-04T12:30:03Z) - A General Online Algorithm for Optimizing Complex Performance Metrics [5.726378955570775]
我々は,バイナリ,マルチクラス,マルチラベルの分類問題において,様々な複雑なパフォーマンス指標を用いて,直接的に使用可能な汎用オンラインアルゴリズムを導入,分析する。
アルゴリズムの更新と予測のルールは、過去のデータを保存することなく、非常にシンプルで計算的に効率的である。
論文 参考訳(メタデータ) (2024-06-20T21:24:47Z) - Local Sample-weighted Multiple Kernel Clustering with Consensus
Discriminative Graph [73.68184322526338]
マルチカーネルクラスタリング(MKC)は、ベースカーネルの集合から最適な情報融合を実現するためにコミットされる。
本稿では,新しい局所サンプル重み付きマルチカーネルクラスタリングモデルを提案する。
実験により, LSWMKCはより優れた局所多様体表現を有し, 既存のカーネルやグラフベースのクラスタリングアルゴリズムよりも優れていた。
論文 参考訳(メタデータ) (2022-07-05T05:00:38Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。