Dezhong YaoWanning PanYuexin ShiMichael J. O'Neill...
104333.1-104333.19页
查看更多>>摘要：One underlying assumption of recent Federated Learning (FL) paradigms is that all local models share an identical network architecture. However, this assumption is inefficient for heterogeneous systems where devices possess varying computation and communication capabilities. The presence of such heterogeneity among devices negatively impacts the scalability of FL and slows down the training process due to the existence of stragglers. To this end, this paper proposes a novel federated compression framework for heterogeneous models, named FedHM, distributing the heterogeneous low-rank models to clients and then aggregating them into a full-rank global model. Furthermore, FedHM significantly reduces communication costs by utilizing low-rank models. Compared with state-of-the-art heterogeneous FL methods under various FL settings, FedHM is superior in the performance and robustness of models with different sizes. Additionally, the convergence guarantee of FL for heterogeneous devices is first theoretically analyzed.
Francesco BacchiocchiMatteo CastiglioniNicola GattiAlberto Marchesi...
104334.1-104334.24页
查看更多>>摘要：We study principal-agent problems in which a principal commits to an outcome-dependent payment scheme-called contract-in order to induce an agent to take a costly, unobservable action leading to favorable outcomes. We consider a generalization of the classical (single-round) version of the problem in which the principal interacts with the agent by committing to contracts over multiple rounds. The principal has no information about the agent, and they have to learn an optimal contract by only observing the outcome realized at each round. We focus on settings in which the size of the agent's action space is small. We design an algorithm that learns an approximately-optimal contract with high probability in a number of rounds polynomial in the size of the outcome space, when the number of actions is constant. Our algorithm solves an open problem by Zhu et al. Moreover, it can also be employed to provide a Θ(T~(4/5)) regret bound in the related online learning setting in which the principal aims at maximizing their cumulative utility over rounds, considerably improving previously-known regret bounds.
查看更多>>摘要：We study the problem of allocating divisible resources among n agents, hopefully in a fair and efficient manner. With the presence of strategic agents, additional incentive guarantees are also necessary, and the problem of designing fair and efficient mechanisms becomes much less tractable. While there are flourishing positive results against strategic agents for homogeneous divisible items, very few of them are known to hold in cake cutting. We show that the Maximum Nash Welfare (MNW) mechanism, which provides desirable fairness and efficiency guarantees and achieves an incentive ratio of 2 for homogeneous divisible items, also has an incentive ratio of 2 in cake cutting. Remarkably, this result holds even without the free disposal assumption, which is hard to get rid of in the design of truthful cake cutting mechanisms. Moreover, we show that, for cake cutting, the Partial Allocation (PA) mechanism proposed by Cole et al., which is truthful and 1/e-MNW for homogeneous divisible items, has an incentive ratio between [e~(1/e), e] and when randomization is allowed, can be turned to be truthful in expectation. Given two alternatives for a trade-off between incentive ratio and Nash welfare provided by the MNW and PA mechanisms, we establish an interpolation between them for both cake cutting and homogeneous divisible items. Finally, we study the optimal incentive ratio achievable by envy-free cake cutting mechanisms. We first give an envy-free mechanism for two agents with an incentive ratio of 4/3. Then, we show that any envy-free cake cutting mechanism with the connected pieces constraint has an incentive ratio of Θ(n).
Piero Andrea BonattiFrancesco MaglioccaIliana Mineva PetrovaLuigi Sauro...
104345.1-104345.16页
查看更多>>摘要：A deductive module of a knowledge base KB is a subset of KB that preserves a specified class of consequences. Module extraction is applied in ontology design, debugging, and reasoning. The locality-based module extractors of the OWL API are less effective when the knowledge base contains facts such as ABox assertions. The competing module extractor PrisM computes smaller modules at the cost of higher computation time. In this paper, we introduce and study a novel module extraction technique, called conditional module extraction, that can be applied to satisfiable SRIQ(D) knowledge bases. Experimental analysis shows that conditional module extraction constitutes an appealing alternative to PrisM and to the locality-based extractors of the OWL API, when the ABox is nonempty.
NETL
NSTL
Elsevier