Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification

• URL: http://arxiv.org/abs/2407.11619v1
• Date: Tue, 16 Jul 2024 11:31:20 GMT
• Title: Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification
• Authors: Saba Ahmadi, Kunhe Yang, Hanrui Zhang,
• Abstract summary: We study the problem of online binary classification in settings where strategic agents can modify their observable features to receive a positive classification. We introduce the Strategic Littlestone Dimension, a new measure that captures the joint complexity of the hypothesis class and the manipulation graph. 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.
• Score: 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.

Related papers

• Learnability Gaps of Strategic Classification [68.726857356532]
  We focus on addressing a fundamental question: the learnability gaps between strategic classification and standard learning. We provide nearly tight sample complexity and regret bounds, offering significant improvements over prior results. Notably, our algorithm in this setting is of independent interest and can be applied to other problems such as multi-label learning.
  arXiv  Detail & Related papers  (2024-02-29T16:09:19Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Similarity-aware Positive Instance Sampling for Graph Contrastive Pre-training [82.68805025636165]
  We propose to select positive graph instances directly from existing graphs in the training set. Our selection is based on certain domain-specific pair-wise similarity measurements. Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
  arXiv  Detail & Related papers  (2022-06-23T20:12:51Z)
• Learning Losses for Strategic Classification [5.812499828391904]
  We take a learning theoretic perspective, focusing on the sample complexity needed to learn a good decision rule. We analyse the sample complexity for a known graph of possible manipulations in terms of the complexity of the function class and the manipulation graph. Using techniques from transfer learning theory, we define a similarity measure for manipulation graphs and show that learning outcomes are robust with respect to small changes in the manipulation graph.
  arXiv  Detail & Related papers  (2022-03-25T02:26:16Z)
• Graph Self-supervised Learning with Accurate Discrepancy Learning [64.69095775258164]
  We propose a framework that aims to learn the exact discrepancy between the original and the perturbed graphs, coined as Discrepancy-based Self-supervised LeArning (D-SLA) We validate our method on various graph-related downstream tasks, including molecular property prediction, protein function prediction, and link prediction tasks, on which our model largely outperforms relevant baselines.
  arXiv  Detail & Related papers  (2022-02-07T08:04:59Z)
• Unbiased Graph Embedding with Biased Graph Observations [52.82841737832561]
  We propose a principled new way for obtaining unbiased representations by learning from an underlying bias-free graph. Based on this new perspective, we propose two complementary methods for uncovering such an underlying graph.
  arXiv  Detail & Related papers  (2021-10-26T18:44:37Z)
• Partial Graph Reasoning for Neural Network Regularization [26.793648333908905]
  Dropout,as a commonly used regularization technique, disables neuron ac-tivations during network optimization. We present DropGraph that learns regularization function by constructing a stand-alone graph from the backbone features. This add-on graph regularizes the network during training and can be completely skipped during inference.
  arXiv  Detail & Related papers  (2021-06-03T12:57:01Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  We consider the problem of inferring the graph structure from a given set of graph signals. Traditional graph learning models do not take this distributional uncertainty into account.
  arXiv  Detail & Related papers  (2021-05-12T06:47:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.