Title: Multi-Agent Distributed Optimization With Feasible Set Privacy Show Chinese title

Title: 具有可行集隐私的多智能体分布式优化

Abstract: We consider the problem of decentralized constrained optimization with multiple agents $E_1,\ldots,E_N$ who jointly wish to learn the optimal solution set while keeping their feasible sets $\mathcal{P}_1,\ldots,\mathcal{P}_N$ private from each other. We assume that the objective function $f$ is known to all agents and each feasible set is a collection of points from a universal alphabet $\mathcal{P}_{alph}$. A designated agent (leader) starts the communication with the remaining (non-leader) agents, and is the first to retrieve the solution set. The leader searches for the solution by sending queries to and receiving answers from the non-leaders, such that the information on the individual feasible sets revealed to the leader should be no more than nominal, i.e., what is revealed from learning the solution set alone. We develop achievable schemes for obtaining the solution set at nominal information leakage, and characterize their communication costs under two communication setups between agents. In this work, we focus on two kinds of network setups: i) ring, where each agent communicates with two adjacent agents, and ii) star, where only the leader communicates with the remaining agents. We show that, if the leader first learns the joint feasible set through an existing private set intersection (PSI) protocol and then deduces the solution set, the information leaked to the leader is greater than nominal. Moreover, we draw connection of our schemes to threshold PSI (ThPSI), which is a PSI-variant where the intersection is revealed only when its cardinality is larger than a threshold value. Finally, for various realizations of $f$ mapped uniformly at random to a fixed range of values, our schemes are more communication-efficient with a high probability compared to retrieving the entire feasible set through PSI. Show Chinese abstract

Abstract: 我们考虑多个代理之间的去中心化约束优化问题，$E_1,\ldots,E_N$他们希望共同学习最优解集，同时保持各自的可行集$\mathcal{P}_1,\ldots,\mathcal{P}_N$对彼此保密。 我们假设目标函数$f$为所有代理所知，每个可行集是从通用字母表$\mathcal{P}_{alph}$中收集的点的集合。 指定的一个代理（领导者）首先与其余（非领导者）代理进行通信，并是第一个检索解集的代理。 领导者通过向非领导者发送查询并接收回答来寻找解集，使得对领导者揭示的个体可行集的信息不超过名义上的程度，即仅从学习解集本身中揭示的信息。 我们开发了在名义信息泄露下获得解集的可行方案，并在代理之间的两种通信设置下分析了它们的通信成本。 在这项工作中，我们关注两种网络设置：i) 环形，其中每个代理与两个相邻代理通信；ii) 星型，其中只有领导者与其余代理通信。 我们表明，如果领导者首先通过现有的私有集合交集（PSI）协议学习联合可行集，然后推导出解集，则泄露给领导者的相关信息将超过名义水平。 此外，我们将我们的方案与阈值PSI（ThPSI）联系起来，这是一种PSI变体，只有当交集的基数大于某个阈值时才揭示交集。 最后，对于各种将$f$均匀随机映射到固定值范围的实现，我们的方案在高概率下比通过PSI检索整个可行集更具有通信效率。