論文の概要: Efficient Online Learning for Dynamic k-Clustering

• arxiv url: http://arxiv.org/abs/2106.04336v1
• Date: Tue, 8 Jun 2021 13:53:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-09 23:38:15.086265
• Title: Efficient Online Learning for Dynamic k-Clustering
• Title（参考訳）: 動的kクラスタリングのための効率的なオンライン学習
• Authors: Dimitris Fotakis, Georgios Piliouras, Stratis Skoulakis
• Abstract要約: 我々は、textitDynamic $k$-Clusteringと呼ばれるオンライン学習の問題について検討する。 いくつかのよく確立された計算予想の下では、textitconstant-regretはリアルタイムの複雑さを達成できない。 この効率的なソリューションに加えて、オンライン学習に関する長い研究にも貢献しています。
• 参考スコア（独自算出の注目度）: 32.78817940609874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called \textit{Dynamic $k$-Clustering}, in which $k$ centers are maintained in a metric space over time (centers may change positions) such as a dynamically changing set of $r$ clients is served in the best possible way. The connection cost at round $t$ is given by the \textit{$p$-norm} of the vector consisting of the distance of each client to its closest center at round $t$, for some $p\geq 1$ or $p = \infty$. We present a \textit{$\Theta\left( \min(k,r) \right)$-regret} polynomial-time online learning algorithm and show that, under some well-established computational complexity conjectures, \textit{constant-regret} cannot be achieved in polynomial-time. In addition to the efficient solution of Dynamic $k$-Clustering, our work contributes to the long line of research on combinatorial online learning.
• Abstract（参考訳）: オンライン学習の観点から動的クラスタリング問題を考察する。 オンライン学習問題である \textit{dynamic $k$-clustering} を考えると、k$センターは時間とともにメートル空間で維持され(センターは位置を変える可能性がある)、例えば動的に変化する$r$クライアントのセットは最善の方法で提供されます。 ラウンド$t$の接続コストは、ある$p\geq 1$または$p = \infty$に対して、各クライアントからラウンド$t$の最も近い中心までの距離からなるベクトルの \textit{$p$-norm} によって与えられる。 我々は、多項式時間オンライン学習アルゴリズム \textit{$\theta\left( \min(k,r) \right)$-regret} を提示し、いくつかの確立された計算複雑性予想の下では、多項式時間において \textit{constant-regret} は達成できないことを示す。 Dynamic $k$-Clusteringの効率的なソリューションに加えて、我々の研究は組合せオンライン学習に関する長い研究に寄与している。

関連論文リスト

• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。 得られた解法は数値的に安定かつ高速であることを示す。
  論文  参考訳（メタデータ） (2024-04-25T12:09:16Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
  我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。 私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
  論文  参考訳（メタデータ） (2023-06-05T12:22:46Z)
• Fast Online Node Labeling for Very Large Graphs [11.700626862639131]
  現在のメソッドは、$mathcalO(n3)$または$mathcalO(n2)$スペースの複雑さでグラフカーネルランタイムマトリックスを反転させるか、ランダムなスパンニングツリーを大量にサンプリングする。 本稿では,一連の研究によって導入されたテクスチトリン緩和技術に基づく改善を提案する。
  論文  参考訳（メタデータ） (2023-05-25T17:13:08Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Efficient Online-Bandit Strategies for Minimax Learning Problems [21.300877551771197]
  いくつかの学習問題は、例えば、実験的な分散ロバスト学習や、非標準集約的損失による最小化といった、min-max問題の解決に関係している。 具体的には、これらの問題は、モデルパラメータ$winmathcalW$と、トレーニングセットの実証分布$pinmathcalK$で学習を行う凸線型問題である。 効率的な手法を設計するために、オンライン学習アルゴリズムを(組合せ)帯域幅アルゴリズムと対戦させる。
  論文  参考訳（メタデータ） (2021-05-28T16:01:42Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Online Learning with Vector Costs and Bandits with Knapsacks [8.340947016086739]
  オンライン学習にベクターコスト(OLVCp)を導入し、各時間に1,ldots,T$の$tのステップで、未知のベクターコストを発生させるアクションを実行する必要がある。 オンラインアルゴリズムの目標は、コストベクトルの和の$ell_p$ノルムを最小化することである。
  論文  参考訳（メタデータ） (2020-10-14T18:28:41Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)

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

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