論文の概要: Efficient Online Large-Margin Classification via Dual Certificates

• arxiv url: http://arxiv.org/abs/2509.19670v1
• Date: Wed, 24 Sep 2025 01:07:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-25 20:53:19.649405
• Title: Efficient Online Large-Margin Classification via Dual Certificates
• Title（参考訳）: Dual Certificatesによるオンライン大規模分類の効率化
• Authors: Nam Ho-Nguyen, Fatma Kılınç-Karzan, Ellie Nguyen, Lingqing Shen,
• Abstract要約: 双対定式化によるオフライン最大マージン問題について検討する。 得られた幾何学的洞察を用いて、オンライン設定のための原理的で効率的なアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 0.2099922236065961
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online classification is a central problem in optimization, statistical learning and data science. Classical algorithms such as the perceptron offer efficient updates and finite mistake guarantees on linearly separable data, but they do not exploit the underlying geometric structure of the classification problem. We study the offline maximum margin problem through its dual formulation and use the resulting geometric insights to design a principled and efficient algorithm for the online setting. A key feature of our method is its translation invariance, inherited from the offline formulation, which plays a central role in its performance analysis. Our theoretical analysis yields improved mistake and margin bounds that depend only on translation-invariant quantities, offering stronger guarantees than existing algorithms under the same assumptions in favorable settings. In particular, we identify a parameter regime where our algorithm makes at most two mistakes per sequence, whereas the perceptron can be forced to make arbitrarily many mistakes. Our numerical study on real data further demonstrates that our method matches the computational efficiency of existing online algorithms, while significantly outperforming them in accuracy.
• Abstract（参考訳）: オンライン分類は、最適化、統計学習、データサイエンスにおいて中心的な問題である。 パーセプトロンのような古典的なアルゴリズムは、線形分離可能なデータに対して効率的な更新と有限の誤り保証を提供するが、それらは分類問題の基本的な幾何学的構造を利用しない。 オフラインの最大マージン問題をその双対定式化を通して検討し、結果として得られる幾何学的洞察を用いて、オンライン設定のための原理的かつ効率的なアルゴリズムを設計する。 本手法の重要な特徴は,オフラインの定式化から受け継いだ翻訳不変性であり,その性能解析において中心的な役割を担っている。 我々の理論的解析は、翻訳不変量にのみ依存する誤りとマージン境界を改良し、同じ仮定の下で有利な設定で既存のアルゴリズムよりも強い保証を提供する。 特に、アルゴリズムがシーケンス毎に少なくとも2つの誤りを犯すパラメータ構造を同定する一方、パーセプトロンは任意に多くの誤りを犯すことができる。 実データに対する数値的な研究により,提案手法は既存のオンラインアルゴリズムの計算効率とよく一致し,精度は著しく向上した。

関連論文リスト

• Online-BLS: An Accurate and Efficient Online Broad Learning System for Data Stream Classification [52.251569042852815]
  オンライン更新毎にクローズドフォームソリューションを備えたオンライン広範学習システムフレームワークを導入する。 我々は,効果的な重み推定アルゴリズムと効率的なオンライン更新戦略を設計する。 我々のフレームワークは、コンセプトドリフトを伴うデータストリームシナリオに自然に拡張され、最先端のベースラインを超えます。
  論文  参考訳（メタデータ） (2025-01-28T13:21:59Z)
• A General Online Algorithm for Optimizing Complex Performance Metrics [5.726378955570775]
  我々は,バイナリ,マルチクラス,マルチラベルの分類問題において,様々な複雑なパフォーマンス指標を用いて,直接的に使用可能な汎用オンラインアルゴリズムを導入,分析する。 アルゴリズムの更新と予測のルールは、過去のデータを保存することなく、非常にシンプルで計算的に効率的である。
  論文  参考訳（メタデータ） (2024-06-20T21:24:47Z)
• Online Nonparametric Supervised Learning for Massive Data [0.0]
  本研究では,非パラメトリック分類器を大規模にリアルタイムに計算する高速アルゴリズムと,ストリーミングデータフレームワークを開発した。 提案手法は、リアルタイムな胎児の健康モニタリングによく使用される機械学習アルゴリズムと比較して評価・比較する。
  論文  参考訳（メタデータ） (2024-05-29T20:04:23Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  動的後悔と適応的後悔を最適化する効率的な方法を提案する。 提案アルゴリズムでは,各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。 また、さらに強力な測度、すなわち「内部的動的後悔」を研究し、ラウンド当たりの射影数を$O(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Interpolation-based Contrastive Learning for Few-Label Semi-Supervised Learning [43.51182049644767]
  半教師付き学習(SSL)は,ラベルが限定された強力なモデルを構築する上で,有効な手法であることが長年証明されてきた。 摂動サンプルを元のものと類似した予測を強制する正規化に基づく手法が注目されている。 本稿では,学習ネットワークの埋め込みを誘導し,サンプル間の線形変化を誘導する新たな対照的な損失を提案する。
  論文  参考訳（メタデータ） (2022-02-24T06:00:05Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Online Passive-Aggressive Total-Error-Rate Minimization [1.370633147306388]
  オンライン・パッシブ・アグレッシブ・ラーニング(PA)と総エラーレート最小化(TER)を二項分類に活用する新しいオンライン・ラーニング・アルゴリズムを提案する。 実験結果から,提案したPATERアルゴリズムは,実世界のデータセットにおける既存の最先端オンライン学習アルゴリズムよりも,効率と効率の面で優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2020-02-05T13:10:01Z)

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

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