Jamal Atif

TMLR Journal 2025 Journal Article

Differentially Private Gradient Flow based on the Sliced Wasserstein Distance

• Ilana Sebag
• Muni Sreenivas Pydi
• Jean-Yves Franceschi
• Alain Rakotomamonjy
• Mike Gartrell
• Jamal Atif
• Alexandre Allauzen

Safeguarding privacy in sensitive training data is paramount, particularly in the context of generative modeling. This can be achieved through either differentially private stochastic gradient descent or a differentially private metric for training models or generators. In this paper, we introduce a novel differentially private generative modeling approach based on a gradient flow in the space of probability measures. To this end, we define the gradient flow of the Gaussian-smoothed Sliced Wasserstein Distance, including the associated stochastic differential equation (SDE). By discretizing and defining a numerical scheme for solving this SDE, we demonstrate the link between smoothing and differential privacy based on a Gaussian mechanism, due to a specific form of the SDE's drift term. We then analyze the differential privacy guarantee of our gradient flow, which accounts for both the smoothing and the Wiener process introduced by the SDE itself. Experiments show that our proposed model can generate higher-fidelity data at a low privacy budget compared to a generator-based model, offering a promising alternative.

NeurIPS Conference 2024 Conference Paper

Optimal Classification under Performative Distribution Shift

• Edwige Cyffers
• Muni S. Pydi
• Jamal Atif
• Oliver Cappé

Performative learning addresses the increasingly pervasive situations in which algorithmic decisions may induce changes in the data distribution as a consequence of their public deployment. We propose a novel view in which these performative effects are modelled as push forward measures. This general framework encompasses existing models and enables novel performative gradient estimation methods, leading to more efficient and scalable learning strategies. For distribution shifts, unlike previous models which require full specification of the data distribution, we only assume knowledge of the shift operator that represents the performative changes. This approach can also be integrated into various change-of-variable-based models, such as VAEs or normalizing flows. Focusing on classification with a linear-in-parameters performative effect, we prove the convexity of the performative risk under a new set of assumptions. Notably, we do not limit the strength of performative effects but rather their direction, requiring only that classification becomes harder when deploying more accurate models. In this case, we also establish a connection with adversarially robust classification by reformulating the performative risk as a min-max variational problem. Finally, we illustrate our approach on synthetic and real datasets.

IJCAI Conference 2023 Conference Paper

Online Certification of Preference-Based Fairness for Personalized Recommender Systems (Extended Abstract)

• Virginie Do
• Sam Corbett-Davies
• Jamal Atif
• Nicolas Usunier

Recommender systems are facing scrutiny because of their growing impact on the opportunities we have access to. Current audits for fairness are limited to coarse-grained parity assessments at the level of sensitive groups. We propose to audit for envy-freeness, a more granular criterion aligned with individual preferences: every user should prefer their recommendations to those of other users. Since auditing for envy requires to estimate the preferences of users beyond their existing recommendations, we cast the audit as a new pure exploration problem in multi-armed bandits. We propose a sample-efficient algorithm with theoretical guarantees that it does not deteriorate user experience. We also study the trade-offs achieved on real-world recommendation datasets.

AAAI Conference 2022 Conference Paper

Online Certification of Preference-Based Fairness for Personalized Recommender Systems

• Virginie Do
• Sam Corbett-Davies
• Jamal Atif
• Nicolas Usunier

Recommender systems are facing scrutiny because of their growing impact on the opportunities we have access to. Current audits for fairness are limited to coarse-grained parity assessments at the level of sensitive groups. We propose to audit for envy-freeness, a more granular criterion aligned with individual preferences: every user should prefer their recommendations to those of other users. Since auditing for envy requires to estimate the preferences of users beyond their existing recommendations, we cast the audit as a new pure exploration problem in multi-armed bandits. We propose a sample-efficient algorithm with theoretical guarantees that it does not deteriorate user experience. We also study the tradeoffs achieved on real-world recommendation datasets.

NeurIPS Conference 2022 Conference Paper

Towards Consistency in Adversarial Classification

• Laurent Meunier
• Raphael Ettedgui
• Rafael Pinot
• Yann Chevaleyre
• Jamal Atif

In this paper, we study the problem of consistency in the context of adversarial examples. Specifically, we tackle the following question: can surrogate losses still be used as a proxy for minimizing the $0/1$ loss in the presence of an adversary that alters the inputs at test-time? Different from the standard classification task, this question cannot be reduced to a point-wise minimization problem, and calibration needs not to be sufficient to ensure consistency. In this paper, we expose some pathological behaviors specific to the adversarial problem, and show that no convex surrogate loss can be consistent or calibrated in this context. It is therefore necessary to design another class of surrogate functions that can be used to solve the adversarial consistency issue. As a first step towards designing such a class, we identify sufficient and necessary conditions for a surrogate loss to be calibrated in both the adversarial and standard settings. Finally, we give some directions for building a class of losses that could be consistent in the adversarial framework.

ICML Conference 2021 Conference Paper

Mixed Nash Equilibria in the Adversarial Examples Game

• Laurent Meunier
• Meyer Scetbon
• Rafael Pinot
• Jamal Atif
• Yann Chevaleyre

This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of mixed Nash equilibria in the zero-sum game formed by the attacker and the classifier. While previous works usually allow only one player to use randomized strategies, we show the necessity of considering randomization for both the classifier and the attacker. We demonstrate that this game has no duality gap, meaning that it always admits approximate Nash equilibria. We also provide the first optimization algorithms to learn a mixture of classifiers that approximately realizes the value of this game, \emph{i. e. } procedures to build an optimally robust randomized classifier.

AAAI Conference 2021 Conference Paper

On Lipschitz Regularization of Convolutional Layers using Toeplitz Matrix Theory

• Alexandre Araujo
• Benjamin Negrevergne
• Yann Chevaleyre
• Jamal Atif

This paper tackles the problem of Lipschitz regularization of Convolutional Neural Networks. Lipschitz regularity is now established as a key property of modern deep learning with implications in training stability, generalization, robustness against adversarial examples, etc. However, computing the exact value of the Lipschitz constant of a neural network is known to be NP-hard. Recent attempts from the literature introduce upper-bounds to approximate this constant that are either efficient but loose or accurate but computationally expensive. In this work, by leveraging the theory of Toeplitz matrices, we introduce a new upper-bound for convolutional layers that is both tight and easy to compute. Based on this result we devise an algorithm to train Lipschitz regularized Convolutional Neural Networks.

IJCAI Conference 2021 Conference Paper

Online Selection of Diverse Committees

• Virginie Do
• Jamal Atif
• Jérôme Lang
• Nicolas Usunier

Citizens' assemblies need to represent subpopulations according to their proportions in the general population. These large committees are often constructed in an online fashion by contacting people, asking for the demographic features of the volunteers, and deciding to include them or not. This raises a trade-off between the number of people contacted (and the incurring cost) and the representativeness of the committee. We study three methods, theoretically and experimentally: a greedy algorithm that includes volunteers as long as proportionality is not violated; a non-adaptive method that includes a volunteer with a probability depending only on their features, assuming that the joint feature distribution in the volunteer pool is known; and a reinforcement learning based approach when this distribution is not known a priori but learnt online.

NeurIPS Conference 2021 Conference Paper

Two-sided fairness in rankings via Lorenz dominance

• Virginie Do
• Sam Corbett-Davies
• Jamal Atif
• Nicolas Usunier

We consider the problem of generating rankings that are fair towards both users and item producers in recommender systems. We address both usual recommendation (e. g. , of music or movies) and reciprocal recommendation (e. g. , dating). Following concepts of distributive justice in welfare economics, our notion of fairness aims at increasing the utility of the worse-off individuals, which we formalize using the criterion of Lorenz efficiency. It guarantees that rankings are Pareto efficient, and that they maximally redistribute utility from better-off to worse-off, at a given level of overall utility. We propose to generate rankings by maximizing concave welfare functions, and develop an efficient inference procedure based on the Frank-Wolfe algorithm. We prove that unlike existing approaches based on fairness constraints, our approach always produces fair rankings. Our experiments also show that it increases the utility of the worse-off at lower costs in terms of overall utility.

ICML Conference 2020 Conference Paper

Randomization matters How to defend against strong adversarial attacks

• Rafael Pinot
• Raphael Ettedgui
• Geovani Rizk
• Yann Chevaleyre
• Jamal Atif

\emph{Is there a classifier that ensures optimal robustness against all adversarial attacks? } This paper tackles this question by adopting a game-theoretic point of view. We present the adversarial attacks and defenses problem as an \emph{infinite} zero-sum game where classical results (\emph{e. g. } Nash or Sion theorems) do not apply. We demonstrate the non-existence of a Nash equilibrium in our game when the classifier and the Adversary are both deterministic, hence giving a negative answer to the above question in the deterministic regime. Nonetheless, the question remains open in the randomized regime. We tackle this problem by showing that any deterministic classifier can be outperformed by a randomized one. This gives arguments for using randomization, and leads us to a simple method for building randomized classifiers that are robust to state-or-the-art adversarial attacks. Empirical results validate our theoretical analysis, and show that our defense method considerably outperforms Adversarial Training against strong adaptive attacks, by achieving 0. 55 accuracy under adaptive PGD-attack on CIFAR10, compared to 0. 42 for Adversarial training.

ECAI Conference 2020 Conference Paper

Understanding and Training Deep Diagonal Circulant Neural Networks

• Alexandre Araujo
• Benjamin Négrevergne
• Yann Chevaleyre
• Jamal Atif

In this paper, we study deep diagonal circulant neural networks, which are deep neural networks in which weight matrices are the product of diagonal and circulant ones. Besides making a theoretical analysis of their expressivity, we introduce principled techniques for training these models: we devise an initialization scheme and propose a smart use of non-linearity functions in order to train deep diagonal circulant networks. Furthermore, we show that these networks outperform recently introduced deep networks with other types of structured layers. We conduct a thorough experimental study to compare the performance of deep diagonal circulant networks with state-of-the-art models based on structured matrices and with dense models. We show that our models achieve better accuracy than other structured approaches while requiring 2x fewer weights than the next best approach. Finally, we train compact and accurate deep diagonal circulant networks on a real world video classification dataset with over 3. 8 million training examples.

NeurIPS Conference 2019 Conference Paper

Theoretical evidence for adversarial robustness through randomization

• Rafael Pinot
• Laurent Meunier
• Alexandre Araujo
• Hisashi Kashima
• Florian Yger
• Cedric Gouy-Pailler
• Jamal Atif

This paper investigates the theory of robustness against adversarial attacks. It focuses on the family of randomization techniques that consist in injecting noise in the network at inference time. These techniques have proven effective in many contexts, but lack theoretical arguments. We close this gap by presenting a theo- retical analysis of these approaches, hence explaining why they perform well in practice. More precisely, we make two new contributions. The first one relates the randomization rate to robustness to adversarial attacks. This result applies for the general family of exponential distributions, and thus extends and unifies the previous approaches. The second contribution consists in devising a new upper bound on the adversarial risk gap of randomized neural networks. We support our theoretical claims with a set of experiments.

AIJ Journal 2018 Journal Article

Belief revision, minimal change and relaxation: A general framework based on satisfaction systems, and applications to description logics

• Marc Aiguier
• Jamal Atif
• Isabelle Bloch
• Céline Hudelot

Belief revision of knowledge bases represented by a set of sentences in a given logic has been extensively studied but for specific logics, mainly propositional, and also recently Horn and description logics. Here, we propose to generalize this operation from a model-theoretic point of view, by defining revision in the abstract model theory of satisfaction systems. In this framework, we generalize to any satisfaction system the characterization of the AGM postulates given by Katsuno and Mendelzon for propositional logic in terms of minimal change among interpretations. In this generalization, the constraint on syntax independence is partially relaxed. Moreover, we study how to define revision, satisfying these weakened AGM postulates, from relaxation notions that have been first introduced in description logics to define dissimilarity measures between concepts, and the consequence of which is to relax the set of models of the old belief until it becomes consistent with the new pieces of knowledge. We show how the proposed general framework can be instantiated in different logics such as propositional, first-order, description and Horn logics. In particular for description logics, we introduce several concrete relaxation operators tailored for the description logic ALC and its fragments EL and ELU, discuss their properties and provide some illustrative examples.

UAI Conference 2018 Conference Paper

Graph-based Clustering under Differential Privacy

• Rafael Pinot
• Anne Morvan
• Florian Yger
• Cédric Gouy-Pailler
• Jamal Atif

In this paper, we present the first differentially private clustering method for arbitraryshaped node clusters in a graph. This algorithm takes as input only an approximate Minimum Spanning Tree (MST) T released under weight differential privacy constraints from the graph. Then, the underlying nonconvex clustering partition is successfully recovered from cutting optimal cuts on T. As opposed to existing methods, our algorithm is theoretically well-motivated. Experiments support our theoretical findings.

NeurIPS Conference 2018 Conference Paper

Uplift Modeling from Separate Labels

• Ikko Yamane
• Florian Yger
• Jamal Atif
• Masashi Sugiyama

Uplift modeling is aimed at estimating the incremental impact of an action on an individual's behavior, which is useful in various application domains such as targeted marketing (advertisement campaigns) and personalized medicine (medical treatments). Conventional methods of uplift modeling require every instance to be jointly equipped with two types of labels: the taken action and its outcome. However, obtaining two labels for each instance at the same time is difficult or expensive in many real-world problems. In this paper, we propose a novel method of uplift modeling that is applicable to a more practical setting where only one type of labels is available for each instance. We show a mean squared error bound for the proposed estimator and demonstrate its effectiveness through experiments.

ECAI Conference 2016 Conference Paper

Efficient Semantic Tableau Generation for Abduction in Propositional Logic

• Yifan Yang
• Ricardo de Aldama
• Jamal Atif
• Isabelle Bloch

ECAI Conference 2014 Conference Paper

Concept Dissimilarity Based on Tree Edit Distances and Morphological Dilations

• Felix Distel
• Jamal Atif
• Isabelle Bloch

A number of similarity measures for comparing description logic concepts have been proposed. Criteria have been developed to evaluate a measure's fitness for an application. These criteria include on the one hand those that ensure compatibility with the semantics, such as equivalence soundness, and on the other hand the properties of a metric, such as the triangle inequality. In this work we present two classes of dissimilarity measures that are at the same time equivalence sound and satisfy the triangle inequality: a simple dissimilarity measure, based on description trees for the lightweight description logic EL; and an instantiation of a general framework, presented in our previous work, using dilation operators from mathematical morphology, and which exploits the link between Hausdorff distance and dilations using balls of the ground distance as structuring elements.

KR Conference 2014 Short Paper

Concept Dissimilarity with Triangle Inequality

• Felix Distel
• Jamal Atif
• Isabelle Bloch

and (Lehmann and Turhan 2012) list amongst others the properties of a metric, in particular the triangle inequality, as well as soundness with respect to equivalence and subsumption. The triangle inequality has been somewhat controversial and in some applications such as (Janowicz and Wilkes 2009) it is not needed. In other applications such as metricbased conceptual clustering and distance-based optimization methods it is crucial (Fayyad et al. 1996). Unfortunately, even the measures presented in (Lehmann and Turhan 2012) and (d’Amato, Staab, and Fanizzi 2008) with their otherwise good theoretical properties do not satisfy the triangle inequality. Our results aim to provide knowledge engineers from these fields with an adequate measure. In this work, we give a general framework that can be used to construct concept dissimilarity measures with good theoretical properties, including the triangle inequality. The framework is based on concept relaxations, operators that can be used to successively make concepts more general. A directed distance between two concepts C and D can then be defined as the number of times D needs to be relaxed before it subsumes C. We show that the maximum of the two directed distances yields a good dissimilarity measure. Finally, we demonstrate ways to instantiate the framework. Several researchers have developed properties that ensure compatibility of a concept similarity or dissimilarity measure with the formal semantics of Description Logics. While these authors have highlighted the relevance of the triangle inequality, none of their proposed dissimilarity measures satisfy it. In this work we present a theoretical framework for dissimilarity measures with this property. Our approach is based on concept relaxations, operators that perform stepwise generalizations on concepts. We prove that from any relaxation we can derive a dissimilarity measure that satisfies a number or properties that are important when comparing concepts.

ECAI Conference 2010 Conference Paper

Integrating Bipolar Fuzzy Mathematical Morphology in Description Logics for Spatial Reasoning

• Céline Hudelot
• Jamal Atif
• Isabelle Bloch

Bipolarity is an important feature of spatial information, involved in the expression of preferences and constraints about spatial positioning or in pairs of opposite spatial relations such as left and right. Another important feature is imprecision which has to be taken into account to model vagueness, inherent to many spatial relations (as for instance vague expressions such as close to, to the right of), and to gain in robustness in the representations. In previous works, we have shown that fuzzy sets and fuzzy mathematical morphology are appropriate frameworks, on the one hand, to represent bipolarity and imprecision of spatial relations and, on the other hand, to combine qualitative and quantitative reasoning in description logics extended with fuzzy concrete domains. The purpose of this paper is to integrate the bipolarity feature in the latter logical framework based on bipolar and fuzzy mathematical morphology and description logics with fuzzy concrete domains. Two important issues are addressed in this paper: the modeling of the bipolarity of spatial relations at the terminological level and the integration of bipolar notions in fuzzy description logics. At last, we illustrate the potential of the proposed formalism for spatial reasoning on a simple example in brain imaging.

ECAI Conference 2008 Conference Paper

Sequential spatial reasoning in images based on pre-attention mechanisms and fuzzy attribute graphs

• Geoffroy Fouquier
• Jamal Atif
• Isabelle Bloch

Spatial relations play a crucial role in model-based image recognition and interpretation due to their stability compared to many other image appearance characteristics, and graphs are well adapted to represent such information. Sequential methods for knowledgebased recognition of structures require to define in which order the structures have to be recognized, which can be expressed as the optimization of a path in the representation graph. We propose to integrate pre-attention mechanisms in the optimization criterion, in the form of a saliency map, by reasoning on the saliency of spatial area defined by spatial relations. Such mechanisms extract knowledge from an image without object recognition in advance and do not require any a priori knowledge on the image. Therefore, pre-attentional mechanisms provide useful knowledge for object segmentation and recognition. The derived algorithms are applied on brain image understanding.

ECAI Conference 2008 Conference Paper

Structure segmentation and recognition in images guided by structural constraint propagation

• Olivier Nempont
• Jamal Atif
• Elsa D. Angelini
• Isabelle Bloch

In some application domains, such as medical imaging, the objects that compose the scene are known as well as some of their properties and their spatial arrangement. We can take advantage of this knowledge to perform the segmentation and recognition of structures in medical images. We propose here to formalize this problem as a constraint network and we perform the segmentation and recognition by iterative domain reductions, the domains being sets of regions. For computational purposes we represent the domains by their upper and lower bounds and we iteratively reduce the domains by updating their bounds. We show some preliminary results on normal and pathological brain images.

IJCAI Conference 2007 Conference Paper

• Jamal Atif
• C
• eacute; line Hudelot
• Geoffroy Fouquier
• Isabelle Bloch
• Elsa Angelini

In several domains of spatial reasoning, such as medical image interpretation, spatial relations between structures play a crucial role since they are less prone to variability than intrinsic properties of structures. Moreover, they constitute an important part of available knowledge. We show in this paper how this knowledge can be appropriately represented by graphs and fuzzy models of spatial relations, which are integrated in a reasoning process to guide the recognition of individual structures in images. However pathological cases may deviate substantially from generic knowledge. We propose a method to adapt the knowledge representation to take into account the influence of the pathologies on the spatial organization of a set of structures, based on learning procedures. We also propose to adapt the reasoning process, using graph based propagation and updating.