Osman Yagan

Talha Cihad Gulcu, Vaggos Chatziafratis, Yingrui Zhang et al.

This paper studies the vulnerability of flow networks against adversarial attacks. In particular, consider a power system (or, any system carrying a physical flow) consisting of $N$ transmission lines with initial loads $L_1, \ldots , L_N$ and capacities $C_1, \ldots, C_N$, respectively; the capacity $C_i$ defines the maximum flow allowed on line $i$. Under an equal load redistribution model, where load of failed lines is redistributed equally among all remaining lines, we study the {\em optimization} problem of finding the best $k$ lines to attack so as to minimize the number of {\em alive} lines at the steady-state (i.e., when cascades stop). This is done to reveal the worst-case attack vulnerability of the system as well as to reveal its most vulnerable lines. We derive optimal attack strategies in several special cases of load-capacity distributions that are practically relevant. We then consider a modified optimization problem where the adversary is also constrained by the {\em total} load (in addition to the number) of the initial attack set, and prove that this problem is NP-Hard. Finally, we develop heuristic algorithms for selecting the attack set for both the original and modified problems. Through extensive simulations, we show that these heuristics outperform benchmark algorithms under a wide range of settings.

Yingrui Zhang, Osman Yagan

Integrated cyber-physical systems (CPSs), such as the smart grid, are increasingly becoming the underpinning technology for major industries. A major concern regarding such systems are the seemingly unexpected large-scale failures, which are often attributed to a small initial shock getting escalated due to intricate dependencies within and across the individual counterparts of the system. In this paper, we develop a novel interdependent system model to capture this phenomenon, also known as cascading failures. Our framework consists of two networks that have inherently different characteristics governing their intra-dependency: i) a cyber-network where a node is functional as long as it belongs to the largest connected (i.e., giant) component; and ii) a physical network where nodes are given an initial flow and a capacity, and failure of a node results with redistribution of its flow to the remaining nodes, upon which further failures might take place due to overloading (i.e., the flow of a node exceeding its capacity). Furthermore, it is assumed that these two networks are inter-dependent. For simplicity, we consider a one-to-one interdependency model where every node in the cyber-network is dependent upon and supports a single node in the physical network, and vice versa. We provide a thorough analysis of the dynamics of cascading failures in this interdependent system initiated with a random attack. The system robustness is quantified as the surviving fraction of nodes at the end of cascading failures, and is derived in terms of all network parameters involved (e.g., degree distribution, load/capacity distribution, failure size, etc.). Analytic results are supported through an extensive numerical study. Among other things, these results demonstrate the ability of our model to capture the unexpected nature of large-scale failures and provide insights on improving system robustness.

I-Cheng Lin, Osman Yagan, Carlee Joe-Wong

Federated learning has recently gained popularity as a framework for distributed clients to collaboratively train a machine learning model using local data. While traditional federated learning relies on a central server for model aggregation, recent advancements adopt a decentralized framework, enabling direct model exchange between clients and eliminating the single point of failure. However, existing decentralized frameworks often assume all clients train a shared model. Personalizing each client's model can enhance performance, especially with heterogeneous client data distributions. We propose FedSPD, an efficient personalized federated learning algorithm for the decentralized setting, and show that it learns accurate models even in low-connectivity networks. To provide theoretical guarantees on convergence, we introduce a clustering-based framework that enables consensus on models for distinct data clusters while personalizing to unique mixtures of these clusters at different clients. This flexibility, allowing selective model updates based on data distribution, substantially reduces communication costs compared to prior work on personalized federated learning in decentralized settings. Experimental results on real-world datasets show that FedSPD outperforms multiple decentralized variants of personalized federated learning algorithms, especially in scenarios with low-connectivity networks.

Mansi Sood, Eray Can Elumar, Osman Yagan

In several applications in distributed systems, an important design criterion is ensuring that the network is sparse, i.e., does not contain too many edges, while achieving reliable connectivity. Sparsity ensures communication overhead remains low, while reliable connectivity is tied to reliable communication and inference on decentralized data reservoirs and computational resources. A class of network models called random K-out graphs appear widely as a heuristic to balance connectivity and sparsity, especially in settings with limited trust, e.g., privacy-preserving aggregation of networked data in which networks are deployed. However, several questions remain regarding how to choose network parameters in response to different operational requirements, including the need to go beyond asymptotic results and the ability to model the stochastic and adversarial environments. To address this gap, we present theorems to inform the choice of network parameters that guarantee reliable connectivity in regimes where nodes can be finite or unreliable. We first derive upper and lower bounds for probability of connectivity in random K-out graphs when the number of nodes is finite. Next, we analyze the property of r-robustness, a stronger notion than connectivity that enables resilient consensus in the presence of malicious nodes. Finally, motivated by aggregation mechanisms based on pairwise masking, we model and analyze the impact of a subset of adversarial nodes, modeled as deletions, on connectivity and giant component size - metrics that are closely tied to privacy guarantees. Together, our results pave the way for end-to-end performance guarantees for a suite of algorithms for reliable inference on networks.

Eray Can Elumar, Cem Tekin, Osman Yagan

Recent advances in large language models (LLMs) have enabled automated dataset labeling with minimal human supervision. While majority voting across multiple LLMs can improve label reliability by mitigating individual model biases, it incurs high computational costs due to repeated querying. In this work, we propose a novel online framework, Cost-aware Majority Voting (CaMVo), for efficient and accurate LLM-based dataset annotation. CaMVo adaptively selects a subset of LLMs for each data instance based on contextual embeddings, balancing confidence and cost without requiring pre-training or ground-truth labels. Leveraging a LinUCB-based selection mechanism and a Bayesian estimator over confidence scores, CaMVo estimates a lower bound on labeling accuracy for each LLM and aggregates responses through weighted majority voting. Our empirical evaluation on the MMLU and IMDB Movie Review datasets demonstrates that CaMVo achieves comparable or superior accuracy to full majority voting while significantly reducing labeling costs. This establishes CaMVo as a practical and robust solution for cost-efficient annotation in dynamic labeling environments.

Anupam Nayak, Tong Yang, Osman Yagan et al.

Reverse Kullback-Leibler (KL) divergence-based regularization with respect to a fixed reference policy is widely used in modern reinforcement learning to preserve the desired traits of the reference policy and sometimes to promote exploration (using uniform reference policy, known as entropy regularization). Beyond serving as a mere anchor, the reference policy can also be interpreted as encoding prior knowledge about good actions in the environment. In the context of alignment, recent game-theoretic approaches have leveraged KL regularization with pretrained language models as reference policies, achieving notable empirical success in self-play methods. Despite these advances, the theoretical benefits of KL regularization in game-theoretic settings remain poorly understood. In this work, we develop and analyze algorithms that provably achieve improved sample efficiency under KL regularization. We study both two-player zero-sum Matrix games and Markov games: for Matrix games, we propose OMG, an algorithm based on best response sampling with optimistic bonuses, and extend this idea to Markov games through the algorithm SOMG, which also uses best response sampling and a novel concept of superoptimistic bonuses. Both algorithms achieve a logarithmic regret in $T$ that scales inversely with the KL regularization strength $β$ in addition to the standard $\widetilde{\mathcal{O}}(\sqrt{T})$ regret independent of $β$ which is attained in both regularized and unregularized settings

Eray Can Elumar, Cem Tekin, Osman Yagan

We consider bandits with anytime knapsacks (BwAK), a novel version of the BwK problem where there is an \textit{anytime} cost constraint instead of a total cost budget. This problem setting introduces additional complexities as it mandates adherence to the constraint throughout the decision-making process. We propose SUAK, an algorithm that utilizes upper confidence bounds to identify the optimal mixture of arms while maintaining a balance between exploration and exploitation. SUAK is an adaptive algorithm that strategically utilizes the available budget in each round in the decision-making process and skips a round when it is possible to violate the anytime cost constraint. In particular, SUAK slightly under-utilizes the available cost budget to reduce the need for skipping rounds. We show that SUAK attains the same problem-dependent regret upper bound of $ O(K \log T)$ established in prior work under the simpler BwK framework. Finally, we provide simulations to verify the utility of SUAK in practical settings.