Search

Your search keyword '"Inria de Paris"' showing total 6,454 results
Start Over Author "Inria de Paris"
6,454 results on '"Inria de Paris"'

1. Practical Error Bounds for Properties in Plane-Wave Electronic Structure Calculations

Author

Eric Cancès, Geneviève Dusson, Gaspard Kemlin, Antoine Levitt, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), MATHematics for MatERIALS (MATHERIALS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Mathématiques de Besançon (UMR 6623) (LMB), Université de Bourgogne (UB)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)

Subjects
Condensed Matter - Materials Science, Condensed Matter::Materials Science, Computational Mathematics, Applied Mathematics, FOS: Mathematics, [PHYS.COND.CM-MS]Physics [physics]/Condensed Matter [cond-mat]/Materials Science [cond-mat.mtrl-sci], Materials Science (cond-mat.mtrl-sci), FOS: Physical sciences, Numerical Analysis (math.NA), Mathematics - Numerical Analysis, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; We propose accurate computable error bounds for quantities of interest in plane-wave electronic structure calculations, in particular ground-state density matrices and energies, and interatomic forces. These bounds are based on an estimation of the error in terms of the residual of the solved equations, which is then efficiently approximated with computable terms. After providing coarse bounds based on an analysis of the inverse Jacobian, we improve on these bounds by solving a linear problem in a small dimension that involves a Schur complement. We numerically show how accurate these bounds are on a few representative materials, namely silicon, gallium arsenide and titanium dioxide.

Published
2022

2. Parallel approximation of the exponential of Hermitian matrices

Author

Hecht, Frédéric, Kaber, Sidi-Mahmoud, Perrin, Lucas, Plagne, Alain, Salomon, Julien, Algorithms and parallel tools for integrated numerical simulations (ALPINES), Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Numerical Analysis, Geophysics and Ecology (ANGE), Inria de Paris, Centre de Mathématiques Laurent Schwartz (CMLS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-CE46-0013,ALLOWAPP,Algorithmes pour l'optimisation à grande échelle de problèmes de propagation d'ondes(2019)

Subjects
FOS: Computer and information sciences, Parallel computing, MATLAB, Numerical Analysis (math.NA), Matrix exponential, Truncation error, AMS subject classifications. 15A16, 65F60, 65L99, 65Y05, Partial fraction decomposition, Computer Science - Distributed, Parallel, and Cluster Computing, Octave, FOS: Mathematics, Taylor series, expm, Pad\'e approximation, Distributed, Parallel, and Cluster Computing (cs.DC), Mathematics - Numerical Analysis, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Roundoff error, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

In this work, we consider a rational approximation of the exponential function to design an algorithm for computing matrix exponential in the Hermitian case. Using partial fraction decomposition, we obtain a parallelizable method, where the computation reduces to independent resolutions of linear systems. We analyze the effects of rounding errors on the accuracy of our algorithm. We complete this work with numerical tests showing the efficiency of our method and a comparison of its performances with Krylov algorithms.

Published
2023

3. QPLayer: efficient differentiation of convex quadratic optimization

Author

Bambade, Antoine, Schramm, Fabian, Taylor, Adrien, Carpentier, Justin, Models of visual object recognition and scene understanding (WILLOW), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), École des Ponts ParisTech (ENPC), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Louis Vuitton ENS Chair on Artificial Intelligence, ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), and European Project: 101070165,AGIMUS

Subjects
Machine Learning, Optimization, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization layers, Differentiable Optimization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract

Optimization layers within neural network architectures have become increasingly popular for their ability to solve a wide range of machine learning tasks and to model domain-specific knowledge. However, designing optimization layers requires careful consideration as the underlying optimization problems might be infeasible during training. Motivated by applications in learning, control, and robotics, this work focuses on convex quadratic programming (QP) layers. The specific structure of this type of optimization layer can be efficiently exploited for faster computations while still allowing rich modeling capabilities. We leverage primal-dual augmented Lagrangian techniques for computing derivatives of both feasible and infeasible QPs. Not requiring feasibility allows, as a byproduct, for more flexibility in the QP to be learned. The effectiveness of our approach is demonstrated in a few standard learning experiments, obtaining three to ten times faster computations than alternative state-of-the-art methods while being more accurate and numerically robust. Along with these contributions, we provide an open-source C++ software package called QPLayer for efficiently differentiating convex QPs and which can be interfaced with modern learning frameworks.

Published
2023

4. ISF et BDIFFMIN - Fonctions Matlab pour l'arrangement d'hyperplans et le calcul du B-différentiel du minimum par composante de deux fonctions vectorielles affines

Author

Dussault, Jean-Pierre, Gilbert, Jean Charles, Plaquevent-Jourdain, Baptiste, Université de Sherbrooke, Département d'Informatique, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Sherbrooke, Département de Mathématiques, and Inria de Paris, Université de Sherbrooke

Subjects
Strict linear inequalities, Hyperplane arrangement, Inégalités linéaires strictes, Minimum par composante de fonctions, Symétrie, Bipartition linéairement séparable d'un ensemble fini, Symmetry, B-differential, Winder's formula, 05A18, 05C40, 26A24, 26A27, 46N10, 47A50, 47A63, 49J52, 49N15, 52C35, 65Y20, 65K15, 90C33, 90C46, Stem vector, Isf, Arrangement d'hyperplans, Cône pointu, Formule de Winder, Borne de Schläfli, [MATH]Mathematics [math], Bdiffmin, Matlab, Circuit de matroïde, Pointed cone, Linearly separable bipartition of a finite set, Schläfli's bound, Matroid circuit, B-différentiel, Vecteur-souche, Componentwise minimum of functions
Abstract

The Matlab function Bdiffmin aims at computing the B-differential of the componentwise minimum of two affine vector functions. To realize this task, Bdiffmin calls the Matlab function Isf, which has been designed to determine the chambers of an arrangement of hyperplanes having a point in common. The sign vectors computed by the latter function can be used to solve a number of other enumeration problems such as determining the signed feasibility of strict inequality systems, listing the orthants encountered by the null space of a matrix, itemizing the pointed cones generated by a set of vectors and their inverses, giving the bipartitions of a finite set of points that can be separated by an affine hyperplane and many others.; La fonction Matlab Bdiffmin a pour but de calculer le B-différentiel du minimum par composante de deux fonctions vectorielles affines. Pour réaliser cette tâche, Bdiffmin fait appel à la fonction Matlab Isf, qui a été conçue pour déterminer les chambres d'un arrangement d'hyperplans ayant un point en commun. Les vecteurs de signes calculés par cette dernière fonction peuvent être utilisés pour résoudre un certain nombre d'autres problèmes d'énumération tels que la détermination de tous les sens des inégalités rendant un système d'inégalités strictes réalisable, établir la liste de tous les orthants rencontrés par le noyau d'une matrice, détailler tous les cônes pointus que l'on peut former au moyen d'un ensemble fini de vecteurs et de leurs inverses, donner les bipartitions d'un ensemble fini de points qui puissent être séparées par un hyperplan affine, ainsi que beaucoup d'autres problèmes.

Published
2023

5. OFence: Pairing Barriers to Find Concurrency Bugs in the Linux Kernel

Author

Baptiste Lepers, Josselin Giet, Willy Zwaenepoel, Julia Lawall, The University of Sydney, Analyse Statique par Interprétation Abstraite (ANTIQUE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Well Honed Infrastructure Software for Programming Environments and Runtimes (Whisper), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and CSG Inria associate team

Subjects
static analysis, bug finding, kernel, memory barrier, concurrency, [INFO.INFO-OS]Computer Science [cs]/Operating Systems [cs.OS]
Abstract

This paper received a Best Paper Award at EuroSys 2023; International audience; Knowing which functions may execute concurrently is key to finding concurrency-related bugs. Existing tools infer the possibility of concurrency using dynamic analysis or by pairing functions that use the same locks. Code that relies on more relaxed concurrency controls is, by and large, out of the reach of existing concurrency-related bug-tracking tools. In this paper, we propose a new heuristic to automatically infer the possibility of concurrency in lockless code that relies on memory barriers (memory fences) for correctness, a task made complex by the fact that barriers do not have a unique identifier and do not have a clearly delimited scope. To infer the possibility of concurrency between barriers, we propose a novel heuristic based on matching objects accessed before and after barriers. Our approach is based on the observation that barriers work in pairs: if a write memory barrier orders writes to a set of objects, then there should be a read barrier that orders reads to the same set of objects. This pairing strategy allows us to infer which barriers are meant to run concurrently and, in turn, check the code surrounding the barriers for concurrency-related bugs. As a example of a type of concurrency bug, we focus on bugs related to the incorrect placement of reads or writes relative to barriers. When we detect incorrect read or write placements in the code, we automatically produce a patch to fix them. We evaluate our heuristic on the Linux kernel. Our analysis runs in 8 minutes. We fixed 12 incorrect ordering constraints that could have resulted in hard-to-debug data corruption or kernel crashes. The patches have been merged in the mainline kernel. None of the bugs could have been found using existing static analysis heuristics.

Published
2023

6. Neural Network Information Leakage through Hidden Learning

Author

Arthur Carvalho Walraven da Cunha, Emanuele Natale, Laurent Viennot, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Centre National de la Recherche Scientifique (CNRS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), OPAL-Meso, COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Inria, CNRS, I3S, and Université Côte d'Azur

Subjects
Artificial Neural Network, Hidden computation, Information security, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG]
Abstract

We investigate the problem of making a neural network perform some hidden computation whose result can be easily retrieved from the network output. In particular, we consider the following scenario. A user is provided a neural network for a classification task by a company. We further assume that the company has limited access to the user's computation, and can only observe the output of the network when the user evaluates it. The user's input to the network contains some sensible information. We provide a simple and efficient training procedure, called Hidden Learning, that produces two networks such that i) One of the networks solves the original classification task with comparable performance to state of the art solutions of the task; ii) The other network takes as input the output of the first and solves another classification task that retrieves the sensible information with considerable accuracy. Our result might expose important issues from an information security point of view, as for the use of artificial neural networks in sensible applications.

Published
2023

7. A GKP qubit protected by dissipation in a high-impedance superconducting circuit driven by a microwave frequency comb

Author

Sellem, Lev-Arcady, Sarlette, Alain, Leghtas, Zaki, Mirrahimi, Mazyar, Rouchon, Pierre, Campagne-Ibarcq, Philippe, MATHematics for MatERIALS (MATHERIALS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), QUANTum Information Circuits (QUANTIC), Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de physique de l'ENS - ENS Paris (LPENS), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, Université Paris sciences et lettres (PSL), Centre Automatique et Systèmes (CAS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Laboratoire de physique de l'ENS - ENS Paris (LPENS), ANR-18-CE47-0005,HAMROQS,Modèles réduits haute précision pour systèmes quantiques ouverts(2018), ANR-20-CE47-0007,SYNCAMIL,Synthèse d'hamiltonians non locaux pour la protection d'information quantique(2020), ANR-22-PETQ-0006,NISQ2LSQ,From NISQ to LSQ: Bosonic and LDPC codes(2022), European Project: 884762,Q-Feedback, European Project: 101042304,HORIZON.1.1 - European Research Council (ERC),ERC-2021-STG - ERC STARTING GRANTS,DANCINGFOOL(2022), and European Project: 851740,H2020-EU.1.1. - EXCELLENT SCIENCE - European Research Council (ERC),10.3030/851740,ECLIPSE(2020)

Subjects
Quantum Physics, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], Optimization and Control (math.OC), FOS: Mathematics, FOS: Physical sciences, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Quantum Physics (quant-ph), Mathematics - Optimization and Control
Abstract

We propose a novel approach to generate, protect and control GKP qubits. It employs a microwave frequency comb parametrically modulating a Josephson circuit to enforce a dissipative dynamics of a high impedance circuit mode, autonomously stabilizing the finite-energy GKP code. The encoded GKP qubit is robustly protected against all dominant decoherence channels plaguing superconducting circuits but quasi-particle poisoning. In particular, noise from ancillary modes leveraged for dissipation engineering does not propagate at the logical level. In a state-of-the-art experimental setup, we estimate that the encoded qubit lifetime could extend two orders of magnitude beyond the break-even point, with substantial margin for improvement through progress in fabrication and control electronics. Qubit initialization, readout and control via Clifford gates can be performed while maintaining the code stabilization, paving the way toward the assembly of GKP qubits in a fault-tolerant quantum computing architecture., 61 pages, 20 figures, 1 table

Published
2023

8. Sur le B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles

Author

Dussault, Jean-Pierre, Gilbert, Jean Charles, Plaquevent-Jourdain, Baptiste, Université de Sherbrooke, Département d'Informatique, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Sherbrooke, Département de Mathématiques, and Inria de Paris, Université de Sherbrooke

Subjects
Approche duale, Strict linear inequalities, Hyperplane arrangement, Inégalités linéaires strictes, Minimum par composante de fonctions, Symétrie, Bipartition of a finite set, Dual approach, Symmetry, B-differential, Winder's formula, 05A18, 05C40, 26A24, 26A27, 46N10, 47A50, 47A63, 49J52, 49N15, 52C35, 65Y20, 65K15, 90C33, 90C46, C-differential, Stem vector, Arrangement d'hyperplans, Cône pointu, Formule de Winder, Complexité, [MATH]Mathematics [math], Connectivity, Circuit de matroïde, Pointed cone, Complexity, Complementarity problem, Matroid circuit, B-différentiel, C-différentiel, Vecteur-souche, Gordan's alternative, Problème de complémentarité, Componentwise minimum of functions, Connexité, Alternative de Gordan, Bipartition d'un ensemble fini
Abstract

This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. These formulations are used to state some properties of the B-differential, like its symmetry, condition for its completeness, its connectivity, bounds on its cardinal, etc. The set to specify has a finite number of elements, which may grow exponentially with the range space dimension of the functions, so that its description is most often algorithmic. We present first an incremental-recursive approach avoiding to solve any optimization subproblem, which is based on the notion of matroid circuit and the related introduced concept of stem vector. Next, we propose modifications, adapted to the problem at stake, of an algorithm introduced by Rada and Černý in 2018 for determining the cells of an arrangement in the space of hyperplanes having a point in common. Measured in CPU time on the considered test-problems, the mean acceleration ratios of the proposed algorithms, with respect to the one of Rada and Černý, are in the range 7..15, and this speed-up can exceed 30, depending on the problem and the approach.; Cet article se concentre sur la description et le calcul du B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles. Ce problème se pose dans la reformulation du problème de complémentarité linéaire avec la C-fonction Min. Cette question a de nombreuses formulations équivalentes et nous en citons quelques-unes en algèbre linéaire, en analyse convexe et en géométrie discrète. Ces formulations sont utilisées pour établir certaines propriétés du B-différentiel, comme sa symétrie, une condition assurant sa complétude, sa connectivité, des bornes sur son cardinal, etc. L'ensemble à décrire comporte un nombre fini d'éléments, qui peut grandir exponentiellement avec la dimension de l'espace d'arrivée des fonctions, de sorte que sa description est le plus souvent algorithmique. Nous présentons d'abord une approche incrémentale-récursive, qui évite de résoudre des problèmes d'optimisation et qui est fondée sur la notion de circuit de matroïde et sur le concept introduit adjacent de vecteur-souche. Ensuite, nous proposons des modifications, adaptées au problème posé, d'un algorithme introduit par Rada et Černý en 2018 pour déterminer les cellules d'un arrangement dans l'espace d'hyperplans ayant un point commun. Mesurée en temps CPU sur les problèmes-tests considérés, les moyennes des quotients d'accélération des algorithmes proposés, par rapport à celui de Rada et Černý, sont de l'ordre de 7..15, et cette accélération peut dépasser 30, selon le problème et l'approche.

Published
2023

9. Sur le B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles - Le rapport complet

Author

Dussault, Jean-Pierre, Gilbert, Jean Charles, Plaquevent-Jourdain, Baptiste, Université de Sherbrooke, Département d'Informatique, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Sherbrooke, Département de Mathématiques, and Inria de Paris, France & Université de Sherbrooke, Canada

Subjects
Approche duale, Strict linear inequalities, Hyperplane arrangement, Inégalités linéaires strictes, Minimum par composante de fonctions, Symétrie, Bipartition of a finite set, Dual approach, AMS MSC 2020: 05A18, 05C40, 26A24, 26A27, 46N10, 47A50, 47A63, 49J52, 49N15, 52C35, 65Y20, 65K15, 90C33, 90C46, Symmetry, B-differential, Winder's formula, C-differential, Stem vector, Cône pointu, Arrangement d'hyperplans, Formule de Winder, Complexité, [MATH]Mathematics [math], Connectivity, Circuit de matroïde, Pointed cone, Complexity, Complementarity problem, Matroid circuit, B-différentiel, C-différentiel, Vecteur-souche, Gordan's alternative, Problème de complémentarité, Componentwise minimum of functions, Connexité, Bipartition d'un ensemble fini, Alternative de Gordan
Abstract

This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. These formulations are used to state some properties of the B-differential, like its symmetry, condition for its completeness, its connectivity, bounds on its cardinal, etc. The set to specify has a finite number of elements, which may grow exponentially with the range space dimension of the functions, so that its description is most often algorithmic. We present first an incremental-recursive approach avoiding to solve any optimization subproblem, which is based on the notion of matroid circuit and the related introduced concept of stem vector. Next, we propose modifications, adapted to the problem at stake, of an algorithm introduced by Rada and Černý in 2018 for determining the cells of an arrangement in the space of hyperplanes having a point in common. Measured in CPU time on the considered test-problems, the mean acceleration ratios of the proposed algorithms, with respect to the one of Rada and Černý, are in the range 7..15, and this speed-up can exceed 30, depending on the problem and the approach.; Cet article se concentre sur la description et le calcul du B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles. Ce problème se pose dans la reformulation du problème de complémentarité linéaire avec la C-fonction Min. Cette question a de nombreuses formulations équivalentes et nous en citons quelques-unes en algèbre linéaire, en analyse convexe et en géométrie discrète. Ces formulations sont utilisées pour établir certaines propriétés du B-différentiel, comme sa symétrie, une condition assurant sa complétude, sa connectivité, des bornes sur son cardinal, etc. L'ensemble à décrire comporte un nombre fini d'éléments, qui peut grandir exponentiellement avec la dimension de l'espace d'arrivée des fonctions, de sorte que sa description est le plus souvent algorithmique. Nous présentons d'abord une approche incrémentale-récursive, qui évite de résoudre des problèmes d'optimisation et qui est fondée sur la notion de circuit de matroïde et sur le concept introduit adjacent de vecteur-souche. Ensuite, nous proposons des modifications, adaptées au problème posé, d'un algorithme introduit par Rada et Černý en 2018 pour déterminer les cellules d'un arrangement dans l'espace d'hyperplans ayant un point commun. Mesurée en temps CPU sur les problèmes-tests considérés, les moyennes des quotients d'accélération des algorithmes proposés, par rapport à celui de Rada et Černý, sont de l'ordre de 7..15, et cette accélération peut dépasser 30, selon le problème et l'approche.

Published
2023

10. Spatially-Consistent Feature Matching and Learning for Heritage Image Analysis

Author

Xi Shen, Robin Champenois, Shiry Ginosar, Ilaria Pastrolin, Morgane Rousselot, Oumayma Bounou, Tom Monnier, Spyros Gidaris, François Bougard, Pierre-Guillaume Raverdy, Marie-Françoise Limon, Christine Bénévent, Marc Smith, Olivier Poncet, K. Bender, Béatrice Joyeux-Prunel, Elizabeth Honig, Alexei A. Efros, Mathieu Aubry, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, University of California [Berkeley], University of California, École nationale des chartes (ENC), Université Paris sciences et lettres (PSL), Models of visual object recognition and scene understanding (WILLOW), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Valeo.ai, VALEO, Centre National de la Recherche Scientifique (CNRS), Service Expérimentation et Développement [Paris] (SED), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Archives nationales, Université de Genève (UNIGE), This work was supported in part by ANR project EnHerit ANR-17-CE23-0008, PSL Filigrane pour tous project, project Rapid Tabasco, gifts from Adobe to Ecole des Ponts., ANR-17-CE23-0008,EnHerit,Exploitation des bases d'images patrimoniales(2017), University of California [Berkeley] (UC Berkeley), University of California (UC), Centre Jean Mabillon (CJM), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and Université de Genève = University of Geneva (UNIGE)

Subjects
Self-supervised learning, Artificial Intelligence, Feature learning, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Computer Vision and Pattern Recognition, Artwork analysis, Software, Historical watermark recognition, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; Progress in the digitization of cultural assets leads to online databases that become too large for a human to analyze. Moreover, some analyses might be challenging, even for experts. In this paper, we explore two applications of computer vision to analyze historical data: watermark recognition and one-shot repeated pattern detection in artwork collections. Both problems present computer vision challenges which we believe to be representative of the ones encountered in cultural heritage applications: limited supervision is available, the tasks are fine-grained recognition, and the data comes in several different modalities. Both applications are also highly practical, as recognizing watermarks makes it possible to date and locate documents, while detecting repeated patterns allows exploring visual links between artworks. We demonstrate on both tasks the benefits of relying on deep mid-level features. More precisely, we define an image similarity score based on geometric verification of mid-level features and show how spatial consistency can be used to fine-tune out-of-the-box features for the target dataset with weak or no supervision. This paper relates and extends our previous works. Our code and data are available at \url{http://imagine.enpc.fr/~shenx/HisImgAnalysis/}.

Published
2022

11. Flexibility can Hurt Dynamic Matching System Performance

Author

Arnaud Cadas, Josu Doncel, Jean-Michel Fourneau, Ana Busic, Dynamics of Geometric Networks (DYOGENE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Universidad del Pais Vasco / Euskal Herriko Unibertsitatea [Espagne] (UPV/EHU), Données et algorithmes pour une ville intelligente et durable - DAVID (DAVID), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
FOS: Computer and information sciences, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Computer Science - Computer Science and Game Theory, Computer Networks and Communications, Hardware and Architecture, Probability (math.PR), FOS: Mathematics, Mathematics - Probability, Software, Computer Science and Game Theory (cs.GT)
Abstract

International audience; We study the performance of general dynamic matching models. This model is defined by a connected graph, where nodes represent the class of items and the edges the compatibilities between items. Items of different classes arrive one by one to the system according to a given probability distribution. Upon arrival, an item is matched with a compatible item according to the First Come First Served discipline and leave the system immediately, whereas it is enqueued with other items of the same class, if any. We show that such a model may exhibit a non intuitive behavior: increasing the services ability by adding new edges in the matching graph may lead to a larger average population. This is similar to a Braess paradox. We first consider a quasicomplete graph with four nodes and we provide values of the probability distribution of the arrivals such that when we add an edge the mean number of items is larger. Then, we consider an arbitrary matching graph and we show sufficient conditions for the existence or non-existence of this paradox. We conclude that the analog to the Braess paradox in matching models is given when specific independent sets are in saturation, i.e., the system is close to the stability condition.

Published
2022

12. SOTT: Greedy Approximation of a Tensor as a Sum of Tensor Trains

Author

Ehrlacher, Virginie, Ruiz, Maria Fuente, Lombardi, Damiano, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), MATHematics for MatERIALS (MATHERIALS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), COmputational Mathematics for bio-MEDIcal Applications (COMMEDIA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), ANR-18-CE46-0001,ADAPT,Méthodes tensorielles parallèles dynamiques et adaptatives(2018), ANR-19-CE46-0002,COMODO,Systèmes de diffusion croisée sur des domaines en mouvement(2019), European Project: 810367,EMC2(2019), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), and École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)

Subjects
65D15, Computational Mathematics, Tensor methods, Applied Mathematics, Canonical Polyadic, Tensor Train AMS subject classifications. 65F99, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience In the present work, a method is proposed in order to compute an approximation of a given tensor as a sum of Tensor Trains (TTs), where the order of the variates and the values of the ranks can vary from one term to the other in an adaptive way. The numerical scheme is based on a greedy algorithm and an adaptation of the TT-SVD method. The proposed approach can also be used in order to compute an approximation of a tensor in a Canonical Polyadic format (CP), as an alternative to standard algorithms like Alternating Linear Squares (ALS) or Alternating Singular Value Decomposition (ASVD) methods. Some numerical experiments are proposed, in which the proposed method is compared to ALS and ASVD methods for the construction of a CP approximation of a given tensor and performs particularly well for high-order tensors. The interest of approximating a tensor as a sum of Tensor Trains is illustrated in several numerical test cases.

Published
2022

13. Dispelling myths on superposition attacks: formal security model and attack analyses

Author

Céline Chevalier, Luka Music, Elham Kashefi, Information Quantique [LIP6] (QI), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), School of Informatics [Edimbourg], University of Edinburgh, Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities (CASCADE), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Centre de Recherche en Economie et Droit (CRED), Université Panthéon-Assas (UP2), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Quandela SAS, Université Paris-Panthéon-Assas, and ANR-18-CE39-0015,CryptiQ,Cryptographie dans un monde quantique(2018)

Subjects
FOS: Computer and information sciences, 050101 languages & linguistics, Computer Science - Cryptography and Security, Computer science, FOS: Physical sciences, 02 engineering and technology, Computer security, computer.software_genre, Superposition principle, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], Quantum state, Intuition (Bergson), 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], 0501 psychology and cognitive sciences, Quantum information science, Computer Science::Cryptography and Security, Quantum Physics, Applied Mathematics, 05 social sciences, TheoryofComputation_GENERAL, Mythology, Computer security model, Adversary, Cryptographic protocol, 16. Peace & justice, Computer Science Applications, 020201 artificial intelligence & image processing, Quantum Physics (quant-ph), computer, Cryptography and Security (cs.CR)
Abstract

It is of folkloric belief that the security of classical cryptographic protocols is automatically broken if the Adversary is allowed to perform superposition queries and the honest players forced to perform actions coherently on quantum states. Another widely held intuition is that enforcing measurements on the exchanged messages is enough to protect protocols from these attacks. However, the reality is much more complex. Security models dealing with superposition attacks only consider unconditional security. Conversely, security models considering computational security assume that all supposedly classical messages are measured, which forbids by construction the analysis of superposition attacks. Boneh and Zhandry have started to study the quantum computational security for classical primitives in their seminal work at Crypto'13, but only in the single-party setting. To the best of our knowledge, an equivalent model in the multiparty setting is still missing. In this work, we propose the first computational security model considering superposition attacks for multiparty protocols. We show that our new security model is satisfiable by proving the security of the well-known One-Time-Pad protocol and give an attack on a variant of the equally reputable Yao Protocol for Secure Two-Party Computations. The post-mortem of this attack reveals the precise points of failure, yielding highly counter-intuitive results: Adding extra classical communication, which is harmless for classical security, can make the protocol become subject to superposition attacks. We use this newly imparted knowledge to construct the first concrete protocol for Secure Two-Party Computation that is resistant to superposition attacks. Our results show that there is no straightforward answer to provide for either the vulnerabilities of classical protocols to superposition attacks or the adapted countermeasures., 46 pages

Published
2022

14. Nonlinear acceleration of momentum and primal-dual algorithms

Author

Raghu Bollapragada, Damien Scieur, Alexandre d’Aspremont, Northwestern University [Evanston], Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019)

Subjects
[STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), General Mathematics, FOS: Mathematics, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Mathematics - Optimization and Control, Software, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; We describe a convergence acceleration scheme for multistep optimization algorithms. The extrapolated solution is written as a nonlinear average of the iterates produced by the original optimization algorithm. Our scheme does not need the underlying fixed-point operator to be symmetric, hence handles e.g. algorithms with momentum terms such as Nesterov's accelerated method, or primal-dual methods. The weights are computed via a simple linear system and we analyze performance in both online and offline modes. We use Crouzeix's conjecture to show that acceleration performance is controlled by the solution of a Chebyshev problem on the numerical range of a non-symmetric operator modelling the behavior of iterates near the optimum. Numerical experiments are detailed on image processing problems, logistic regression and neural network training for CIFAR10 and ImageNet.

Published
2022

15. DP-Parse: Finding Word Boundaries from Raw Speech with an Instance Lexicon

Author

Algayres, Robin, Ricoul, Tristan, Karadayi, Julien, Laurençon, Hugo, Zaiem, Salah, Mohamed, Abdelrahman, Sagot, Benoît, Dupoux, Emmanuel, Apprentissage machine et développement cognitif (CoML), Laboratoire de sciences cognitives et psycholinguistique (LSCP), Département d'Etudes Cognitives - ENS Paris (DEC), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Département d'Etudes Cognitives - ENS Paris (DEC), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Meta AI Research [Paris], Meta AI, Automatic Language Modelling and ANAlysis & Computational Humanities (ALMAnaCH), Inria de Paris, and École des hautes études en sciences sociales (EHESS)

Subjects
FOS: Computer and information sciences, Human-Computer Interaction, Linguistics and Language, Computer Science - Computation and Language, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Artificial Intelligence, Communication, [SCCO.COMP]Cognitive science/Computer science, [SCCO.LING]Cognitive science/Linguistics, Computation and Language (cs.CL), Computer Science Applications
Abstract

Finding word boundaries in continuous speech is challenging as there is little or no equivalent of a ‘space’ delimiter between words. Popular Bayesian non-parametric models for text segmentation (Goldwater et al., 2006, 2009) use a Dirichlet process to jointly segment sentences and build a lexicon of word types. We introduce DP-Parse, which uses similar principles but only relies on an instance lexicon of word tokens, avoiding the clustering errors that arise with a lexicon of word types. On the Zero Resource Speech Benchmark 2017, our model sets a new speech segmentation state-of-the-art in 5 languages. The algorithm monotonically improves with better input representations, achieving yet higher scores when fed with weakly supervised inputs. Despite lacking a type lexicon, DP-Parse can be pipelined to a language model and learn semantic and syntactic representations as assessed by a new spoken word embedding benchmark. 1

Published
2022

16. Data Augmentation in High Dimensional Low Sample Size Setting Using a Geometry-Based Variational Autoencoder

Author

Clément Chadebec, Elina Thibeau-Sutre, Ninon Burgos, Stéphanie Allassonnière, Chadebec, Clément, PaRis Artificial Intelligence Research InstitutE - - PRAIRIE2019 - ANR-19-P3IA-0001 - P3IA - VALID, Institut de Neurosciences Translationnelles de Paris - - IHU-A-ICM2010 - ANR-10-IAHU-0006 - IAHU - VALID, Université Paris Cité (UPCité), Institut National de la Santé et de la Recherche Médicale (INSERM), Centre de Recherche des Cordeliers (CRC (UMR_S_1138 / U1138)), École pratique des hautes études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université Paris Cité (UPCité), Sorbonne Université (SU), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Health data- and model- driven Knowledge Acquisition (HeKA), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche des Cordeliers (CRC (UMR_S_1138 / U1138)), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université Paris Cité (UPCité)-École pratique des hautes études (EPHE), Institut du Cerveau = Paris Brain Institute (ICM), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Sorbonne Université (SU)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU), Algorithms, models and methods for images and signals of the human brain (ARAMIS), Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut du Cerveau = Paris Brain Institute (ICM), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Sorbonne Université (SU)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), ANR-10-IAHU-0006,IHU-A-ICM,Institut de Neurosciences Translationnelles de Paris(2010), École Pratique des Hautes Études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université Paris Cité (UPCité)-École Pratique des Hautes Études (EPHE), Université de Paris (UP), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université de Paris (UP), Institut du Cerveau et de la Moëlle Epinière = Brain and Spine Institute (ICM), Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut du Cerveau et de la Moëlle Epinière = Brain and Spine Institute (ICM), Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], and Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Applied Mathematics, Machine Learning (stat.ML), Data Augmentation, [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Machine Learning (cs.LG), Variational Autoencoder, Latent space representation, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Computational Theory and Mathematics, Statistics - Machine Learning, Artificial Intelligence, Computer Vision and Pattern Recognition, Software
Abstract

In this paper, we propose a new method to perform data augmentation in a reliable way in the High Dimensional Low Sample Size (HDLSS) setting using a geometry-based variational autoencoder. Our approach combines a proper latent space modeling of the VAE seen as a Riemannian manifold with a new generation scheme which produces more meaningful samples especially in the context of small data sets. The proposed method is tested through a wide experimental study where its robustness to data sets, classifiers and training samples size is stressed. It is also validated on a medical imaging classification task on the challenging ADNI database where a small number of 3D brain MRIs are considered and augmented using the proposed VAE framework. In each case, the proposed method allows for a significant and reliable gain in the classification metrics. For instance, balanced accuracy jumps from 66.3% to 74.3% for a state-of-the-art CNN classifier trained with 50 MRIs of cognitively normal (CN) and 50 Alzheimer disease (AD) patients and from 77.7% to 86.3% when trained with 243 CN and 210 AD while improving greatly sensitivity and specificity metrics., Comment: accepted to IEEE transactions on pattern analysis and machine intelligence (TPAMI)

Published
2022

17. On Non-Linear operators for Geometric Deep Learning

Author

Sergeant-Perthuis, Grégoire, Maier, Jakob, Bruna, Joan, Oyallon, Edouard, OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dynamics of Geometric Networks (DYOGENE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), Machine Learning and Information Access (MLIA), Institut des Systèmes Intelligents et de Robotique (ISIR), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), EO was supported by the Project ANR-21-CE23-0030 ADONIS and EMERG-ADONIS from Alliance SU. GSP was also supported by France Relance and Median Technologies., and ANR-21-CE23-0030,ADONIS,Optimization asynchrone décentralisée de modèle d'apprentissage automatique(2021)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Artificial Intelligence (cs.AI), Computer Science - Artificial Intelligence, Computer Science - Neural and Evolutionary Computing, Neural and Evolutionary Computing (cs.NE), [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

This work studies operators mapping vector and scalar fields defined over a manifold $\mathcal{M}$, and which commute with its group of diffeomorphisms $\text{Diff}(\mathcal{M})$. We prove that in the case of scalar fields $L^p_\omega(\mathcal{M,\mathbb{R}})$, those operators correspond to point-wise non-linearities, recovering and extending known results on $\mathbb{R}^d$. In the context of Neural Networks defined over $\mathcal{M}$, it indicates that point-wise non-linear operators are the only universal family that commutes with any group of symmetries, and justifies their systematic use in combination with dedicated linear operators commuting with specific symmetries. In the case of vector fields $L^p_\omega(\mathcal{M},T\mathcal{M})$, we show that those operators are solely the scalar multiplication. It indicates that $\text{Diff}(\mathcal{M})$ is too rich and that there is no universal class of non-linear operators to motivate the design of Neural Networks over the symmetries of $\mathcal{M}$.

Published
2023

18. Recommandations sur les « éditeurs de la zone grise »

Author

Blanqui, Frédéric, Canteaut, Anne, de Jong, Hidde, Imperiale, Sébastien, Mitton, Nathalie, Pallez, Guillaume, Pennec, Xavier, Rival, Xavier, Thirion, Bertrand, Deduction modulo, interopérabilité et démonstration automatique (DEDUCTEAM), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Cryptologie symétrique, cryptologie fondée sur les codes et information quantique (COSMIQ), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Analyse, ingénierie et contrôle des micro-organismes (MICROCOSME), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Grenoble Alpes (UGA), Mathematical and Mechanical Modeling with Data Interaction in Simulations for Medicine (M3DISIM), Laboratoire de mécanique des solides (LMS), École polytechnique (X)-Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Self-organizing Future Ubiquitous Network (FUN), Inria Lille - Nord Europe, Scalable Storage for Clouds and Beyond (KerData), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), E-Patient : Images, données & mOdèles pour la médeciNe numériquE (EPIONE), Inria Sophia Antipolis - Méditerranée (CRISAM), Analyse Statique par Interprétation Abstraite (ANTIQUE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Modèles et inférence pour les données de Neuroimagerie (MIND), IFR49 - Neurospin - CEA, Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Inria Saclay - Ile de France, and Inria

Subjects
[INFO]Computer Science [cs], [MATH]Mathematics [math]
Abstract

Recommandations de la Commission d'Évaluation Inria, adoptées le 25 janvier 2023, sur certains éditeurs, notamment MDPI et Frontiers, qui prennent depuis quelques années une place significative dans les domaines de l'informatique et des mathématiques, disciplines où ils étaient absents par le passé.

Published
2023

19. STOP: A dataset for spoken task oriented semantic parsing

Author

Tomasello, Paden, Shrivastava, Akshat, Lazar, Daniel, Hsu, Po-Chun, Le, Duc, Sagar, Adithya, Elkahky, Ali, Copet, Jade, Hsu, Wei-Ning, Adi, Yossi, Algayres, Robin, Nguyen, Tu Ahn, Dupoux, Emmanuel, Zettlemoyer, Luke, Mohamed, Abdelrahman, Meta AI, University of Tampere [Finland], Laboratoire de sciences cognitives et psycholinguistique (LSCP), Département d'Etudes Cognitives - ENS Paris (DEC), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Apprentissage machine et développement cognitif (CoML), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Département d'Etudes Cognitives - ENS Paris (DEC), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dalhousie University [Halifax], Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), École des hautes études en sciences sociales (EHESS), Department of Computer Science & Engineering (CSE), and University of Washington [Seattle]

Subjects
FOS: Computer and information sciences, Domain adaptation, Sound (cs.SD), Computer Science - Computation and Language, Computer Science - Artificial Intelligence, Assistant, [SCCO.LING]Cognitive science/Linguistics, Computer Science - Sound, Spoken language understanding, Artificial Intelligence (cs.AI), Audio and Speech Processing (eess.AS), FOS: Electrical engineering, electronic engineering, information engineering, Computation and Language (cs.CL), Electrical Engineering and Systems Science - Audio and Speech Processing
Abstract

End-to-end spoken language understanding (SLU) predicts intent directly from audio using a single model. It promises to improve the performance of assistant systems by leveraging acoustic information lost in the intermediate textual representation and preventing cascading errors from Automatic Speech Recognition (ASR). Further, having one unified model has efficiency advantages when deploying assistant systems on-device. However, the limited number of public audio datasets with semantic parse labels hinders the research progress in this area. In this paper, we release the Spoken Task-Oriented semantic Parsing (STOP) dataset, the largest and most complex SLU dataset to be publicly available. Additionally, we define low-resource splits to establish a benchmark for improving SLU when limited labeled data is available. Furthermore, in addition to the human-recorded audio, we are releasing a TTS-generated version to benchmark the performance for low-resource domain adaptation of end-to-end SLU systems. Initial experimentation show end-to-end SLU models performing slightly worse than their cascaded counterparts, which we hope encourages future work in this direction.

Published
2023

20. Stability and decoherence rates of a GKP qubit protected by dissipation

Author

Sellem, Lev-Arcady, Robin, Rémi, Campagne-Ibarcq, Philippe, Rouchon, Pierre, MATHematics for MatERIALS (MATHERIALS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), QUANTum Information Circuits (QUANTIC), Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de physique de l'ENS - ENS Paris (LPENS), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, Université Paris sciences et lettres (PSL), Centre Automatique et Systèmes (CAS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Laboratoire de physique de l'ENS - ENS Paris (LPENS), and European Project: 884762,Q-Feedback

Subjects
Quantum Physics, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], Optimization and Control (math.OC), FOS: Mathematics, FOS: Physical sciences, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Quantum Physics (quant-ph), Mathematics - Optimization and Control
Abstract

We analyze an experimentally accessible Lindblad master equation for a quantum harmonic oscillator. It approximately stabilizes finite-energy periodic grid states called Gottesman-Kitaev-Preskill (GKP) states, that can be used to encode and protect a logical qubit. We give explicit upper bounds for the energy of the solutions of the Lindblad master equation. Using three periodic observables to define the Bloch sphere coordinates of a logical qubit, we show that their dynamics is governed by a diffusion partial differential equation on a 2D-torus with a Witten Laplacian. We show that the evolution of these logical coordinates is exponentially slow even in presence of small diffusive noise processes along the two quadratures of the phase space. Numerical simulations indicate similar results for other physically relevant noise processes., Comment: 16 pages, 1 figure. This work has been accepted to IFAC for publication under a Creative Commons Licence CC-BY-NC-ND

Published
2023
Full Text
View/download PDF

21. Coherent presentations of monoids with a right-noetherian Garside family

Author

Pierre-Louis Curien, Alen Ɖurić, Yves Guiraud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Design, study and implementation of languages for proofs and programs (PI.R2), Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris Cité (UPCité)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), The second author has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement N° 754362., and European Project: 754362,MathInParis(2017)

Subjects
20M05, 18B40, 18N30, 20F36, 68Q42, Algebra and Number Theory, Artin-Tits monoid, Mathematics - Category Theory, Group Theory (math.GR), Monoid, Coherent presentation, Higher rewriting, MSC 2020 : 20M05, 18B40, 18N30, 20F36, 68Q42, Polygraph, [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], Mathematics::Group Theory, Mathematics::Category Theory, FOS: Mathematics, Category Theory (math.CT), Geometry and Topology, Mathematics - Group Theory, Garside family, [MATH.MATH-CT]Mathematics [math]/Category Theory [math.CT]
Abstract

28 pages; International audience; This paper shows how to construct coherent presentations (presentations by generators, relations and relations among relations) of monoids admitting a right-noetherian Garside family. Thereby, it resolves the question of finding a unifying generalisation of the following two distinct extensions of construction of coherent presentations for spherical Artin-Tits monoids: to general Artin-Tits monoids, and to Garside monoids. The result is applied to some monoids which are neither Artin-Tits nor Garside.

Published
2023

22. Sparse matrices: convergence of the characteristic polynomial seen from infinity

Author

Coste, Simon, Dynamics of Geometric Networks (DYOGENE), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), The author is supported by ERC NEMO, under the European Union’s Horizon 2020 research andinnovation programme grant agreement number 78885., Coste, Simon, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Statistics and Probability, [MATH.MATH-PR] Mathematics [math]/Probability [math.PR], Probability (math.PR), FOS: Mathematics, Statistics, Probability and Uncertainty, 05C80, 15B52, 30B20, Mathematics - Probability
Abstract

We prove that the reverse characteristic polynomial $\det(I_n - zA_n)$ of a random $n \times n$ matrix $A_n$ with iid $\mathrm{Bernoulli}(d/n)$ entries converges in distribution towards the random infinite product $\prod_{\ell = 1}^\infty(1-z^\ell)^{Y_\ell}$ where $Y_\ell$ are independent $\mathrm{Poisson}(d^\ell/\ell)$ random variables. We show that this random function is a Poisson analog of more classical Gaussian objects such as the Gaussian holomorphic chaos. As a byproduct, we obtain new simple proofs of previous results on the asymptotic behaviour of extremal eigenvalues of sparse Erd��s-R��nyi digraphs: for every $d>1$, the greatest eigenvalue of $A_n$ is close to $d$ and the second greatest is smaller than $\sqrt{d}$, a Ramanujan-like property for irregular digraphs. For $d, Added the semi-sparse case $d_n \to \infty$ and a more complete description of the $d_n=d

Published
2023

23. The limited-memory recursive variational Gaussian approximation (L-RVGA)

Author

Marc Lambert, Silvère Bonnabel, Francis Bach, Délégation générale de l'armement (DGA), Ministère de la Défense, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Centre de Robotique (CAOR), MINES ParisTech - École nationale supérieure des mines de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institut de sciences exactes et appliquées (ISEA), Université de la Nouvelle-Calédonie (UNC), Laboratoire d'informatique de l'école normale supérieure (LIENS), DGA, ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), European Project: 724063,ERC-2016-COG,SEQUOIA(2017), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Bayesian logistic regression, Statistics and Probability, FOS: Computer and information sciences, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], factor analysis, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [SPI.AUTO]Engineering Sciences [physics]/Automatic, Theoretical Computer Science, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], expectation-maximization, Computational Theory and Mathematics, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Kalman filter, Statistics, Probability and Uncertainty, Variational approximation
Abstract

We consider the problem of computing a Gaussian approximation to the posterior distribution of a parameter given a large number N of observations and a Gaussian prior, when the dimension of the parameter d is also large. To address this problem we build on a recently introduced recursive algorithm for variational Gaussian approximation of the posterior, called recursive variational Gaussian approximation (RVGA), which is a single pass algorithm, free of parameter tuning. In this paper, we consider the case where the parameter dimension d is high, and we propose a novel version of RVGA that scales linearly in the dimension d (as well as in the number of observations N), and which only requires linear storage capacity in d. This is afforded by the use of a novel recursive expectation maximization (EM) algorithm applied for factor analysis introduced herein, to approximate at each step the covariance matrix of the Gaussian distribution conveying the uncertainty in the parameter. The approach is successfully illustrated on the problems of high dimensional least-squares and logistic regression, and generalized to a large class of nonlinear models., Comment: Statistics and Computing, In press

Published
2023
Full Text
View/download PDF

24. Phase Semantics for Linear Logic with Least and Greatest Fixed Points

Author

De, Abhishek, Jafarrahmani, Farzad, Saurin, Alexis, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Design, study and implementation of languages for proofs and programs (PI.R2), Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris Cité (UPCité)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Les assistants à la démonstration au cœur du raisonnement mathématique (PICUBE), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), ANR-21-CE48-0019,RECIPROG,Raisonner avec des preuves circulaires pour la programmation(2021), and European Project

Subjects
Fixed points, Theory of computation → Linear logic, Phase semantics, Cosure ordinals, Theory of computation → Proof theory, Linear logic, Cut elimination, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], closure ordinals, Theory of computation → Proof theory phrases Linear logic
Abstract

The truth semantics of linear logic (i.e. phase semantics) is often overlooked despite having a wide range of applications and deep connections with several denotational semantics. In phase semantics, one is concerned about the provability of formulas rather than the contents of their proofs (or refutations). Linear logic equipped with the least and greatest fixpoint operators (μMALL) has been an active field of research for the past one and a half decades. Various proof systems are known viz. finitary and non-wellfounded, based on explicit and implicit (co)induction respectively. In this paper, we extend the phase semantics of multiplicative additive linear logic (a.k.a. MALL) to μMALL with explicit (co)induction (i.e. μMALL^{ind}). We introduce a Tait-style system for μMALL called μMALL_ω where proofs are wellfounded but potentially infinitely branching. We study its phase semantics and prove that it does not have the finite model property., LIPIcs, Vol. 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), pages 35:1-35:23

Published
2022

25. Infinite-Dimensional Sums-of-Squares for Optimal Control

Author

Berthier, Elo��se, Carpentier, Justin, Rudi, Alessandro, Bach, Francis, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Models of visual object recognition and scene understanding (WILLOW), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, This work was supported by the Direction Générale de l’Armement, and by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grants SEQUOIA 724063 and REAL 947908). We thank Didier Henrion for interesting discussions related to this work., IEEE, ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control
Abstract

International audience; We introduce an approximation method to solve an optimal control problem via the Lagrange dual of its weak formulation. It is based on a sum-of-squares representation of the Hamiltonian, and extends a previous method from polynomial optimization to the generic case of smooth problems. Such a representation is infinite-dimensional and relies on a particular space of functions-a reproducing kernel Hilbert space-chosen to fit the structure of the control problem. After subsampling, it leads to a practical method that amounts to solving a semi-definite program. We illustrate our approach by a numerical application on a simple low-dimensional control problem.

Published
2022

26. The rule-based model approach. A Kappa model for hepatic stellate cells activation by TGFB1

Author

Bouguéon, Matthieu, Boutillier, Pierre, Feret, Jérôme, Hazard, Octave, Théret, Nathalie, Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de recherche en santé, environnement et travail (Irset), Université d'Angers (UA)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École des Hautes Études en Santé Publique [EHESP] (EHESP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Structure Fédérative de Recherche en Biologie et Santé de Rennes ( Biosit : Biologie - Santé - Innovation Technologique ), Nomadic Labs, Analyse Statique par Interprétation Abstraite (ANTIQUE), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X), Elisabetta De Maria, EHESP-Irset (EHESP-Irset), École des Hautes Études en Santé Publique [EHESP] (EHESP), Dynamics, Logics and Inference for biological Systems and Sequences (Dyliss), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
Rules-based language, Reversion, Liver Fibrosis, HSC, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], ComputingMilieux_MISCELLANEOUS, Kappa
Abstract

International audience; In this chapter, we introduce Kappa, a site graph rewriting language. As a realistic case study, we model a population of hepatic stellate cells under the effect of the TGFB1 protein. Kappa offers a rule-centric approach, inspired from chemistry, where interaction rules locally modify the state of a system that is defined as a graph of components, connected or not. In this case study, the components will be occurrences of hepatic stellate cells in different states, and occurrences of the protein TGFB1. The protein TGFB1 induces different behaviors of hepatic stellate cells thereby contribut- ing either to tissue repair or to fibrosis. Better understanding the overall behavior of the mechanisms that are involved in these processes is a key issue to identify markers and therapeutic targets likely to promote the resolution of fibrosis at the expense of its progression.

Published
2022

27. Verified Lustre Normalization with Node Subsampling

Author

Basile Pesin, Paul Jeanmaire, Marc Pouzet, Timothy Bourke, Université Paris sciences et lettres (PSL), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallélisme de Kahn Synchrone ( Parkas), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), BPI 'Programme d'Investissements d'Avenir' - ES3CAP, ANR-19-CE25-0014,FidelR,FidelR(2019), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
CCS Concepts: • Software and its engineering → Formal language definitions, Normalization (statistics), interactive theorem proving, Correctness, Computer science, Semantics (computer science), Dataflow, • Computer systems organization → Embedded software stream languages, 02 engineering and technology, computer.software_genre, Software verification, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, computer.programming_language, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Assembly language, Programming language, Lustre (programming language), Proof assistant, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, verified compilation, Compilers, Hardware and Architecture, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Compiler, computer, Software
Abstract

Dataflow languages allow the specification of reactive systems by mutually recursive stream equations, functions, and boolean activation conditions called clocks. Lustre and Scade are dataflow languages for programming embedded systems. Dataflow programs are compiled by a succession of passes. This article focuses on the normalization pass which rewrites programs into the simpler form required for code generation. Vélus is a compiler from a normalized form of Lustre to CompCert’s Clight language. Its specification in the Coq interactive theorem prover includes an end-to-end correctness proof that the values prescribed by the dataflow semantics of source programs are produced by executions of generated assembly code. We describe how to extend Vélus with a normalization pass and to allow subsampled node inputs and outputs. We propose semantic definitions for the unrestricted language, divide normalization into three steps to facilitate proofs, adapt the clock type system to handle richer node definitions, and extend the end-to-end correctness theorem to incorporate the new features. The proofs require reasoning about the relation between static clock annotations and the presence and absence of values in the dynamic semantics. The generalization of node inputs requires adding a compiler pass to ensure the initialization of variables passed in function calls.

Published
2021

28. Complete Positivity Violation in Higher-order Quantum Adiabatic Elimination

Author

Tokieda, Masaaki, Elouard, Cyril, Sarlette, Alain, Rouchon, Pierre, MATHematics for MatERIALS (MATHERIALS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Traitement optimal de l'information avec des dispositifs quantiques (QINFO), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), QUANTum Information Circuits (QUANTIC), Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de physique de l'ENS - ENS Paris (LPENS), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, Université Paris sciences et lettres (PSL), Centre Automatique et Systèmes (CAS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), ANR-18-CE47-0005,HAMROQS,Modèles réduits haute précision pour systèmes quantiques ouverts(2018), and European Project: 884762,Q-Feedback

Subjects
Lindblad master equation, Quantum Physics, Quantum information, FOS: Physical sciences, Completely positive map, Jaynes-Cummings Hamiltonian, Open quantum systems, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], Adiabatic elimination, Qubit, Quantum harmonic oscillator, Quantum Physics (quant-ph), Invariant manifold
Abstract

When a composite Lindblad system consists of weakly coupled sub-systems with fast and slow timescales, the description of slow dynamics can be simplified by discarding fast degrees of freedom. This model reduction technique is called adiabatic elimination. While second-order perturbative expansion with respect to the timescale separation has revealed that the evolution of a reduced state is completely positive, this paper presents an example exhibiting complete positivity violation in the fourth-order expansion. Despite the non-uniqueness of slow dynamics parametrization, we prove that complete positivity cannot be ensured in any parametrization. The violation stems from correlation in the initial state., 6 pages, submitted to IFAC for possible publication

Published
2022

29. Generative Spoken Dialogue Language Modeling: preprint version

Author

Nguyen, Tu Anh, Kharitonov, Eugene, Copet, Jade, Adi, Yossi, Hsu, Wei-Ning, Elkahky, Ali, Tomasello, Paden, Algayres, Robin, Sagot, Benoît, Mohamed, Abdelrahman, Dupoux, Emmanuel, Meta AI, Automatic Language Modelling and ANAlysis & Computational Humanities (ALMAnaCH), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École des hautes études en sciences sociales (EHESS), Apprentissage machine et développement cognitif (CoML), Laboratoire de sciences cognitives et psycholinguistique (LSCP), Département d'Etudes Cognitives - ENS Paris (DEC), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Département d'Etudes Cognitives - ENS Paris (DEC), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris

Subjects
[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

We introduce dGSLM, the first "textless" model able to generate audio samples of naturalistic spoken dialogues. It uses recent work on unsupervised spoken unit discovery coupled with a dual-tower transformer architecture with cross-attention trained on 2000 hours of two-channel raw conversational audio (Fisher dataset) without any text or labels. It is able to generate speech, laughter and other paralinguistic signals in the two channels simultaneously and reproduces naturalistic turn taking. Generation samples can be found at: https://speechbot.github.io/dgslm.

Published
2022

30. Are word boundaries useful for unsupervised language learning?

Author

Nguyen, Tu Anh, de Seyssel, Maureen, Algayres, Robin, Roze, Patricia, Dunbar, Ewan, Dupoux, Emmanuel, Meta AI, Automatic Language Modelling and ANAlysis & Computational Humanities (ALMAnaCH), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Apprentissage machine et développement cognitif (CoML), Laboratoire de sciences cognitives et psycholinguistique (LSCP), Département d'Etudes Cognitives - ENS Paris (DEC), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Département d'Etudes Cognitives - ENS Paris (DEC), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Laboratoire de Linguistique Formelle (LLF - UMR7110), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), University of Toronto, and Meta AI Research [Paris]

Subjects
FOS: Computer and information sciences, Computer Science - Computation and Language, [SHS.LANGUE]Humanities and Social Sciences/Linguistics, Computation and Language (cs.CL)
Abstract

Word or word-fragment based Language Models (LM) are typically preferred over character-based ones in many downstream applications. This may not be surprising as words seem more linguistically relevant units than characters. Words provide at least two kinds of relevant information: boundary information and meaningful units. However, word boundary information may be absent or unreliable in the case of speech input (word boundaries are not marked explicitly in the speech stream). Here, we systematically compare LSTMs as a function of the input unit (character, phoneme, word, word part), with or without gold boundary information. We probe linguistic knowledge in the networks at the lexical, syntactic and semantic levels using three speech-adapted black box NLP psycholinguistically-inpired benchmarks (pWUGGY, pBLIMP, pSIMI). We find that the absence of boundaries costs between 2\% and 28\% in relative performance depending on the task. We show that gold boundaries can be replaced by automatically found ones obtained with an unsupervised segmentation algorithm, and that even modest segmentation performance gives a gain in performance on two of the three tasks compared to basic character/phone based models without boundary information., This is an archived version from September 2020

Published
2022

31. Adaptive force biasing algorithms: New convergence results and tensor approximations of the bias

Author

Virginie Ehrlacher, Tony Lelièvre, Pierre Monmarché, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), MATHematics for MatERIALS (MATHERIALS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), This work was supported by the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement number 614492 and under the European Union’s Horizon 2020 Research and Innovation Programme, ERC Grant Agreement number 810367, project EMC2. It was also supported by the ANR JCJC project COMODO (ANR-19-CE46-0002) and the ANR Project EFI (ANR-17-CE40-0030) of he French National Research Agency., ANR-19-CE46-0002,COMODO,Systèmes de diffusion croisée sur des domaines en mouvement(2019), ANR-17-CE40-0030,EFI,Entropie, flots, inégalités(2017), European Project: 9110745(1991), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), and École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)

Subjects
Statistics and Probability, Importance sampling, Probability (math.PR), Monte Carlo methods, Numerical Analysis (math.NA), Molecular dynamics, 65C05, 65N12 [MSC class (2010)], [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], 65C05, 65N12, Tensor, FOS: Mathematics, MSC class (2010): 65C05, 65N12, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Mathematics - Numerical Analysis, Free energy, Statistics, Probability and Uncertainty, Mathematics - Probability
Abstract

International audience We analyze and propose variants of the Adaptive Biasing Force method. First, we prove the convergence of a version of the algorithm where the biasing force is estimated using a weighted occupation measure, with an explicit asymptotic variance. Second, we propose a new flavour of the algorithm adapted to high dimensional reaction coordinates, for which the standard approaches suffer from the curse of dimensionality. More precisely, the free energy is approximated by a sum of tensor products of one-dimensional functions. The consistency of the tensor approximation is established. Numerical experiments on 5-dimensional reaction coordinates demonstrate that the method is indeed able to capture correlations between them.

Published
2022

32. Differentiable Collision Detection: a Randomized Smoothing Approach

Author

Montaut, Louis, Lidec, Quentin Le, Bambade, Antoine, Petrik, Vladimir, Sivic, Josef, Carpentier, Justin, Models of visual object recognition and scene understanding (WILLOW), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Czech Institute of Informatics, Robotics and Cybernetics [Prague] (CIIRC), Czech Technical University in Prague (CTU), École des Ponts ParisTech (ENPC), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres (PSL), and ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019)

Subjects
FOS: Computer and information sciences, Computer Science - Robotics, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], Robotics (cs.RO), [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Abstract

Collision detection appears as a canonical operation in a large range of robotics applications from robot control to simulation, including motion planning and estimation. While the seminal works on the topic date back to the 80s, it is only recently that the question of properly differentiating collision detection has emerged as a central issue, thanks notably to the ongoing and various efforts made by the scientific community around the topic of differentiable physics. Yet, very few solutions have been suggested so far, and only with a strong assumption on the nature of the shapes involved. In this work, we introduce a generic and efficient approach to compute the derivatives of collision detection for any pair of convex shapes, by notably leveraging randomized smoothing techniques which have shown to be particularly adapted to capture the derivatives of non-smooth problems. This approach is implemented in the HPP-FCL and Pinocchio ecosystems, and evaluated on classic datasets and problems of the robotics literature, demonstrating few micro-second timings to compute informative derivatives directly exploitable by many real robotic applications including differentiable simulation., 7 pages, 6 figures, 2 tables

Published
2022

33. Speech Sequence Embeddings using Nearest Neighbors Contrastive Learning

Author

Robin Algayres, Adel Nabli, Benoît Sagot, Emmanuel Dupoux, Apprentissage machine et développement cognitif (CoML), Laboratoire de sciences cognitives et psycholinguistique (LSCP), Département d'Etudes Cognitives - ENS Paris (DEC), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Département d'Etudes Cognitives - ENS Paris (DEC), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Automatic Language Modelling and ANAlysis & Computational Humanities (ALMAnaCH), Inria de Paris, Facebook AI Research [Paris] (FAIR), Facebook, Université Paris sciences et lettres (PSL), École des hautes études en sciences sociales (EHESS), This work was funded in part by facebook AI Research (Research Grant). This work was performed using HPC resources from GENCI-IDRIS (Grant 2021-[AD011011217]), ANR-17-EURE-0017,FrontCog,Frontières en cognition(2017), ANR-10-IDEX-0001,PSL,Paris Sciences et Lettres(2010), and ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019)

Subjects
FOS: Computer and information sciences, Artificial Intelligence (cs.AI), Data augmentation, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Computer Science - Artificial Intelligence, k-nearest neighbors, [SCCO.COMP]Cognitive science/Computer science, [SCCO.LING]Cognitive science/Linguistics, Unsupervised speech sequence embeddings
Abstract

International audience; We introduce a simple neural encoder architecture that can be trained using an unsupervised contrastive learning objective which gets its positive samples from data-augmented k-Nearest Neighbors search. We show that when built on top of recent self-supervised audio representations [1, 2, 3], this method can be applied iteratively and yield competitive SSE as evaluated on two tasks: query-by-example of random sequences of speech, and spoken term discovery. On both tasks our method pushes the state-of-the-art by a significant margin across 5 different languages. Finally, we establish a benchmark on a query-byexample task on the LibriSpeech dataset to monitor future improvements in the field.

Published
2022

34. On the method of reflections

Author

Julien Salomon, Guillaume Legendre, Philippe Laurent, Institut de Recherche en Communications et en Cybernétique de Nantes (IRCCyN), Mines Nantes (Mines Nantes)-École Centrale de Nantes (ECN)-Ecole Polytechnique de l'Université de Nantes (Polytech Nantes), Université de Nantes (UN)-Université de Nantes (UN)-PRES Université Nantes Angers Le Mans (UNAM)-Centre National de la Recherche Scientifique (CNRS), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Numerical Analysis, Geophysics and Ecology (ANGE), Laboratoire Jacques-Louis Lions (LJLL), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Mines Nantes (Mines Nantes)-École Centrale de Nantes (ECN)-Ecole Polytechnique de l'Université de Nantes (EPUN), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)

Subjects
Applied Mathematics, Numerical analysis, Boundary (topology), 010103 numerical & computational mathematics, 16. Peace & justice, 01 natural sciences, Domain (mathematical analysis), 010101 applied mathematics, Set (abstract data type), Computational Mathematics, Mathematics - Analysis of PDEs, Convergence (routing), FOS: Mathematics, Calculus, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Applied mathematics, Unconditional convergence, Boundary value problem, 0101 mathematics, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Subspace topology, Analysis of PDEs (math.AP), Mathematics
Abstract

International audience; This paper aims at reviewing and analysing the method of reflections. The latter is an iterative procedure designed to linear boundary value problems set in multiply connected domains. Being based on a decomposition of the domain boundary, this method is particularly well-suited to numerical solvers relying on integral representation formulas. For the parallel and sequential forms of the method appearing in the literature, we propose a general abstract formulation in a given Hilbert setting and interpret the procedure in terms of subspace corrections. We then prove the unconditional convergence of the sequential form and propose a modification of the parallel one that makes it unconditionally converging. An alternative proof of convergence is provided in a case which does not fit into the previous framework. We finally present some numerical tests.

Published
2021

35. Tameness and the power of programs over monoids in DA

Author

Grosshans, Nathan, Mckenzie, Pierre, Segoufin, Luc, University of Kassel, Département d'Informatique et de Recherche Opérationnelle [Montreal] (DIRO), Université de Montréal (UdeM), Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Universität Kassel [Kassel], École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), General Computer Science, DA, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.0: Algebraic language theory, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Mathematics::Category Theory, Tameness, F.1.1, F.4.3, F.1.3, Programs over monoids, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Lower bounds, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Computer Science::Programming Languages, ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.3: Complexity Measures and Classes, Computer Science - Discrete Mathematics
Abstract

International audience; The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as $\mathbf{DA}$ satisfies tameness and hence that the regular languages recognized by programs over monoids in $\mathbf{DA}$ are precisely those recognizable in the classical sense by morphisms from $\mathbf{QDA}$. Third, we show by contrast that the well studied class of monoids called $\mathbf{J}$ is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from $\mathbf{DA}$.

Published
2022

36. 33èmes Journées Francophones des Langages Applicatifs

Author

Keller, Chantal, Bourke, Timothy, Blazy, Sandrine, Bour, Frédéric, Bury, Guillaume, Dumbrava, Stefania, Gallois-Wong, Diane, Guatto, Adrien, Janin, David, Kerjean, Marie, Pellissier, Luc, Pereira, Mário, Trieu, Alix, Zakowski, Yannick, Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Parallélisme de Kahn Synchrone ( Parkas), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Langages de programmation : systèmes de types, concurrence, preuve de programme (CAMBIUM), Collège de France (CdF (institution))-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Tarides [Paris], OCamlPro SAS, Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), Nomadic Labs, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Algorithmique Complexité et Logique (LACL), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12), NOVA Laboratory for Computer Science and Informatics (NOVA-LINCS), Departamento de Informática (DI), Faculdade de Ciências e Tecnologia = School of Science & Technology (FCT NOVA), Universidade Nova de Lisboa = NOVA University Lisbon (NOVA)-Universidade Nova de Lisboa = NOVA University Lisbon (NOVA)-Faculdade de Ciências e Tecnologia = School of Science & Technology (FCT NOVA), Universidade Nova de Lisboa = NOVA University Lisbon (NOVA)-Universidade Nova de Lisboa = NOVA University Lisbon (NOVA), Aarhus University [Aarhus], Compilation et Analyse, Logiciel et Matériel (CASH), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Chantal Keller, Timothy Bourke, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Bourke, Timothy

Subjects
[INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL]
Abstract

International audience; Les 33èmes Journées Francophones des Langages Applicatifs (JFLA) se sont tenues à Saint-Médard-d'Excideuil, plus précisément Domaine d'Essendiéras (Périgord), du mardi 28 juin 2022 au vendredi 1er juillet 2022.Les JFLA réunissent concepteurs, utilisateurs et théoriciens ; elles ont pour ambition de couvrir les domaines des langages applicatifs, de la preuve formelle, de la vérification de programmes, et des objets mathématiques qui sous-tendent ces outils. Ces domaines doivent être pris au sens large : nous souhaitons promouvoir les ponts entre les différentes thématiques.- Langages fonctionnels et applicatifs : sémantique, compilation, optimisation, typage, mesures, extensions par d'autres paradigmes.- Assistants de preuve : implémentation, nouvelles tactiques, développements présentant un intérêt technique ou méthodologique.- Logique, correspondance de Curry-Howard, réalisabilité, extraction de programmes, modèles.- Spécification, prototypage, développements formels d'algorithmes.- Vérification de programmes ou de modèles, méthode déductive, interprétation abstraite, raffinement.- Utilisation industrielle des langages fonctionnels et applicatifs, ou des méthodes issues des preuves formelles, outils pour le web.Les articles soumis aux JFLA sont relus par au moins deux personnes s'ils sont acceptés, trois personnes s'ils sont rejetés. Les critiques des relecteurs sont toujours bienveillantes et la plupart du temps encourageantes et constructives, même en cas de rejet.

Published
2022

37. A robust and efficient line search for self-consistent field iterations

Author

Michael F. Herbst, Antoine Levitt, Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), MATHematics for MatERIALS (MATHERIALS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), École des Ponts ParisTech (ENPC), RWTH Aachen University, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), and École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)

Subjects
Condensed Matter - Materials Science, Numerical Analysis, Physics and Astronomy (miscellaneous), Applied Mathematics, MathematicsofComputing_NUMERICALANALYSIS, Materials Science (cond-mat.mtrl-sci), FOS: Physical sciences, Computational Physics (physics.comp-ph), Computer Science Applications, Computational Mathematics, Condensed Matter::Materials Science, Modeling and Simulation, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Physics::Chemical Physics, Physics - Computational Physics, ComputingMethodologies_COMPUTERGRAPHICS
Abstract

International audience; We propose a novel adaptive damping algorithm for the self-consistent field (SCF) iterations of Kohn-Sham density-functional theory, using a backtracking line search to automatically adjust the damping in each SCF step. This line search is based on a theoretically sound, accurate and inexpensive model for the energy as a function of the damping parameter. In contrast to usual damped SCF schemes, the resulting algorithm is fully automatic and does not require the user to select a damping. We successfully apply it to a wide range of challenging systems, including elongated supercells, surfaces and transition-metal alloys.

Published
2022

38. On the Effectiveness of Richardson Extrapolation in Data Science

Author

Francis Bach, Laboratoire d'informatique de l'école normale supérieure (LIENS), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support the European Research Council (grant SEQUOIA 724063)., PNRIA, ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris)

Subjects
021103 operations research, Numerical analysis, 0211 other engineering and technologies, Richardson extrapolation, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Kernel method, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Approximation error, Applied mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 0101 mathematics, Gradient descent, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Computer Science::Databases, Mathematics
Abstract

International audience; Richardson extrapolation is a classical technique from numerical analysis that can improve the approximation error of an estimation method by combining linearly several estimates obtained from different values of one of its hyperparameters, without the need to know in details the inner structure of the original estimation method. The main goal of this paper is to study when Richardson extrapolation can be used within machine learning, beyond the existing applications to step-size adaptations in stochastic gradient descent. We identify two situations where Richardson interpolation can be useful: (1) when the hyperparameter is the number of iterations of an existing iterative optimization algorithm, with applications to averaged gradient descent and Frank-Wolfe algorithms (where we obtain asymptotically rates of $O(1/k^2)$ on polytopes, where $k$ is the number of iterations), and (2) when it is a regularization parameter, with applications to Nesterov smoothing techniques for minimizing non-smooth functions (where we obtain asymptotically rates close to $O(1/k^2)$ for non-smooth functions), and ridge regression. In all these cases, we show that extrapolation techniques come with no significant loss in performance, but with sometimes strong gains, and we provide theoretical justifications based on asymptotic developments for such gains, as well as empirical illustrations on classical problems from machine learning.

Published
2021

39. FANOK: Knockoffs in Linear Time

Author

Quentin Rebjock, Armin Askari, Laurent El Ghaoui, Alexandre d'Aspremont, University of California [Berkeley], University of California, Ecole Polytechnique Fédérale de Lausanne (EPFL), Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL), AA would like to acknowledge support from theML and Optimisation joint research initiative with the fonds AXA pour la recherche and Kamet Ventures, a Google focused award, as well as funding by the French government under management of Agence Nationale de la Recherche as part of the'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute)., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), University of California [Berkeley] (UC Berkeley), University of California (UC), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
FOS: Computer and information sciences, False discovery rate, Computer Science - Machine Learning, convex optimization, Computer science, Machine Learning (stat.ML), Feature selection, 010103 numerical & computational mathematics, coordinate descent, 01 natural sciences, Machine Learning (cs.LG), Methodology (stat.ME), 010104 statistics & probability, symbols.namesake, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, 0101 mathematics, Coordinate descent, Time complexity, Statistics - Methodology, Semidefinite programming, Series (mathematics), [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], semidefinite programming, Convex optimization, symbols, false discovery rate, Algorithm, Gaussian network model
Abstract

We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems. Identifying the knockoff distribution requires solving a large scale semidefinite program for which we derive several efficient methods. One handles generic covariance matrices, has a complexity scaling as $O(p^3)$ where $p$ is the ambient dimension, while another assumes a rank $k$ factor model on the covariance matrix to reduce this complexity bound to $O(pk^2)$. We also derive efficient procedures to both estimate factor models and sample knockoff covariates with complexity linear in the dimension. We test our methods on problems with $p$ as large as $500,000$., Comment: For code see https://github.com/qrebjock/fanok

Published
2021

40. Differential Privacy at Risk: Bridging Randomness and Privacy Budget

Author

Stéphane Bressan, Ashish Dandekar, Debabrota Basu, Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Chalmers University of Technology [Göteborg], National University of Singapore (NUS), This work was supported by the National Research Foundation (NRF) Singapore under its Corporate Laboratory@University Scheme, National University of Singapore, and Singapore Telecommunications Ltd. This research was also funded in part by the BioQOP project of the French ANR (ANR-17-CE39-0006). We thank Pierre Senellart for his help in reviewing derivations of privacy at risk for the Laplace mechanism., ANR-17-CE39-0006,BioQOP,Optimisation des accès à des données de vidéo-surveillance sous contraintes de respect de la vie privée dans une architecture distribuée(2017), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris

Subjects
FOS: Computer and information sciences, Mathematical optimization, Computer Science - Machine Learning, Computer Science - Cryptography and Security, Data steward, Computer science, Calibration (statistics), G.3, cost model, Mathematics - Statistics Theory, Machine Learning (stat.ML), 02 engineering and technology, Statistics Theory (math.ST), Convexity, Compensation (engineering), Machine Learning (cs.LG), [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, 020204 information systems, differential privacy, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Differential privacy, Data Structures and Algorithms (cs.DS), Dfferential privacy, Randomness, General Environmental Science, Ethics, business.industry, Probabilistic logic, Information technology, QA75.5-76.95, BJ1-1725, Electronic computers. Computer science, laplace mechanism, General Earth and Planetary Sciences, ComputingMilieux_COMPUTERSANDSOCIETY, 020201 artificial intelligence & image processing, 65C20, business, Cryptography and Security (cs.CR)
Abstract

The calibration of noise for a privacy-preserving mechanism depends on the sensitivity of the query and the prescribed privacy level. A data steward must make the non-trivial choice of a privacy level that balances the requirements of users and the monetary constraints of the business entity. We analyse roles of the sources of randomness, namely the explicit randomness induced by the noise distribution and the implicit randomness induced by the data-generation distribution, that are involved in the design of a privacy-preserving mechanism. The finer analysis enables us to provide stronger privacy guarantees with quantifiable risks. Thus, we propose privacy at risk that is a probabilistic calibration of privacy-preserving mechanisms. We provide a composition theorem that leverages privacy at risk. We instantiate the probabilistic calibration for the Laplace mechanism by providing analytical results. We also propose a cost model that bridges the gap between the privacy level and the compensation budget estimated by a GDPR compliant business entity. The convexity of the proposed cost model leads to a unique fine-tuning of privacy level that minimises the compensation budget. We show its effectiveness by illustrating a realistic scenario that avoids overestimation of the compensation budget by using privacy at risk for the Laplace mechanism. We quantitatively show that composition using the cost optimal privacy at risk provides stronger privacy guarantee than the classical advanced composition., Comment: Presented in Workshop on Privacy Preserving AI (PPAI) at AAAI, 2020

Published
2021

41. Some Remarks on a Coupling Method for the Practical Computation of Homogenized Coefficients

Author

Claude Le Bris, Frédéric Legoll, Olga Gorynina, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), MATHematics for MatERIALS (MATHERIALS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Modélisation et expérimentation multi-échelle pour les solides hétérogènes (Multi-échelle), Laboratoire Navier (NAVIER UMR 8205), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel-École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), and École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)

Subjects
Coupling, Applied Mathematics, Computation, Elliptic pdes, 010103 numerical & computational mathematics, 01 natural sciences, Computational Mathematics, Optimization and Control (math.OC), FOS: Mathematics, Applied mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Granularity, 0101 mathematics, Mathematics - Optimization and Control, Mathematics
Abstract

International audience; We numerically investigate, and improve upon, a computational approach originally introduced in [Cottereau, IJNME 2013] which aims at evaluating the effective coefficient of a medium modelled by a highly oscillatory coefficient. This computational approach is based on a Arlequin type coupling. It combines the original fine-scale description of the medium (modelled by an oscillatory coefficient) with an effective description (modelled by a constant coefficient) and optimizes upon the coefficient of the effective medium to best fit the response of the actual heterogeneous medium using a purely homogeneous medium. We present here a mathematical formalization of the approach along with various improvements of the algorithms, in order to obtain a procedure as efficient as possible. Representative numerical results demonstrate the added value of our approach in comparison to the original approach.

Published
2021

42. Réduction de modèles pour les inéquations variationnelles

Author

Niakh, Idrissa, Ern, Alexandre, Ehrlacher, Virginie, Drouet, Guillaume, ElectRotechnique et MEcanique des Structures (EDF R&D ERMES), EDF R&D (EDF R&D), EDF (EDF)-EDF (EDF), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), Simulation for the Environment: Reliable and Efficient Numerical Algorithms (SERENA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), MATHematics for MatERIALS (MATHERIALS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, EDF Labs, and Université Polytechnique Hauts-de-France [UPHF]

Subjects
Méthode des éléments finis, Réduction de modèle, [SPI.MECA.STRU]Engineering Sciences [physics]/Mechanics [physics.med-ph]/Structural mechanics [physics.class-ph], Inéquations variationnelles, Méthode des bases réduites, Problème de contact, Condition inf sup
Abstract

International audience; Ce travail s’inscrit dans le contexte de la réduction de modèle pour les inéquations variationnelles. Plus précisément, nous étudions la stabilité du modèle réduit dans le cas d’une formulation duale où les bases primale et duale sont construites de manière décorrélée. Nous fournissons une stratégie pour enrichir la base primale en fonction de la base duale de sorte que le modèle réduit satisfasse une condition de stabilité inf-sup. Comme exemple d’application, nous considérons le problème de contact de Hertz sans frottement.

Published
2022

43. Wasserstein model reduction approach for parametrized flow problems in porous media

Author

Battisti, Beatrice, Blickhan, Tobias, Enchery, Guillaume, Ehrlacher, Virginie, Lombardi, Damiano, Mula, Olga, Modeling Enablers for Multi-PHysics and InteractionS (MEMPHIS), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Politecnico di Torino = Polytechnic of Turin (Polito), Technische Universität München = Technical University of Munich (TUM), IFP Energies nouvelles (IFPEN), École des Ponts ParisTech (ENPC), MATHematics for MatERIALS (MATHERIALS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, COmputational Mathematics for bio-MEDIcal Applications (COMMEDIA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Eindhoven University of Technology [Eindhoven] (TU/e), ANR-19-CE46-0002,COMODO,Systèmes de diffusion croisée sur des domaines en mouvement(2019), and ANR-18-CE46-0001,ADAPT,Méthodes tensorielles parallèles dynamiques et adaptatives(2018)

Subjects
[MATH]Mathematics [math]
Abstract

The aim of this work is to build a reduced-order model for parametrized porous media equations. The main challenge of this type of problems is that the Kolmogorov width of the solution manifold typically decays quite slowly and thus makes usual linear model-order reduction methods inappropriate. In this work, we investigate an adaptation of the methodology proposed in [15], based on the use of Wasserstein barycenters [1], to the case of non-conservative problems. Numerical examples in one-dimensional test cases illustrate the advantages and limitations of this approach and suggest further research directions that we intend to explore in the future.; Le but de ce travail est de construire un modèle réduit pour des problèmes d'écoulements en milieux poreux paramétrés. La difficulté principale de ce type de problèmes est que la distance de Kolmogorov de l'ensemble de solutions décroît lentement, rendant ainsi les méthodes de réduction de modèles linéaires usuelles inefficaces. Ici, nous proposons une adaptation de la méthodologie proposée dans [15], utilisant des barycentres de Wasserstein [1], au cas de problèmes non conservatifs. Des tests numériques en dimension 1 permettent d'illustrer les avantages et les limitations de cette approche et d'identifier des pistes de recherche que nous souhaiterons aborder dans un futur travail.

Published
2022

44. Deep learning-based schemes for singularly perturbed convection-diffusion problems

Author

Beguinet, Adrien, Ehrlacher, Virginie, Flenghi, Roberta, Fuente-Ruiz, Maria, Mula, Olga, Somacal, Agustin, Université Paris-Saclay, École des Ponts ParisTech (ENPC), MATHematics for MatERIALS (MATHERIALS), Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC)-École des Ponts ParisTech (ENPC)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Mathematical Risk Handling (MATHRISK), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-Inria de Paris, COmputational Mathematics for bio-MEDIcal Applications (COMMEDIA), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Eindhoven University of Technology [Eindhoven] (TU/e), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), This project was partly funded by the Emergence project grant of the Paris City Council 'Models and Measures'. Funding from I-Site FUTURE is also acknowledged., and European Project: 810367,EMC2(2019)

Subjects
FOS: Mathematics, Numerical Analysis (math.NA), Mathematics - Numerical Analysis, [MATH]Mathematics [math]
Abstract

Deep learning-based numerical schemes such as Physically Informed Neural Networks (PINNs) have recently emerged as an alternative to classical numerical schemes for solving Partial Differential Equations (PDEs). They are very appealing at first sight because implementing vanilla versions of PINNs based on strong residual forms is easy, and neural networks offer very high approximation capabilities. However, when the PDE solutions are low regular, an expert insight is required to build deep learning formulations that do not incur in variational crimes. Optimization solvers are also significantly challenged, and can potentially spoil the final quality of the approximated solution due to the convergence to bad local minima, and bad generalization capabilities. In this paper, we present an exhaustive numerical study of the merits and limitations of these schemes when solutions exhibit low-regularity, and compare performance with respect to more benign cases when solutions are very smooth. As a support for our study, we consider singularly perturbed convection-diffusion problems where the regularity of solutions typically degrades as certain multiscale parameters go to zero.

Published
2022

45. Leveraging Randomized Smoothing for Optimal Control of Nonsmooth Dynamical Systems

Author

Le Lidec, Quentin, Montaut, Louis, Schmid, Cordelia, Laptev, Ivan, Carpentier, Justin, Models of visual object recognition and scene understanding (WILLOW), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Czech Institute of Informatics, Robotics and Cybernetics [Prague] (CIIRC), Czech Technical University in Prague (CTU), This work was supported in part by L'Agence d'Innovation Défense, the HPC resources from GENCI-IDRIS(Grant AD011012215), the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d'avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute), the European Regional Development Fund under the project IMPACT (reg. no. CZ.02.1.01/0.0/0.0/15 003/0000468), the Grant Agency of the Czech Technical University in Prague, grant No. SGS21/178/OHK3/3T/17, and Louis Vuitton ENS Chair on Artificial Intelligence., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)

Subjects
FOS: Computer and information sciences, Computer Science - Robotics, Optimization and Control (math.OC), FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Robotics (cs.RO), Mathematics - Optimization and Control
Abstract

Optimal Control (OC) algorithms such as Differential Dynamic Programming (DDP) take advantage of the derivatives of the dynamics to efficiently control physical systems. Yet, in the presence of nonsmooth dynamical systems, such class of algorithms are likely to fail due, for instance, to the presence of discontinuities in the dynamics derivatives or because of non-informative gradient during the solving. On the contrary, Reinforcement Learning (RL) algorithms have shown better empirical results in scenarios exhibiting nonsmooth effects (contacts, frictions, etc). Our approach leverages recent works on Randomized Smoothing (RS) to tackle nonsmoothness issues commonly encountered in Optimal Control, and provides key insights on the interplay between RL and OC through the prism of RS methods. This naturally leads us to introduce the Randomized Differential Dynamic Programming (R-DDP) algorithm accounting for deterministic but non-smooth dynamics in a very sample-efficient way. The experiments demonstrate that our method is able to solve classic robotic problems with dry friction and frictional contacts, where classical OC algorithms are likely to fail and RL algorithms require in practice a prohibitive number of samples to find an optimal solution.

Published
2022

46. Are discrete units necessary for Spoken Language Modeling?

Author

Tu Anh Nguyen, Benoit Sagot, Emmanuel Dupoux, Meta AI, Automatic Language Modelling and ANAlysis & Computational Humanities (ALMAnaCH), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Apprentissage machine et développement cognitif (CoML), Laboratoire de sciences cognitives et psycholinguistique (LSCP), Département d'Etudes Cognitives - ENS Paris (DEC), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Département d'Etudes Cognitives - ENS Paris (DEC), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École des hautes études en sciences sociales (EHESS), Université Paris sciences et lettres (PSL), Grant from CIFAR (Learning in Machines and Brains) and HPC resources from GENCI–IDRIS (Grant 2021-AD011011691R1), ANR-17-EURE-0017,FrontCog,Frontières en cognition(2017), ANR-10-IDEX-0001,PSL,Paris Sciences et Lettres(2010), and ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Computer Science - Computation and Language, Signal Processing, Discrete Units, [SCCO.COMP]Cognitive science/Computer science, Electrical and Electronic Engineering, Spoken Language Modeling, [SCCO.LING]Cognitive science/Linguistics, Computation and Language (cs.CL), HuBERT, Machine Learning (cs.LG)
Abstract

International audience; Recent work in spoken language modeling shows the possibility of learning a language unsupervisedly from raw audio without any text labels. The approach relies first on transforming the audio into a sequence of discrete units (or pseudo-text) and then training a language model directly on such pseudo-text. Is such a discrete bottleneck necessary, potentially introducing irreversible errors in the encoding of the speech signal, or could we learn a language model without discrete units at all? In this work, we study the role of discrete versus continuous representations in spoken language modeling. We show that discretization is indeed essential for good results in spoken language modeling. We show that discretization removes linguistically irrelevant information from the continuous features, helping to improve language modeling performances. On the basis of this study, we train a language model on the discrete units of the HuBERT features, reaching new state-of-the-art results in the lexical, syntactic and semantic metrics of the Zero Resource Speech Challenge 2021 (Track 1-Speech Only).

Published
2022

47. Using single-cell models to predict the functionality of synthetic circuits at the population scale

Author

Chetan Aditya, Jakob Ruess, François Bertaux, Gregory Batt, InBio - Méthodes Expérimentales et Computationnelles pour la Modélisation des Processus Cellulaires / Experimental and Computational Methods for Modeling Cellular Processes, Institut Pasteur [Paris]-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris Cité (UPC), This work was supported by the H2020 Fet-Open COSYBIO grant (grant agreement no. 766840) and by the ANR grant CyberCircuits (ANR-18-CE91-0002)., ANR-18-CE91-0002,CyberCircuits,Circuits cybergénétiques pour tester la composabilité des réseaux génétiques(2018), European Project: 766840,H2020,COSY-BIO(2017), InBio - Méthodes Expérimentales et Computationnelles pour la Modélisation des Processus Cellulaires / Experimental and Computational Methods for Modeling Cellular Processes (INBIO), Institut Pasteur [Paris] (IP)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris Cité (UPCité)

Subjects
Model theory, Population dynamics, Computer science, [SDV]Life Sciences [q-bio], Population, Model parameters, Saccharomyces cerevisiae, 03 medical and health sciences, 0302 clinical medicine, Synthetic differentiation circuits, Composability, Gene Regulatory Networks, education, 030304 developmental biology, Electronic circuit, Stochastic Processes, 0303 health sciences, education.field_of_study, Multidisciplinary, Scale (chemistry), System dynamics, Optogenetics, Biological Variation, Population, Synthetic Biology, Biochemical engineering, Chemical master equation, Single-Cell Analysis, 030217 neurology & neurosurgery
Abstract

Posté sur BioRxiv le 4 août 2021; International audience; Mathematical modeling has become a major tool to guide the characterization and synthetic construction of cellular processes. However, models typically lose their capacity to explain or predict experimental outcomes as soon as any, even minor, modification of the studied system or its operating conditions is implemented. This limits our capacity to fully comprehend the functioning of natural biological processes and is a major roadblock for the de novo design of complex synthetic circuits. A common cause of this problem is that cell-to-cell variability creates couplings between single-cell circuits and population processes such as selection or growth. Altering the circuit may then have unforeseen consequences inside growing populations. Here we construct a yeast optogenetic differentiation system that exploits cell-to-cell variability to enable external control of the population composition. We show that a simple deterministic model can explain the dynamics of the core system. However, modifying the context of the circuit by expressing system components from plasmids leads to failure of model predictions. Subsequently, we deploy theory from stochastic chemical kinetics to construct models of the system’s components that simultaneously track single-cell and population processes and demonstrate that this allows us to quantitatively predict emerging dynamics of the plasmid-based system without any adjustment of model parameters. We conclude that carefully characterizing the dynamics of cell-to-cell variability using appropriate modeling theory may allow one to unravel the complex interplay of stochastic single-cell and population processes and to predict the functionality of complex synthetic circuits in growing populations before the circuit is constructed.

Published
2022

48. Mass concentration in rescaled first order integral functionals

Author

Monteil, Antonin, Pegon, Paul, Laboratoire Analyse et Mathématiques Appliquées (LAMA), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), A. M. acknowledges support by Leverhulme grant RPG-2018-438., Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Pegon, Paul

Subjects
Relaxation, H-mass, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], semicontinuity, [MATH] Mathematics [math], convergence of measures, Functionals on measures, Mathematics - Analysis of PDEs, integral functionals, branched transport, Primary: 28A33, 49J45, 46E35, Secondary: 49Q20, 76T99, 49Q22, 49J10, Γ-convergence, Optimization and Control (math.OC), FOS: Mathematics, concentration-compactness, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AP] Mathematics [math]/Analysis of PDEs [math.AP], [MATH]Mathematics [math], Mathematics - Optimization and Control, Cahn-Hilliard fluids, Analysis of PDEs (math.AP), Calculus of variations
Abstract

We consider first order local minimization problems of the form $\min \int_{\mathbb{R}^N}f(u,\nabla u)$ under a mass constraint $\int_{\mathbb{R}^N}u=m\in\mathbb{R}$. We prove that the minimal energy function $H(m)$ is always concave on $(-\infty,0)$ and $(0,+\infty)$, and that relevant rescalings of the energy, depending on a small parameter $\varepsilon$, $\Gamma$-converge in the weak topology of measures towards the $H$-mass, defined for atomic measures $\sum_i m_i\delta_{x_i}$ as $\sum_i H(m_i)$. We also consider space dependent Lagrangians $f(x,u,\nabla u)$, which cover the case of space dependent $H$-masses $\sum_i H(x_i,m_i)$, and also the case of a family of Lagrangians $(f_\varepsilon)_\varepsilon$ converging as $\varepsilon\to 0$. The $\Gamma$-convergence result holds under mild assumptions on $f$, and covers several situations including homogeneous \(H\)-masses in any dimension $N\geq 2$ for exponents above a critical threshold, and all concave $H$-masses in dimension $N=1$. Our result yields in particular the concentration of Cahn-Hilliard fluids into droplets, and is related to the approximation of branched transport by elliptic energies.

Published
2022

49. Temporal exponential random graph models of longitudinal brain networks after stroke

Author

Obando, Catalina, Rosso, Charlotte, Siegel, Joshua, Corbetta, Maurizio, De Vico Fallani, Fabrizio, Institut du Cerveau et de la Moëlle Epinière = Brain and Spine Institute (ICM), Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Service d'Urgences Cérébro-Vasculaires [CHU Pitié-Salpêtrière], CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP), Accidents vasculaires cérébraux [ICM Paris] (iCRIN AVC), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Washington University in Saint Louis (WUSTL), University of Padova Medical School, Venetian Institute Molecular Medicine (VIMM), The research leading to these results has received funding from the program 'Investissements d’avenir' ANR-10-IAIHU-06 (Agence Nationale de la Recherche-10-IA Institut Hospitalo-Universitaire-6). FD acknowledges support from the 'Agence Nationale de la Recherche' through contract number ANR-15-NEUC-0006-02. MC acknowledges support from the 'National Institute of Health' through contracts number R01-HD06117 and R01-NS095741. The content is solely the responsibility of the authors and does not necessarily represent the official views of any of the funding agencies., Institut du Cerveau = Paris Brain Institute (ICM), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Sorbonne Université (SU)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Algorithms, models and methods for images and signals of the human brain (ARAMIS), Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut du Cerveau = Paris Brain Institute (ICM), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Sorbonne Université (SU)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut du Cerveau et de la Moëlle Epinière = Brain and Spine Institute (ICM), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de la Santé et de la Recherche Médicale (INSERM)-CHU Pitié-Salpêtrière [AP-HP], Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU), Università degli Studi di Padova = University of Padua (Unipd), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut du Cerveau et de la Moëlle Epinière = Brain and Spine Institute (ICM), and Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Assistance publique - Hôpitaux de Paris (AP-HP) (AP-HP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Brain Mapping, network models, functional connectivity, functional magnetic resonance imaging, stroke, Biomedical Engineering, Biophysics, Brain, Bioengineering, Life Sciences–Physics interface, Biochemistry, Magnetic Resonance Imaging, Biomaterials, Stroke, Humans, [SDV.IB]Life Sciences [q-bio]/Bioengineering, Nerve Net, Biotechnology, Language
Abstract

Plasticity after stroke is a complex phenomenon. Functional reorganization occurs not only in the perilesional tissue but throughout the brain. However, the local connection mechanisms generating such global network changes remain largely unknown. To address this question, time must be considered as a formal variable of the problem rather than a simple repeated observation. Here, we hypothesized that the presence of temporal connection motifs, such as the formation of temporal triangles (T) and edges (E) over time, would explain large-scale brain reorganization after stroke. To test our hypothesis, we adopted a statistical framework based on temporal exponential random graph models (tERGMs), where the aforementioned temporal motifs were implemented as parameters and adapted to capture global network changes after stroke. We first validated the performance on synthetic time-varying networks as compared to standard static approaches. Then, using real functional brain networks, we showed that estimates of tERGM parameters were sufficient to reproduce brain network changes from 2 weeks to 1 year after stroke. These temporal connection signatures, reflecting within-hemisphere segregation (T) and between hemisphere integration (E), were associated with patients' future behaviour. In particular, interhemispheric temporal edges significantly correlated with the chronic language and visual outcome in subcortical and cortical stroke, respectively. Our results indicate the importance of time-varying connection properties when modelling dynamic complex systems and provide fresh insights into modelling of brain network mechanisms after stroke.

Published
2022

50. Restarting Frank-Wolfe

Author

Kerdreux, Thomas, D'Aspremont, Alexandre, Pokutta, Sebastian, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'école normale supérieure (LIENS), Centre National de la Recherche Scientifique (CNRS), School of Industrial and Systems Engineering [Georgia Tech] (ISyE), Georgia Institute of Technology [Atlanta], ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris

Subjects
[STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; Conditional Gradients (aka Frank-Wolfe algorithms) form a classical set of methods for constrained smooth convex minimization due to their simplicity, the absence of projection step, and competitive numerical performance. While the vanilla Frank-Wolfe algorithm only ensures a worst-case rate of O(1/epsilon), various recent results have shown that for strongly convex functions, the method can be slightly modified to achieve linear convergence. However, this still leaves a huge gap between sublinear O(1/epsilon) convergence and linear O(log(1/epsilon)) convergence to reach an $\epsilon$-approximate solution. Here, we present a new variant of Conditional Gradients, that can dynamically adapt to the function's geometric properties using restarts and thus smoothly interpolates between the sublinear and linear regimes.

Published
2022

Catalog

Books, media, physical & digital resources
See catalog results