論文の概要: Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification

• arxiv url: http://arxiv.org/abs/2407.11619v1
• Date: Tue, 16 Jul 2024 11:31:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-17 15:23:07.405711
• Title: Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification
• Title（参考訳）: ストラテジック・リトルストーン・ディメンション:オンラインストラテジック分類における改善された境界
• Authors: Saba Ahmadi, Kunhe Yang, Hanrui Zhang,
• Abstract要約: 戦略エージェントが観測可能な特徴を修正して肯定的な分類を受けられるような設定において、オンライン二項分類の問題について検討する。 我々は,仮説クラスと操作グラフの結合複雑性をキャプチャする新しい尺度である,ストラテジック・リトルストーン次元を導入する。 我々は、すべてのエージェントがグラフファミリ内の同じグラフで操作する実現可能な設定と、操作グラフが逆向きに選択され、家族内の1つのグラフで一貫したモデル化が行われない非依存的な設定の両方において、後悔すべき境界を導出する。
• 参考スコア（独自算出の注目度）: 22.031509365704423
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of online binary classification in settings where strategic agents can modify their observable features to receive a positive classification. We model the set of feasible manipulations by a directed graph over the feature space, and assume the learner only observes the manipulated features instead of the original ones. We introduce the Strategic Littlestone Dimension, a new combinatorial measure that captures the joint complexity of the hypothesis class and the manipulation graph. We demonstrate that it characterizes the instance-optimal mistake bounds for deterministic learning algorithms in the realizable setting. We also achieve improved regret in the agnostic setting by a refined agnostic-to-realizable reduction that accounts for the additional challenge of not observing agents' original features. Finally, we relax the assumption that the learner knows the manipulation graph, instead assuming their knowledge is captured by a family of graphs. We derive regret bounds in both the realizable setting where all agents manipulate according to the same graph within the graph family, and the agnostic setting where the manipulation graphs are chosen adversarially and not consistently modeled by a single graph in the family.
• Abstract（参考訳）: 戦略エージェントが観測可能な特徴を修正して肯定的な分類を受けられるような設定において、オンライン二項分類の問題について検討する。 特徴空間上の有向グラフによる実現可能な操作の集合をモデル化し、学習者が本来の操作ではなく、操作された特徴のみを観測すると仮定する。 我々は,仮説クラスと操作グラフの結合複雑性をキャプチャする新たな組合せ尺度である,ストラテジック・リトルストーン次元を導入する。 実測可能な設定において、決定論的学習アルゴリズムのインスタンス最適誤り境界を特徴付けることを実証する。 我々はまた、エージェントの本来の特徴を観察しないという追加の課題を考慮に入れた、洗練された無知から実現可能な削減によって、無知環境における後悔の改善も達成した。 最後に、学習者が操作グラフを知っているという仮定を緩和し、その代わりに、その知識がグラフの族によって捕捉されると仮定する。 我々は、すべてのエージェントがグラフファミリ内の同じグラフで操作する実現可能な設定と、操作グラフが逆向きに選択され、家族内の1つのグラフで一貫したモデル化が行われない非依存的な設定の両方において、後悔すべき境界を導出する。

関連論文リスト

• Learnability Gaps of Strategic Classification [68.726857356532]
  我々は,戦略的分類と標準学習の間にある学習可能性のギャップという,根本的な問題に対処することに注力する。 ほぼ厳密なサンプルの複雑さと後悔の限界を提供し、以前の結果よりも大幅に改善します。 この設定における我々のアルゴリズムは、独立して興味を持ち、マルチラベル学習のような他の問題にも適用できる。
  論文  参考訳（メタデータ） (2024-02-29T16:09:19Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  コントラスト学習は、監督の有無にかかわらず、表現を学習するための第一の方法として現れてきた。 近年の研究では、グラフ表現学習における事前学習の有用性が示されている。 本稿では,グラフの対照的な目的に対する拡張を構築する際に,候補のバンクを提供するためのグラフ変換操作を提案する。
  論文  参考訳（メタデータ） (2023-02-06T16:26:29Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。 その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
  論文  参考訳（メタデータ） (2022-12-08T23:36:00Z)
• Similarity-aware Positive Instance Sampling for Graph Contrastive Pre-training [82.68805025636165]
  トレーニングセット内の既存グラフから直接正のグラフインスタンスを選択することを提案する。 私たちの選択は、特定のドメイン固有のペアワイズ類似度測定に基づいています。 さらに,ノードを動的にマスキングしてグラフ上に均等に分配する適応ノードレベルの事前学習手法を開発した。
  論文  参考訳（メタデータ） (2022-06-23T20:12:51Z)
• Learning Losses for Strategic Classification [5.812499828391904]
  私たちは、よい決定ルールを学ぶのに必要な、サンプルの複雑さに焦点をあてて、学習理論的な視点を取ります。 我々は、関数クラスと演算グラフの複雑さの観点から、操作可能な既知のグラフのサンプル複雑性を解析する。 移動学習理論の手法を用いて、グラフを操作するための類似度尺度を定義し、その操作グラフの小さな変化に対して学習結果が堅牢であることを示す。
  論文  参考訳（メタデータ） (2022-03-25T02:26:16Z)
• Graph Self-supervised Learning with Accurate Discrepancy Learning [64.69095775258164]
  離散性に基づく自己監督型LeArning(D-SLA)と呼ばれる原図と摂動グラフの正確な相違を学習することを目的としたフレームワークを提案する。 本稿では,分子特性予測,タンパク質機能予測,リンク予測タスクなど,グラフ関連下流タスクにおける本手法の有効性を検証する。
  論文  参考訳（メタデータ） (2022-02-07T08:04:59Z)
• Unbiased Graph Embedding with Biased Graph Observations [52.82841737832561]
  基礎となるバイアスのないグラフから学習することで、バイアスのない表現を得るための、原則化された新しい方法を提案する。 この新たな視点に基づいて、そのような基礎となるグラフを明らかにするための2つの補完的手法を提案する。
  論文  参考訳（メタデータ） (2021-10-26T18:44:37Z)
• Partial Graph Reasoning for Neural Network Regularization [26.793648333908905]
  ドロップアウト(Dropout)は、よく使われる正規化手法であり、ネットワーク最適化中にニューロンのc-tivationsを無効にする。 バックボーンの特徴からスタンドアローングラフを構築することで正規化関数を学習するDropGraphを提案する。 このアドオングラフはトレーニング中にネットワークを正規化し、推論中に完全にスキップすることができる。
  論文  参考訳（メタデータ） (2021-06-03T12:57:01Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。 従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
  論文  参考訳（メタデータ） (2021-05-12T06:47:34Z)

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

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