Skip to main navigation Skip to search Skip to main content

Differentially Private Matroid Bandits for Online Network Topology Optimization

  • Youming Tao
  • , Shuzhen Chen
  • , Kai Li
  • , Dongxiao Yu
  • , Xiuzhen Cheng
  • , Falko Dressler

Research output: Chapter in Book/Published conference output › Conference publication

Abstract

Efficient and adaptive network topology design is fundamental in communication systems. A key problem is to construct low-cost structures like minimum spanning trees (MSTs) from uncertain and stochastic link measurements. However, topology and link data often reveal sensitive attributes, including location and traffic patterns, posing privacy risks. We propose Differentially Private Matroid Bandits, an online learning framework for consecutive MST construction with formal privacy guarantees. Modeling the problem as stochastic optimization over a matroid, we develop algorithms that balance exploration and exploitation while ensuring differential privacy in both central and local models. We establish regret upper bounds capturing the trade-offs among privacy, accuracy, and structural complexity. Experiments on real network data show our approach achieves near-optimal performance with strong privacy protection.
Original languageEnglish
Title of host publicationDifferentially Private Matroid Bandits for Online Network Topology Optimization
PublisherACM
Pages19-24
Number of pages6
ISBN (Electronic)9798400719745
DOIs
Publication statusPublished - 13 Nov 2025

Fingerprint

Dive into the research topics of 'Differentially Private Matroid Bandits for Online Network Topology Optimization'. Together they form a unique fingerprint.

Cite this