論文の概要: A Batch-to-Online Transformation under Random-Order Model
- arxiv url: http://arxiv.org/abs/2306.07163v2
- Date: Wed, 25 Oct 2023 23:22:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-28 01:26:40.717199
- Title: A Batch-to-Online Transformation under Random-Order Model
- Title（参考訳）: ランダム次数モデルに基づくバッチ-オンライン変換
- Authors: Jing Dong, Yuichi Yoshida
- Abstract要約: 本稿では,オンラインアルゴリズムの開発に利用可能な変換フレームワークについて紹介する。
オンライン$(k,z)$-clustering,オンライン行列近似,オンライン回帰など,さまざまな問題に適用する。
われわれのアルゴリズムは、一部のオンラインアプリケーションで望まれる低整合性も享受している。
- 参考スコア（独自算出の注目度）: 23.817140289575377
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a transformation framework that can be utilized to develop
online algorithms with low $\epsilon$-approximate regret in the random-order
model from offline approximation algorithms. We first give a general reduction
theorem that transforms an offline approximation algorithm with low average
sensitivity to an online algorithm with low $\epsilon$-approximate regret. We
then demonstrate that offline approximation algorithms can be transformed into
a low-sensitivity version using a coreset construction method. To showcase the
versatility of our approach, we apply it to various problems, including online
$(k,z)$-clustering, online matrix approximation, and online regression, and
successfully achieve polylogarithmic $\epsilon$-approximate regret for each
problem. Moreover, we show that in all three cases, our algorithm also enjoys
low inconsistency, which may be desired in some online applications.
- Abstract（参考訳）: 我々は,オフライン近似アルゴリズムを用いたランダムオーダーモデルにおいて,$\epsilon$-approximate regretの少ないオンラインアルゴリズムを開発するためのトランスフォーメーションフレームワークを提案する。
まず、平均感度の低いオフライン近似アルゴリズムを、$\epsilon$-approximate regretの低いオンラインアルゴリズムに変換する一般化定理を提案する。
次に,オフライン近似アルゴリズムを,コアセット構成法を用いて低感度バージョンに変換できることを実証する。
提案手法の汎用性を示すために,オンライン$(k,z)$クラスタリング,オンライン行列近似,オンライン回帰など,さまざまな問題に適用し,各問題に対する後悔の多元対数$\epsilon$-approximateを達成することに成功した。
さらに,これら3事例すべてにおいて,オンラインアプリケーションで望まれる低整合性も実現可能であることを示す。
関連論文リスト
- A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization [33.38582292895673]
完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。
これを用いて、一般メタアルゴリズムを記述し、決定論的アルゴリズムを同様の後悔境界を持つゼロ次アルゴリズムに変換する。
論文 参考訳（メタデータ） (2024-02-13T17:42:27Z) - Variance Reduced Online Gradient Descent for Kernelized Pairwise
Learning with Limited Memory [19.822215548822882]
オンラインのペアワイズ学習を扱うために、オンライン勾配降下アルゴリズム(OGD)が提案されている。
OGDアルゴリズムの最近の進歩は、オンライン勾配の計算の複雑さを減らし、O(T)$未満の複雑さを達成し、たとえ$O(1)$であるとしても達成することを目的としている。
本研究では,カーネルのオンラインペアワイズ学習に拡張し,サブ線形後悔を改善したメモリOGDアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-10T09:50:54Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。
提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
論文 参考訳（メタデータ） (2023-05-12T13:53:03Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Learning Infinite-horizon Average-reward MDPs with Linear Function
Approximation [44.374427255708135]
線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。
まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。
次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
論文 参考訳（メタデータ） (2020-07-23T08:23:44Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z) - Faster Projection-free Online Learning [34.96927532439896]
我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。
提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
論文 参考訳（メタデータ） (2020-01-30T21:18:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。