論文の概要: Adversarial Online Classification with a Preview

• arxiv url: http://arxiv.org/abs/2608.29503v1
• Date: Sun, 30 Aug 2026 01:38:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-01 18:31:30.984504
• Title: Adversarial Online Classification with a Preview
• Title（参考訳）: Adversarial Online Classification with a Preview (英語)
• Abstract要約: 最悪のオンライン分類は、リトルストーン次元のようなシーケンシャルな複雑さによって管理されている。 オンラインの順序をランダムにすることなく、古典的な統計次元によって、ランダムなプレビューが最悪ケースのシーケンシャルな複雑さを置き換えることができることを示す。
• 参考スコア（独自算出の注目度）: 17.495168716195476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Worst-case online classification is governed by sequential complexity, such as Littlestone dimension, and can be impossible even for statistically simple classes, such as thresholds of VC dimension one. We study a preview model in which an oblivious adversary fixes an entire labeled sequence of length $T$, a uniformly random subset of size $pT$ is revealed before prediction begins, and the remaining $(1-p)T$ examples are then presented in their original adversarial order. Against the best full-sequence hypothesis evaluated on the unrevealed examples, we characterize the dependence on the preview rate $p$: for binary classes of VC dimension $d$, the optimal excess loss is $Θ(d/p+\sqrt{dT})$, up to the trivial cap at $T$; for multiclass classes we obtain the corresponding $\widetilde O(d_{\rm DS}/p+\sqrt{d_{\rm Nat}T})$ bound with no dependence on the number of labels. Thus a random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order. To achieve the sharp binary bound, our ChainedPrediction algorithm uses an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.
• Abstract（参考訳）: 最悪のオンライン分類はリトルストーン次元のようなシーケンシャルな複雑さによって管理され、VC次元1のしきい値のような統計的に単純なクラスでも不可能である。 予測開始前に, ラベル付き長さ$T$, サイズ$pT$の一様ランダムなサブセットが明らかにされ, 残りの$(1-p)T$のサンプルが元の逆順に表示されるようなプレビューモデルについて検討する。 未公表の例で評価された最良の完全系列仮説に対して、プレビューレート$p$:VC次元のバイナリクラス$d$に対して、最適余剰損失は$(d/p+\sqrt{dT})$, 自明な上限$T$, マルチクラスクラスでは、対応する$\widetilde O(d_{\rm DS}/p+\sqrt{d_{\rm Nat}T})$をラベル数に依存しない形で取得する。 したがって、ランダムプレビューは、オンラインオーダーをランダムにすることなく、古典的な統計次元によって最悪のケースのシーケンシャルな複雑さを置き換えることができる。 このシャープなバイナリ境界を達成するために、我々のChainedPredictionアルゴリズムは、解析引数としてだけではなく、多スケール集約アルゴリズムとして実装された連鎖のオンラインアナログを用いている。

関連論文リスト

• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  モノトン対向は、i.i.d.ラベル付きサンプルを観察し、その選択の有限個の例を付加する。 すべてのサンプルは正しくラベル付けされているが、挿入はクリーンサンプルに依存するため、組み合わせたサンプルは交換できない。 このモデルを導入したLarsen、Pabbaraju、およびShettyは、VC次元$d$のクラスに対して、経験的リスク最小化が予測誤差$O((d/n)log(n/d))$に達することを示した。
  論文  参考訳（メタデータ） (2026-08-06T17:45:32Z)
• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) は、オーバーコンプリートな等幅のタイトフレーム、座標サブサンプリング、プライバシ対応量子化を組み合わせたフレームワークである。 SSTQは平均2乗誤差スケーリングを実現し、クライアントあたり$lceil log N il + b$ bitsを使用する。 また、コードブックに依存したMSEスケーリングを$O(4b)$から$O(2b)$に削減する、プライバシを意識したコードブックの目的も導出します。
  論文  参考訳（メタデータ） (2026-08-05T17:51:25Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。 この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。 この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
  論文  参考訳（メタデータ） (2026-05-10T14:28:05Z)
• Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
  最短経路問題(SSP)問題において,$$-optimal Policy($-optimal Policy)を学習する際のサンプル複雑性について検討した。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。 驚くべきことに、$c_min = 0$のSSP問題はいつでも学習できない。
  論文  参考訳（メタデータ） (2026-04-17T14:47:52Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• Agnostic Smoothed Online Learning without Knowledge of the Base Measure [5.167069404528051]
  本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。 R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
  論文  参考訳（メタデータ） (2024-10-07T15:25:21Z)
• Self-Directed Linear Classification [50.659479930171585]
  オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。 そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
  論文  参考訳（メタデータ） (2023-08-06T15:38:44Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sample Complexity Bounds for Robustly Learning Decision Lists against Evasion Attacks [25.832511407411637]
  敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。 我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。 すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
  論文  参考訳（メタデータ） (2022-05-12T14:40:18Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  プライバシー制約下でのオンライン分類の問題点を考察する。 この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。 学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
  論文  参考訳（メタデータ） (2021-06-25T09:08:33Z)
• Robust learning under clean-label attack [26.323812778809913]
  クリーンラベルデータ汚染攻撃におけるロバスト学習の問題点について検討する。 学習目標は、最適なPAC学習よりも難しい攻撃可能な速度を最小限にすることです。
  論文  参考訳（メタデータ） (2021-03-01T00:21:15Z)

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

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