INRIA a CCSD electronic archive server
Not a member yet
122212 research outputs found
Sort by
Traffic prediction by combining macroscopic models and Gaussian processes
No full textInternational audienceWe propose a physics informed statistical framework for traffic travel time prediction. On one side, the discrepancy of the considered mathematical model is represented by a Gaussian process. On the other side, the traffic simulator is fed with boundary data predicted by a Gaussian process, forced to satisfy the mathematical equations at virtual points, resulting in a multi-objective optimization problem. This combined approach has the merit to address the shortcomings of the purely model-driven or data-driven approaches, while leveraging their respective advantages. Indeed, models are based on physical laws, but cannot capture all the complexity of real phenomena. On the other hand, pure statistical outputs can violate basic characteristic dynamics. We validate our approach on both synthetic and real world data, showing that it delivers more reliable results compared to other methods.“This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.
Algorithmes de Newton-min polyédriques pour les problèmes de complémentarité
No full textInternational audienceThe semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a "negative kink" of the minimum function and acts accordingly.In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global and fast convergence to regular solutions is proved. Promising numerical experiments on a few linear complementarity problems are reported, using an implementation of the hybrid algorithm in Matlab.L'algorithme de Newton semi-lisse est très efficace pour calculer un zéro d'une large classe d'équations non lisses. Lorsque le premier itéré est suffisamment proche d'un zéro régulier et si la fonction est fortement semi-lisse, la suite générée converge quadratiquement vers ce zéro, alors que l'itération ne requière que la résolution d'un système linéaire.Cependant, si le premier itéré est éloigné d'un zéro, il est difficile de forcer sa convergence par recherche linéaire ou régions de confiance, parce que la direction de Newton semi-lisse n'est pas nécessairement une direction de descente de la fonction de moindres-carrés associée, contrairement au cas où la fonction à annuler est différentiable. Nous explorons cette question dans le cas particulier d'une reformulation par équation non lisse du problème de complémentarité non linéaire, en utilisant la fonction minimum. Nous proposons un algorithme globalement convergent, utilisant une direction de Newton semi-lisse modifiée, qui est de descente pour la fonction de moindres-carrés. Au lieu de requérir la satisfaction d'un système linéaire, cette direction doit appartenir à un polyèdre convexe, ce qui peut se calculer en temps polynomial. Ce polyèdre est défini par souvent très peu d'inégalités, obtenues en linéarisant des couples de fonctions qui ont des valeurs négatives proches à l'itéré courant; donc, d'une certaine manière, l'algorithme est capable d'estimer la proximité des "plis négatifs" de la fonction minimum et d'agir en conséquence.De manière à éviter aussi souvent que possible le coût supplémentaire lié au calcul d'un point admissible de polyèdre, un algorithme hybride est également proposé, dans lequel la direction de Newton-min est acceptée si un critère de décroissance suffisante est vérifié, ce qui est souvent le cas en pratique. La convergence globale et rapide vers des solutions régulières est démontrée. Des tests numériques sur quelques problèmes de complémentarité linéaire sont décrits; ceux-ci utilisent une implémentation en Matlab de l'algorithme de Newton-min hybride
Dependent Coeffects for Local Sensitivity Analysis
No full textTo appearInternational audienceDifferential privacy is a formal definition of privacy that bounds the maximum acceptable information leakage when a query is performed on sensitive data. To ensure this property, a key technique involves bounding the query's sensitivity (how much input variations affect the output) and adding noise to the result proportional to this quantity. While prior work like the Fuzz type system focuses on global sensitivity, many useful queries have infinite global sensitivity, restricting the applicability of such approaches. This limitation can be addressed by considering a more fine-grained measure: local sensitivity, which quantifies output change for inputs adjacent to a specific dataset. In this article, we introduce Local Fuzz, a type system with dependent coeffects designed to bound the local sensitivity of programs written in a simple functional language. We provide a denotational semantics for this system in the category of extended premetric spaces, leveraging the recently introduced construction of a dependently graded comonad. Finally, we illustrate how Local Fuzz can lead to better differential privacy guarantees than Fuzz, both for mechanisms that rely on global sensitivity and for those that leverage local sensitivity, such as the Propose-Test-Release framework
Beyond Log Scales: Toward Cognitively Informed Bar Charts for Orders of Magnitude Values
No full textInternational audienceIn this work, we challenge the dominant use of logarithmic scales to communicate values spanning multiple orders of magnitude—Orders of Magnitude Values (OMVs)—to the general public. Focusing on bar charts, we incorporate cognitive insights into visualization design to better align with how humans perceive OMVs. Studies in cognitive psychology suggest that, for large numerical ranges such as millions and billions, people do not think logarithmically. Instead, they perceive numbers in a piecewise linear manner, grouping values into scale words (e.g., millions) and applying linear reasoning within each group. We build upon a recently introduced piecewise linear scale, EplusM, and validate its use in bar charts, which we refer to as EplusM bar charts. We also introduce two novel variants of the EplusM bar chart informed by findings in numerical perception: Bricks, which builds on the concepts of round numbers and subitizing, and Multi-Magnitude, which leverages categorical perception of large numbers. In a crowdsourced experiment, we evaluate four bar chart designs: 1) Log, 2) EplusM, 3) Bricks, and 4) Multi-Magnitude, across value retrieval and quantitative comparison tasks. Our results show that EplusM bar charts are significantly preferred over logarithmic designs, increase user confidence, and reduce perceived mental demand, while maintaining task performance. These findings suggest that EplusM bar charts can serve as effective alternatives to logarithmic ones when visualizing OMVs for general audiences
A graph discretization of vector Laplacian
No full textInternational audienceAs known, the scalar Laplacian gives the celebrated Laplacian matrix of a graph. In this paper, we determine the graph matrix presentation of vector Laplacian (or Helmholtz operator), named as Helmholtzian matrix. To compare the difference and similarity with previous graph matrices, we study the limit points of spectral radius and characterize the connected graphs with spectral radius at most 4.38+ via Helmholtzian matrix. Finally, we discuss the potential applications of Helmholtzian spectra of graphs in the simplicial networks and small-world networks
An asymptotic rigidity property from the realizability of chirotope extensions
No full textLet be a finite full-dimensional point configuration in . We show that if a point configuration has the property that all finite chirotopes realizable by adding (generic) points to are also realizable by adding points to , then and are equal up to a direct affine transform. We also show that for any point configuration and any \varepsilon>0, there is a finite, (generic) extension of with the following property: if another realization of the chirotope of can be extended so as to realize the chirotope of , then there exists a direct affine transform that maps each point of within distance of the corresponding point of
A Minrank-based Encryption Scheme à la Alekhnovich-Regev
No full textInternational audienceIntroduced in 2003 and 2005, Alekhnovich and Regev' schemes were the first public-key encryptions whose security is only based on the average hardness of decoding random linear codes and LWE, without other security assumptions. Such security guarantees made them very popular, being at the origin of the now standardized HQC or Kyber. We present an adaptation of Alekhnovich and Regev' encryption scheme whose security is only based on the hardness of a slight variation of MinRank, the so-called stationary-MinRank problem. We succeeded to reach this strong security guarantee by showing that stationary-MinRank benefits from a search-to-decision reduction. Our scheme therefore brings a partial answer to the long-standing open question of building an encryption scheme whose security relies solely on the hardness of MinRank. Finally, we show after a thoroughly security analysis that our scheme is practical and competitive with other encryption schemes admitting such strong security guarantees. Our scheme is slightly less efficient than FrodoKEM, but much more efficient than Alekhnovich and Regev' original schemes, with possibilities of improvements by considering more structure, in the same way as HQC and Kyber
Definitional Proof Irrelevance Made Accessible
No full textA universe of propositions equipped with definitional proof irrelevance constitutes a convenient medium to express properties and proofs in type-theoretic proof assistants such as Lean, Rocq, and Agda. However, allowing accessibility predicates---used to establish semantic termination arguments---to inhabit such a universe yields undecidable typechecking, hampering the predictability and foundational bases of a proof assistant. To effectively reconcile definitional proof irrelevance and accessibility predicates with both theoretical foundations and practicality in mind, we describe a type theory that extends the Calculus of Inductive Constructions featuring observational equality in a universe of strict propositions, and two variants for handling the elimination principle of accessibility predicates: one variant safeguards decidability by sticking to propositional unfolding, and the other variant favors flexibility with definitional unfolding, at the expense of a potentially diverging typechecking procedure. Crucially, the metatheory of this dual approach establishes that any proof term constructed in the definitional variant of the theory can be soundly embedded into the propositional variant, while preserving the decidability of the latter. Moreover, we prove the two variants to be consistent and to satisfy forms of canonicity, ensuring that programs can indeed be properly evaluated. We present an implementation in Rocq and compare it with existing approaches. Overall, this work introduces an effective technique that informs the design of proof assistants with strict propositions, enabling local computation with accessibility predicates without compromising the ambient type theory
Feller Property and Absorption of Diffusions for Multi-Species Metacommunities
No full textWe consider individuals of two species distributed over m patches, each with a hosting capacity , where . We assume that all the patches are linked by the dispersal of individuals. This work examines how the metacommunity evolves in these patches. The model incorporates Wright-Fisher intra-patch reproduction and a general exchange function representing dispersal. Under minimal assumptions, we demonstrate that as approaches infinity, the processes converge to a diffusion process for which we establish the Feller property. We prove that the limiting process almost surely reaches the absorbing states in finite time.</div
Force-velocity coupling limits human adaptation in physical human–robot interaction
No full textInternational audienceIn physical human–robot interaction, both humans and robots need to adapt to ensure synergetic behavior. This study investigated how humans respond to robots moving with different velocity profiles. In unconstrained human movements, velocity scales with the trajectory’s curvature, i.e., moving fast at linear segments while slowing down at curved segments. Two experiments examined humans tracking a robot that traced an elliptic path with different velocity profiles, while instructed to minimize interaction forces. Results showed involuntary forces were higher when the robot moved with constant velocity or exaggerated the biological velocity-curvature scaling. Specifically, higher angular velocities in the robot were associated with greater tangential and normal forces. Experiment 1 tested whether biomechanical constraints caused these forces by reversing movement direction, but observed differences were small. Experiment 2 explored human adaptation across three practice sessions and found that interaction forces decreased for non-biological profiles only when real-time visual feedback was provided. The force-velocity modulations weakened, indicating that humans learned to predict and compensate for inertial forces. These findings highlight the need to consider human motor limitations and learning processes in physical interaction. The results have practical implications for collaborative and wearable robots where physical contact and coordination between humans and robots are critical