Pamela meeting in Lille: Sept 4/5

  • Where:
    INRIA Lille (Room B21)
  • When: Wednesday Sept. 5

Schedule

Tuesday 4th

8:30pm : Diner in Lille. Le Barbier qui fume Lille Europe 51 rue d’Esch-sur-Alzette 59000 Lille (Be careful, there is also another one in the vieux Lille)

Wednesday 5th

  • 8:30am Decentralized Frank-Wolfe Boosting for Collaborative Learning of Personalized Models We propose a new decentralized technique for collaboratively learning personalized models over a graph of users which is both effective and communication efficient. Our learning problem takes the form of a graph-regularized l1-Adaboost able to build expressive nonlinear models that take into account the singularities of the data of each user but also tend to follow the decisions of neighboring users in the graph. The associated optimization problem jointly minimizes the overall empirical error while ensuring the smoothness of the users’ models with respect to the similarity graph. We propose a decentralized algorithm based on Frank-Wolfe, exploiting the intrinsic sparsity of the updates to obtain an efficient collaborative learning procedure with low communication cost. To make up for the potential absence of background knowledge on the similarities between users, we additionally introduce a formulation to jointly learn the personalized models and the graph topology through an alternating optimization procedure. Finally, we analyze the convergence rate, memory consumption and communication complexity of our algorithm and empirically compare its performance to state-of-the-art decentralized techniques.

    Valentina Zantedeschi, Aurélien Bellet, and Marc Tommasi

  • 9:00: Random Binary Search Trees with Concurrent Insertions We consider the following simple random experiment to determine the impact of concurrency on the performance of binary search trees: n randomly permuted keys arrive one at a time. When a new key arrives, it is first placed into a buffer of size c. Whenever the buffer is full, or when all keys have arrived, an adversary chooses one key from the buffer and inserts it into the binary search tree. The ability of the adversary to choose the next key to insert among c buffered keys, models a distributed system, where up to c processes try to insert keys concurrently. We show that the expected average depth of nodes in the resulting tree is 2ln n + O(c), for any adversarial strategy of choosing the next buffered key to inserted into the tree. This result is tight, and answers an open question by Aspnes and Ruppert (DISC 2016).

    George Giakkoupis, Philipp Woelfel: An Improved Bound for Random Binary Search Trees with Concurrent Insertions. STACS 2018: 37:1-37:13

  • 9:30: Experiments with Federated Learning

    David Leroy, Snips

  • 10:00: Pause

  • 10:30: Case studies, Mediego
  • 12:00: Lunch
  • 13:30 Sprinkler, Cascade

    Adrien Luxey

  • 14:00 Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter! Recommendation systems help users identify interesting content, but they also open new privacy threats. In this paper, we deeply analyze the effect of a Sybil attack that tries to infer information on users from a user-based collaborative- filtering recommendation systems. We discuss the impact of different similarity metrics used to identity users with similar tastes in the trade-off between recommendation quality and privacy. Finally, we propose and evaluate a novel similarity metric that combines the best of both worlds: a high recommendation quality with a low prediction accuracy for the attacker. Our results, on a state-of-the-art recommendation framework and on real datasets show that existing similarity metrics exhibit a wide range of behaviors in the presence of Sybil attacks, while our new similarity metric consistently achieves the best trade-off while outperforming state-of-the-art solutions.

    Antoine Boutet, Florestan De Moor, Davide Frey, Rachid Guerraoui, Anne-Marie Kermarrec, et al.. Collaborative Filtering Under a Sybil Attack: Similarity Metrics do Matter!. the 48th International Conference on Dependable Systems and Networks (DSN-2018), Jun 2018, Luxembourg

  • 14:30 Case studies, Snips.