Search Publications
Publications
2020 |
Fei Mi Xiaoyu Lin, Boi Faltings PermLink ADER: Adaptively Distilled Exemplar Replay Towards Continual Learning for Session-based Recommendation Conference Forthcoming The ACM Conference on Recommender Systems (RecSys), 2020, Forthcoming, (RecSys 2020). @conference{Miii2020, title = {ADER: Adaptively Distilled Exemplar Replay Towards Continual Learning for Session-based Recommendation}, author = {Fei Mi, Xiaoyu Lin, Boi Faltings}, year = {2020}, date = {2020-09-07}, booktitle = {The ACM Conference on Recommender Systems (RecSys), 2020}, note = {RecSys 2020}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } |
Mi, Fei; Faltings, Boi PermLink Memory Augmented Neural Model for Incremental Session-based Recommendation Conference Forthcoming Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), Forthcoming. @conference{Mi2020, title = {Memory Augmented Neural Model for Incremental Session-based Recommendation}, author = {Fei Mi and Boi Faltings}, url = {https://arxiv.org/abs/2005.01573}, year = {2020}, date = {2020-08-08}, booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } |
Goel, Naman; Filos-Ratsikas, Aris; Faltings, Boi PermLink Peer-Prediction in the Presence of Outcome Dependent Lying Incentives Conference Forthcoming Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), Forthcoming. @conference{Goel2020b, title = {Peer-Prediction in the Presence of Outcome Dependent Lying Incentives}, author = {Naman Goel and Aris Filos-Ratsikas and Boi Faltings}, url = {https://www.ijcai.org/Proceedings/2020/0018.pdf}, year = {2020}, date = {2020-07-11}, booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } |
Goel*, Naman; van Schreven*, Cyril; Filos-Ratsikas, Aris; Faltings, Boi PermLink Infochain: A Decentralized, Trustless and Transparent Oracle on Blockchain Conference Forthcoming Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), Forthcoming. @conference{Goel2020c, title = {Infochain: A Decentralized, Trustless and Transparent Oracle on Blockchain}, author = {Naman Goel* and Cyril van Schreven* and Aris Filos-Ratsikas and Boi Faltings}, url = {https://www.ijcai.org/Proceedings/2020/0635.pdf}, year = {2020}, date = {2020-07-11}, booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } |
Goel, Naman; Rutagarama, Maxime; Faltings, Boi PermLink Tackling Peer to Peer Discrimination in the Sharing Economy Conference Proceedings of the 12th ACM Web Science Conference (WebSci 2020), ACM, 2020. @conference{Goel2020, title = {Tackling Peer to Peer Discrimination in the Sharing Economy}, author = {Naman Goel and Maxime Rutagarama and Boi Faltings}, url = {https://lia.epfl.ch/~goel/upload/doc/papers/2020/goel_websci20.pdf}, year = {2020}, date = {2020-07-07}, booktitle = {Proceedings of the 12th ACM Web Science Conference (WebSci 2020)}, publisher = {ACM}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Chatzopoulos, Dimitris; Gujar, Sujit; Faltings, Boi; Hui, Pan PermLink Mneme: A Mobile Distributed Ledger Conference Forthcoming IEEE Infocom, IEEE, Forthcoming. @conference{Chatzopoulos2020a, title = {Mneme: A Mobile Distributed Ledger}, author = {Dimitris Chatzopoulos and Sujit Gujar and Boi Faltings and Pan Hui}, url = {https://lia.epfl.ch/wp-content/uploads/2020/05/main.pdf}, year = {2020}, date = {2020-07-06}, booktitle = {IEEE Infocom}, publisher = {IEEE}, abstract = {Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices and operates via two consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze the security of Mneme and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices and operates via two consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze the security of Mneme and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme. |
Mi, Fei; Kong, Lingjing; Lin, Tao; Yu, Kaicheng; Faltings, Boi PermLink Generalized Class Incremental Learning Workshop Forthcoming CVPR2020 Continual Learning Workshop, Forthcoming. @workshop{Mii2020, title = {Generalized Class Incremental Learning}, author = {Fei Mi and Lingjing Kong and Tao Lin and Kaicheng Yu and Boi Faltings}, year = {2020}, date = {2020-06-14}, booktitle = {CVPR2020 Continual Learning Workshop}, keywords = {}, pubstate = {forthcoming}, tppubtype = {workshop} } |
Triastcyn, Aleksei; Faltings, Boi PermLink Federated Generative Privacy Journal Article Forthcoming IEEE Intelligent Systems, Forthcoming, ISSN: 1541-1672. @article{triastcyn2020fedgp, title = {Federated Generative Privacy}, author = {Aleksei Triastcyn and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2020/05/fedgp_ieee_is_2020.pdf}, doi = {10.1109/MIS.2020.2993966}, issn = {1541-1672}, year = {2020}, date = {2020-05-12}, journal = {IEEE Intelligent Systems}, abstract = {We propose FedGP, a framework for privacy-preserving data release in the federated learning setting. We use generative adversarial networks, generator components of which are trained by FedAvg algorithm, to draw private artificial data samples and empirically assess the risk of information disclosure. Our experiments show that FedGP is able to generate labelled data of high quality to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks.}, keywords = {}, pubstate = {forthcoming}, tppubtype = {article} } We propose FedGP, a framework for privacy-preserving data release in the federated learning setting. We use generative adversarial networks, generator components of which are trained by FedAvg algorithm, to draw private artificial data samples and empirically assess the risk of information disclosure. Our experiments show that FedGP is able to generate labelled data of high quality to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks. |
Antognini, Diego; Faltings, Boi PermLink HotelRec: a Novel Very Large-Scale Hotel Recommendation Dataset Conference Forthcoming LREC 2020, Twelveth International Conference on Language Resources and Evaluation, Forthcoming. @conference{tobedefine, title = {HotelRec: a Novel Very Large-Scale Hotel Recommendation Dataset}, author = {Diego Antognini and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2020/02/LREC_2020_HotelRec.pdf}, year = {2020}, date = {2020-02-17}, booktitle = {LREC 2020, Twelveth International Conference on Language Resources and Evaluation}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } |
Antognini, Diego; Faltings, Boi PermLink GameWikiSum: a Novel Large Multi-Document Summarization Dataset Conference Forthcoming LREC 2020, Twelveth International Conference on Language Resources and Evaluation, Forthcoming. @conference{tobedefineb, title = {GameWikiSum: a Novel Large Multi-Document Summarization Dataset}, author = {Diego Antognini and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2020/02/LREC_2020_GameWikiSum.pdf}, year = {2020}, date = {2020-02-17}, booktitle = {LREC 2020, Twelveth International Conference on Language Resources and Evaluation}, keywords = {}, pubstate = {forthcoming}, tppubtype = {conference} } |
Milojkovic, Nikola; Antognini, Diego; Bergamin, Giancarlo; Faltings, Boi; Musat, Claudiu PermLink Multi-Gradient Descent for Multi-Objective Recommender Systems Proceeding Proceedings of the The Thirty-Fourth AAAI Conference on Artificial Intelligence 2020 - Workshop on Interactive and Conversational Recommendation Systems (WICRS), 2020. @proceedings{mikolovic2019, title = {Multi-Gradient Descent for Multi-Objective Recommender Systems}, author = {Nikola Milojkovic and Diego Antognini and Giancarlo Bergamin and Boi Faltings and Claudiu Musat}, url = {https://lia.epfl.ch/wp-content/uploads/2019/12/multi_obj_2019.pdf https://arxiv.org/abs/2001.00846}, year = {2020}, date = {2020-02-09}, publisher = {Proceedings of the The Thirty-Fourth AAAI Conference on Artificial Intelligence 2020 - Workshop on Interactive and Conversational Recommendation Systems (WICRS)}, abstract = {Recommender systems need to mirror the complexity of the environment they are applied in. The more we know about what might benefit the user, the more objectives the recommender system has. In addition there may be multiple stakeholders - sellers, buyers, shareholders - in addition to legal and ethical constraints. Simultaneously optimizing for a multitude of objectives, correlated and not correlated, having the same scale or not, has proven difficult so far. We introduce a stochastic multi-gradient descent approach to recommender systems (MGDRec) to solve this problem. We show that this exceeds state-of-the-art methods in traditional objective mixtures, like revenue and recall. Not only that, but through gradient normalization we can combine fundamentally different objectives, having diverse scales, into a single coherent framework. We show that uncorrelated objectives, like the proportion of quality products, can be improved alongside accuracy. Through the use of stochasticity, we avoid the pitfalls of calculating full gradients and provide a clear setting for its applicability.}, keywords = {}, pubstate = {published}, tppubtype = {proceedings} } Recommender systems need to mirror the complexity of the environment they are applied in. The more we know about what might benefit the user, the more objectives the recommender system has. In addition there may be multiple stakeholders - sellers, buyers, shareholders - in addition to legal and ethical constraints. Simultaneously optimizing for a multitude of objectives, correlated and not correlated, having the same scale or not, has proven difficult so far. We introduce a stochastic multi-gradient descent approach to recommender systems (MGDRec) to solve this problem. We show that this exceeds state-of-the-art methods in traditional objective mixtures, like revenue and recall. Not only that, but through gradient normalization we can combine fundamentally different objectives, having diverse scales, into a single coherent framework. We show that uncorrelated objectives, like the proportion of quality products, can be improved alongside accuracy. Through the use of stochasticity, we avoid the pitfalls of calculating full gradients and provide a clear setting for its applicability. |
Triastcyn, Aleksei; Faltings, Boi PermLink Bayesian Differential Privacy for Machine Learning Workshop AAAI Workshop on Privacy-Preserving Artificial Intelligence, 2020. @workshop{triastcyn2020bayesiandp, title = {Bayesian Differential Privacy for Machine Learning}, author = {Aleksei Triastcyn and Boi Faltings}, url = {https://www2.isye.gatech.edu/~fferdinando3/cfp/PPAI20/papers/paper_19.pdf}, year = {2020}, date = {2020-02-07}, booktitle = {AAAI Workshop on Privacy-Preserving Artificial Intelligence}, abstract = {We propose Bayesian differential privacy, a relaxation of differential privacy that provides sharper privacy guarantees for similarly distributed data, especially in difficult scenarios, such as deep learning. We derive a general privacy accounting method for iterative learning algorithms under Bayesian differential privacy and show that it is a generalisation of the well-known moments accountant. Our experiments show significant improvements in privacy guarantees for typical cases in deep learning datasets, such as MNIST and CIFAR-10, in some cases bringing the privacy budget ε from 8 down to 0.5.}, keywords = {}, pubstate = {published}, tppubtype = {workshop} } We propose Bayesian differential privacy, a relaxation of differential privacy that provides sharper privacy guarantees for similarly distributed data, especially in difficult scenarios, such as deep learning. We derive a general privacy accounting method for iterative learning algorithms under Bayesian differential privacy and show that it is a generalisation of the well-known moments accountant. Our experiments show significant improvements in privacy guarantees for typical cases in deep learning datasets, such as MNIST and CIFAR-10, in some cases bringing the privacy budget ε from 8 down to 0.5. |
2019 |
Aris Filos-Ratsikas, Yiannis Giannakopoulos ; Lazos, Philip PermLink The Pareto Frontier of Inefficiency in Mechanism Design Conference The 15th Conference on Web and Internet Economics (WINE 2019)., Springer, 2019. @conference{Filos-Ratsikas2019b, title = {The Pareto Frontier of Inefficiency in Mechanism Design}, author = {Aris Filos-Ratsikas, Yiannis Giannakopoulos and Philip Lazos}, url = {https://arxiv.org/abs/1809.03454}, year = {2019}, date = {2019-12-10}, booktitle = {The 15th Conference on Web and Internet Economics (WINE 2019).}, pages = {186-199}, publisher = {Springer}, abstract = {We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms SPα that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter α≥1 across the frontier, between the First-Price (SP1) and Second-Price (SP∞) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether non-truthful mechanisms can provide better makespan guarantees in the equilibrium, compared to truthful ones. We answer this question in the negative, by proving that the Price of Anarchy of all scheduling mechanisms is at least n, where n is the number of machines.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms SPα that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter α≥1 across the frontier, between the First-Price (SP1) and Second-Price (SP∞) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether non-truthful mechanisms can provide better makespan guarantees in the equilibrium, compared to truthful ones. We answer this question in the negative, by proving that the Price of Anarchy of all scheduling mechanisms is at least n, where n is the number of machines. |
Triastcyn, Aleksei; Faltings, Boi PermLink Federated Learning with Bayesian Differential Privacy Inproceedings 2019 IEEE International Conference on Big Data (Big Data), pp. 2587-2596, IEEE, 2019, ISBN: 978-1-7281-0858-2. @inproceedings{triastcyn2019federatedbdp, title = {Federated Learning with Bayesian Differential Privacy}, author = {Aleksei Triastcyn and Boi Faltings}, doi = {10.1109/BigData47090.2019.9005465}, isbn = {978-1-7281-0858-2}, year = {2019}, date = {2019-12-09}, booktitle = {2019 IEEE International Conference on Big Data (Big Data)}, pages = {2587-2596}, publisher = {IEEE}, abstract = {We consider the problem of reinforcing federated learning with formal privacy guarantees. We propose to employ Bayesian differential privacy, a relaxation of differential privacy for similarly distributed data, to provide sharper privacy loss bounds. We adapt the Bayesian privacy accounting method to the federated setting and suggest multiple improvements for more efficient privacy budgeting at different levels. Our experiments show significant advantage over the state-of-the-art differential privacy bounds for federated learning on image classification tasks, including a medical application, bringing the privacy budget below ε = 1 at the client level, and below ε = 0.1 at the instance level. Lower amounts of noise also benefit the model accuracy and reduce the number of communication rounds.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We consider the problem of reinforcing federated learning with formal privacy guarantees. We propose to employ Bayesian differential privacy, a relaxation of differential privacy for similarly distributed data, to provide sharper privacy loss bounds. We adapt the Bayesian privacy accounting method to the federated setting and suggest multiple improvements for more efficient privacy budgeting at different levels. Our experiments show significant advantage over the state-of-the-art differential privacy bounds for federated learning on image classification tasks, including a medical application, bringing the privacy budget below ε = 1 at the client level, and below ε = 0.1 at the instance level. Lower amounts of noise also benefit the model accuracy and reduce the number of communication rounds. |
Antognini, Diego; Faltings, Boi PermLink Learning to Create Sentence Semantic Relation Graphs for Multi-Document Summarization Proceeding Proceedings of the Empirical Methods in Natural Language Processing 2019 - Workshop on New Frontiers in Summarization, 2019. @proceedings{antognini-faltings-2019-learning, title = {Learning to Create Sentence Semantic Relation Graphs for Multi-Document Summarization}, author = {Diego Antognini and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2019/11/D19-5404.pdf https://www.aclweb.org/anthology/D19-5404}, doi = {10.18653/v1/D19-5404}, year = {2019}, date = {2019-11-01}, booktitle = {Proceedings of the 2nd Workshop on New Frontiers in Summarization }, pages = {32--41}, address = {Proceedings of the Empirical Methods in Natural Language Processing 2019 - Workshop on New Frontiers in Summarization}, abstract = {Linking facts across documents is a challenging task, as the language used to express the same information in a sentence can vary significantly, which complicates the task of multi-document summarization. Consequently, existing approaches heavily rely on hand-crafted features, which are domain-dependent and hard to craft, or additional annotated data, which is costly to gather. To overcome these limitations, we present a novel method, which makes use of two types of sentence embeddings: universal embeddings, which are trained on a large unrelated corpus, and domain-specific embeddings, which are learned during training. To this end, we develop SemSentSum, a fully data-driven model able to leverage both types of sentence embeddings by building a sentence semantic relation graph. SemSentSum achieves competitive results on two types of summary, consisting of 665 bytes and 100 words. Unlike other state-of-the-art models, neither hand-crafted features nor additional annotated data are necessary, and the method is easily adaptable for other tasks. To our knowledge, we are the first to use multiple sentence embeddings for the task of multi-document summarization.}, keywords = {}, pubstate = {published}, tppubtype = {proceedings} } Linking facts across documents is a challenging task, as the language used to express the same information in a sentence can vary significantly, which complicates the task of multi-document summarization. Consequently, existing approaches heavily rely on hand-crafted features, which are domain-dependent and hard to craft, or additional annotated data, which is costly to gather. To overcome these limitations, we present a novel method, which makes use of two types of sentence embeddings: universal embeddings, which are trained on a large unrelated corpus, and domain-specific embeddings, which are learned during training. To this end, we develop SemSentSum, a fully data-driven model able to leverage both types of sentence embeddings by building a sentence semantic relation graph. SemSentSum achieves competitive results on two types of summary, consisting of 665 bytes and 100 words. Unlike other state-of-the-art models, neither hand-crafted features nor additional annotated data are necessary, and the method is easily adaptable for other tasks. To our knowledge, we are the first to use multiple sentence embeddings for the task of multi-document summarization. |
Aris Filos-Ratsikas, Evi Micha ; Voudouris, Alexandros A PermLink The Distortion of Distributed Voting Conference The 12th International Symposium on Algorithmic Game Theory, Springer, 2019. @conference{Filos-Ratsikas2019c, title = {The Distortion of Distributed Voting}, author = {Aris Filos-Ratsikas, Evi Micha and Alexandros A. Voudouris}, url = {https://arxiv.org/pdf/1905.01882.pdf}, year = {2019}, date = {2019-09-30}, booktitle = {The 12th International Symposium on Algorithmic Game Theory}, publisher = {Springer}, abstract = {Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data. |
Panayiotis Danassis, Aris Filos-Ratsikas ; Faltings, Boi PermLink Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior Conference The 28th International Joint Conference on Artificial Intelligence (IJCAI '19), 2019. @conference{Danassis2019, title = {Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior}, author = {Panayiotis Danassis, Aris Filos-Ratsikas and Boi Faltings}, url = {https://arxiv.org/pdf/1902.09359.pdf}, year = {2019}, date = {2019-08-15}, booktitle = {The 28th International Joint Conference on Artificial Intelligence (IJCAI '19)}, pages = {215-222}, abstract = {We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on the convergence speed that is polynomial in the desired number of resources and competing agents per resource; crucially, in the realistic case where the aforementioned quantities are bounded independently of the total number of agents/resources, the convergence time remains constant as the total problem size increases. We have evaluated ALMA under three test cases: (i) an anti-coordination scenario where agents with similar preferences compete over the same set of actions, (ii) a resource allocation scenario in an urban environment, under a constant-time constraint, and finally, (iii) an on-line matching scenario using real passenger-taxi data. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm. The latter allows our algorithm to scale to realistic scenarios with hundreds of thousands of agents, e.g., vehicle coordination in urban environments.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on the convergence speed that is polynomial in the desired number of resources and competing agents per resource; crucially, in the realistic case where the aforementioned quantities are bounded independently of the total number of agents/resources, the convergence time remains constant as the total problem size increases. We have evaluated ALMA under three test cases: (i) an anti-coordination scenario where agents with similar preferences compete over the same set of actions, (ii) a resource allocation scenario in an urban environment, under a constant-time constraint, and finally, (iii) an on-line matching scenario using real passenger-taxi data. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm. The latter allows our algorithm to scale to realistic scenarios with hundreds of thousands of agents, e.g., vehicle coordination in urban environments. |
Triastcyn, Aleksei; Faltings, Boi PermLink Federated Generative Privacy Workshop The 1st International Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML’19), 2019. @workshop{triastcyn2019fedgp, title = {Federated Generative Privacy}, author = {Aleksei Triastcyn and Boi Faltings}, url = {https://lia.epfl.ch/wp-content/uploads/2019/07/fml_2019-1.pdf}, year = {2019}, date = {2019-08-12}, booktitle = {The 1st International Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML’19)}, abstract = {In this paper, we propose FedGP, a framework for privacy-preserving data release in the federated learning setting. We use generative adversarial networks, generator components of which are trained by FedAvg algorithm, to draw privacy-preserving artificial data samples and empirically assess the risk of information disclosure. Our experiments show that FedGP is able to generate labelled data of high quality to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks.}, keywords = {}, pubstate = {published}, tppubtype = {workshop} } In this paper, we propose FedGP, a framework for privacy-preserving data release in the federated learning setting. We use generative adversarial networks, generator components of which are trained by FedAvg algorithm, to draw privacy-preserving artificial data samples and empirically assess the risk of information disclosure. Our experiments show that FedGP is able to generate labelled data of high quality to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks. |
Adam Richardson, Aris Filos-Ratsikas ; Faltings, Boi PermLink Eliciting High-Quality Data via Influence for Linear Regression Workshop The 1st International Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML 2019), 2019. @workshop{Richardson2019, title = {Eliciting High-Quality Data via Influence for Linear Regression}, author = {Adam Richardson, Aris Filos-Ratsikas and Boi Faltings}, url = {https://arxiv.org/pdf/1908.11598.pdf}, year = {2019}, date = {2019-08-12}, booktitle = {The 1st International Workshop on Federated Machine Learning for User Privacy and Data Confidentiality (FML 2019)}, abstract = {We consider a crowdsourcing data acquisition scenario, such as federated learning, where a Center collects data points from a set of rational Agents, with the aim of training a model. For linear regression models, we show how a payment structure can be designed to incentivize the agents to provide high-quality data as early as possible, based on a characterization of the influence that data points have on the loss function of the model. Our contributions can be summarized as follows: (a) we prove theoretically that this scheme ensures truthful data reporting as a game-theoretic equilibrium and further demonstrate its robustness against mixtures of truthful and heuristic data reports, (b) we design a procedure according to which the influence computation can be efficiently approximated and processed sequentially in batches over time, (c) we develop a theory that allows correcting the difference between the influence and the overall change in loss and (d) we evaluate our approach on real datasets, confirming our theoretical findings.}, keywords = {}, pubstate = {published}, tppubtype = {workshop} } We consider a crowdsourcing data acquisition scenario, such as federated learning, where a Center collects data points from a set of rational Agents, with the aim of training a model. For linear regression models, we show how a payment structure can be designed to incentivize the agents to provide high-quality data as early as possible, based on a characterization of the influence that data points have on the loss function of the model. Our contributions can be summarized as follows: (a) we prove theoretically that this scheme ensures truthful data reporting as a game-theoretic equilibrium and further demonstrate its robustness against mixtures of truthful and heuristic data reports, (b) we design a procedure according to which the influence computation can be efficiently approximated and processed sequentially in batches over time, (c) we develop a theory that allows correcting the difference between the influence and the overall change in loss and (d) we evaluate our approach on real datasets, confirming our theoretical findings. |
Goel, Naman; Faltings, Boi PermLink Personalized Peer Truth Serum for Eliciting Multi-Attribute Personal Data Conference 35th Conference on Uncertainty in Artificial Intelligence, Tel Aviv (UAI 2019), AUAI, 2019. @conference{Goel2019c, title = {Personalized Peer Truth Serum for Eliciting Multi-Attribute Personal Data}, author = {Naman Goel and Boi Faltings}, url = {https://lia.epfl.ch/~goel/upload/doc/papers/2019/goel_uai19.pdf}, year = {2019}, date = {2019-07-22}, booktitle = {35th Conference on Uncertainty in Artificial Intelligence, Tel Aviv (UAI 2019)}, publisher = {AUAI}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Balatsoukas-Stimming, Alexios; Filos-Ratsikas, Aris PermLink On the Computational Complexity of Blind Detection of Binary Linear Codes Conference 2019 IEEE International Symposium on Information Theory, IEEE, 2019. @conference{Balatsoukas-Stimming2019, title = {On the Computational Complexity of Blind Detection of Binary Linear Codes}, author = {Alexios Balatsoukas-Stimming and Aris Filos-Ratsikas}, url = {https://arxiv.org/pdf/1806.01050.pdf}, year = {2019}, date = {2019-07-07}, booktitle = {2019 IEEE International Symposium on Information Theory}, publisher = {IEEE}, abstract = {In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set C only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set C only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem. |
Filos-Ratsikas, Aris; Goldberg, Paul W PermLink The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches Conference The 51st Annual ACM Symposium on the Theory of Computing (STOC 2019), ACM, 2019. @conference{Filos-Ratsikas2019, title = {The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches}, author = {Aris Filos-Ratsikas and Paul W. Goldberg}, url = {https://arxiv.org/abs/1805.12559}, year = {2019}, date = {2019-06-27}, booktitle = {The 51st Annual ACM Symposium on the Theory of Computing (STOC 2019)}, publisher = {ACM}, abstract = {We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of "natural" problems whose definitions do not incorporate a circuit. |
Ioannis Caragiannis Aris Filos-Ratsikas, Panagiotis Kanellopoulos ; Vaish, Rohit PermLink Stable Fractional Matchings Conference The 20th ACM conference on Economics and Computation (ACM EC '19), 2019. @conference{Caragiannis2019, title = {Stable Fractional Matchings}, author = {Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos and Rohit Vaish}, url = {https://arxiv.org/pdf/1902.06698.pdf}, year = {2019}, date = {2019-06-24}, booktitle = {The 20th ACM conference on Economics and Computation (ACM EC '19)}, abstract = {We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). After observing that, in this cardinal setting, stable fractional matchings can have much higher social welfare than stable integral ones, our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) or nearly-optimal stable fractional matching. We present simple approximation algorithms for this problem with weak welfare guarantees and, rather unexpectedly, we furthermore show that achieving better approximations is hard. This computational hardness persists even for approximate stability. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings. En route to these results, we provide a number of structural observations.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). After observing that, in this cardinal setting, stable fractional matchings can have much higher social welfare than stable integral ones, our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) or nearly-optimal stable fractional matching. We present simple approximation algorithms for this problem with weak welfare guarantees and, rather unexpectedly, we furthermore show that achieving better approximations is hard. This computational hardness persists even for approximate stability. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings. En route to these results, we provide a number of structural observations. |
Mi, Fei; Huang, Minlie; Zhang, Jiyong; Faltings, Boi PermLink Meta-Learning for Low-resource Natural Language Generation in Task-oriented Dialogue Systems Conference The 28th International Joint Conference on Artificial Intelligence (IJCAI '19), 2019. @conference{Mi2019, title = {Meta-Learning for Low-resource Natural Language Generation in Task-oriented Dialogue Systems}, author = {Fei Mi and Minlie Huang and Jiyong Zhang and Boi Faltings}, url = {https://arxiv.org/pdf/1905.05644.pdf}, year = {2019}, date = {2019-05-14}, booktitle = {The 28th International Joint Conference on Artificial Intelligence (IJCAI '19)}, pages = {3151-3157}, abstract = {Natural language generation (NLG) is an essential component of task-oriented dialogue systems. Despite the recent success of neural approaches for NLG, they are typically developed for particular domains with rich annotated training examples. In this paper, we study NLG in a low-resource setting to generate sentences in new scenarios with handful training examples. We formulate the problem from a meta-learning perspective, and propose a generalized optimization-based approach (Meta-NLG) based on the well-recognized model-agnostic metalearning (MAML) algorithm. Meta-NLG defines a set of meta tasks, and directly incorporates the objective of adapting to new low-resource NLG tasks into the meta-learning optimization process. Extensive experiments are conducted on a large multidomain dataset (MultiWoz) with diverse linguistic variations. We show that Meta-NLG significantly outperforms other training procedures in various low-resource configurations. We analyze the results, and demonstrate that Meta-NLG adapts extremely fast and well to low-resource situations.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Natural language generation (NLG) is an essential component of task-oriented dialogue systems. Despite the recent success of neural approaches for NLG, they are typically developed for particular domains with rich annotated training examples. In this paper, we study NLG in a low-resource setting to generate sentences in new scenarios with handful training examples. We formulate the problem from a meta-learning perspective, and propose a generalized optimization-based approach (Meta-NLG) based on the well-recognized model-agnostic metalearning (MAML) algorithm. Meta-NLG defines a set of meta tasks, and directly incorporates the objective of adapting to new low-resource NLG tasks into the meta-learning optimization process. Extensive experiments are conducted on a large multidomain dataset (MultiWoz) with diverse linguistic variations. We show that Meta-NLG significantly outperforms other training procedures in various low-resource configurations. We analyze the results, and demonstrate that Meta-NLG adapts extremely fast and well to low-resource situations. |
Panayiotis Danassis, Boi Faltings PermLink Courtesy As a Means to Coordinate Conference Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19 International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2019, ISBN: 978-1-4503-6309-9. @conference{danassisaamas2019, title = {Courtesy As a Means to Coordinate}, author = {Panayiotis Danassis, Boi Faltings}, url = {http://dl.acm.org/citation.cfm?id=3306127.3331754}, isbn = {978-1-4503-6309-9}, year = {2019}, date = {2019-05-13}, booktitle = {Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems}, pages = {665--673}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, series = {AAMAS '19}, abstract = {We investigate the problem of multi-agent coordination under rationality constraints. Specifically, role allocation, task assignment, resource allocation, etc. Inspired by human behavior, we propose a framework (CA^3NONY) that enables fast convergence to efficient and fair allocations based on a simple convention of courtesy. We prove that following such convention induces a strategy which constitutes an epsilon-subgame-perfect equilibrium of the repeated allocation game with discounting. Simulation results highlight the effectiveness of CA^3NONY as compared to state-of-the-art bandit algorithms, since it achieves more than two orders of magnitude faster convergence, higher efficiency, fairness, and average payoff.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We investigate the problem of multi-agent coordination under rationality constraints. Specifically, role allocation, task assignment, resource allocation, etc. Inspired by human behavior, we propose a framework (CA^3NONY) that enables fast convergence to efficient and fair allocations based on a simple convention of courtesy. We prove that following such convention induces a strategy which constitutes an epsilon-subgame-perfect equilibrium of the repeated allocation game with discounting. Simulation results highlight the effectiveness of CA^3NONY as compared to state-of-the-art bandit algorithms, since it achieves more than two orders of magnitude faster convergence, higher efficiency, fairness, and average payoff. |