INRIA a CCSD electronic archive server
Not a member yet
122212 research outputs found
Sort by
Unsupervised anomaly detection in brain FDG PET with deep generative models: An experimental analysis of model variability and mitigation strategies
No full textInternational audienceUnsupervised anomaly detection allows identifying anomalies from unlabeled data, making it useful for neuroimaging analysis and computer-aided diagnosis. Given an individual's scan, we use a generative model to construct a subject-specific image of healthy appearance and compare both images to spot anomalies. Designing anomaly maps in such way has drawbacks as the reconstructions are imperfect and some variability is not taken into account. We study model variability arising from using different random seeds during training and explore solutions to mitigate the effect of unwanted reconstruction errors and variability. Our experiments on 3D brain FDG PET scans from ADNI suggest that variance between models can be reduced by aggregating their reconstructions in a Z-score based anomaly map, or normalizing the anomaly map with a healthy validation set
Components Operationally: Reversibility and System Engineering: Essays Dedicated to Jean-Bernard Stefani on the Occasion of His 65th Birthday
No full textInternational audienc
Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
No full textInternational audienceA fundamental problem in shape matching and geometric similarity is computing the maximum area overlap between two polygons under translation. For general simple polygons, the best-known algorithm runs in time [Mount, Silverman, Wu 96], where and are the complexities of the input polygons. In a recent breakthrough, Chan and Hair gave a linear-time algorithm for the special case when both polygons are convex. A key challenge in computational geometry is to design improved algorithms for other natural classes of polygons. We address this by presenting an -time algorithm for the case when both polygons are orthogonal. This is the first algorithm for polygon overlap on orthogonal polygons that is faster than the almost 30 years old algorithm for simple polygons. Complementing our algorithmic contribution, we provide -SUM lower bounds for problems on simple polygons with only orthogonal and diagonal edges. First, we establish that there is no algorithm for polygon overlap with running time , where , unless the -SUM hypothesis fails. This matches the running time of our algorithm when . We use part of the above construction to also show a lower bound for the polygon containment problem, a popular special case of the overlap problem. Concretely, there is no algorithm for polygon containment with running time under the -SUM hypothesis, even when the polygon to be contained has vertices. Our lower bound shows that polygon containment for these types of polygons (i.e., with diagonal edges) is strictly harder than for orthogonal polygons, and also strengthens the previously known lower bounds for polygon containment. Furthermore, our lower bounds show tightness of the algorithm of [Mount, Silverman, Wu 96] when
Correctly rounded evaluation of a function: why, how, and at what cost?
No full textThe two accompanying files are: - The SageMath code computing upper bounds for the hardness to round of exp, trigonometric and hyperbolic functions over the firstfew binades surrounding 1;- the LACoR library that implements the BH algorithm for computing upper bounds on the hardness to roundInternational audienceThe goal of this article is to give a survey on the various computational and mathematical issues and progress related to the problem of providing efficient correctly rounded elementary functions in floating-point arithmetic. We also aim at convincing the reader that a future standard for floating-point arithmetic should require the availability of a correctly rounded version of a well-chosen core set of elementary functions. We discuss the interest and feasibility of this requirement
Empirical Risk Minimization with f -Divergence Regularization
No full textIn this paper, the solution to the empirical risk minimization problem with f-divergence regularization (ERM-f DR) is presented and conditions under which the solution also serves as the solution to the minimization of the expected empirical risk subject to an f -divergence constraint are established. The proposed approach extends applicability to a broader class of f -divergences than previously reported and yields theoretical results that recover previously known results. Additionally, the difference between the expected empirical risk of the ERMf DR solution and that of its reference measure is characterized, providing insights into previously studied cases of f -divergences. A central contribution is the introduction of the normalization function, a mathematical object that is critical in both the dual formulation and practical computation of the ERM-f DR solution. This work presents an implicit characterization of the normalization function as a nonlinear ordinary differential equation (ODE), establishes its key properties, and subsequently leverages them to construct a numerical algorithm for approximating the normalization factor under mild assumptions. Further analysis demonstrates structural equivalences between ERM-f DR problems with different f -divergences via transformations of the empirical risk. Finally, the proposed algorithm is used to compute the training and test risks of ERM-f DR solutions under different f -divergence regularizers. This numerical example highlights the practical implications of choosing different functions f in ERMf DR problems
QoverC: A Profiler of Quantum Computer Simulators for Quantum Optimisation
No full textInternational audienceQuantum computers are still infrequent and expensive. They have a great potential for research and industry, but they are noisy, limited, and not always easy to access. All this is preventing rapid and widespread access to the whole potential of this field. To overcome this bottleneck and foster advances in quantum computing, a large plethora of Quantum Computer Simulators (QCS) have emerged, allowing quantum studies on classical machines, and ultimately on quantum devices as well. In addition to being numerous, these simulators differ from each other in an overwhelming number of aspects, which hardens any attempt to categorise/profile them: making a choice is really difficult for a researcher. This work presents a systematic literature review and a public web repository QoverC of the existing QCS for quantum computation in general, and the leading ones for optimisation in particular. To the best of the authors' knowledge, this is the largest QCS study to date, where we include 199 web, desktop, and hybrid simulators, over 22 programming languages. We also provide a comprehensive comparison spanning over 10 metrics. We aim to bring structure to this domain, foster quantum computing, study their particular features, and ease their use and research in the future
Revisiting Lower Bounds for Two-Step Consensus
No full textA seminal result by Lamport shows that at least processes are required to implement partially synchronous consensus that tolerates process failures and can furthermore decide in two message delays under failures. This lower bound is matched by the classical Fast Paxos protocol. However, more recent practical protocols, such as Egalitarian Paxos, provide two-step decisions with fewer processes, seemingly contradicting the lower bound. We show that this discrepancy arises because the classical bound requires two-step decisions under a wide range of scenarios, not all of which are relevant in practice. We propose a more pragmatic condition for which we establish tight bounds on the number of processes required. Interestingly, these bounds depend on whether consensus is implemented as an atomic object or a decision task. For consensus as an object, processes are necessary and sufficient for two-step decisions, while for a task the tight bound is
Making Democracy Work: Fixing and Simplifying Egalitarian Paxos (Extended Version)
No full textClassical state-machine replication protocols, such as Paxos, rely on a distinguished leader process to order commands. Unfortunately, this approach makes the leader a single point of failure and increases the latency for clients that are not co-located with it. As a response to these drawbacks, Egalitarian Paxos introduced an alternative, leaderless approach, that allows replicas to order commands collaboratively. Not relying on a single leader allows the protocol to maintain non-zero throughput with up to crashes of any processes out of a total of . The protocol furthermore allows any process to execute a command fast, in message delays, provided no more than other processes fail, and all concurrently submitted commands commute with ; the latter condition is often satisfied in practical systems. Egalitarian Paxos has served as a foundation for many other replication protocols. But unfortunately, the protocol is very complex, ambiguously specified and suffers from nontrivial bugs. In this paper, we present EPaxos* -- a simpler and correct variant of Egalitarian Paxos. Our key technical contribution is a simpler failure-recovery algorithm, which we have rigorously proved correct. Our protocol also generalizes Egalitarian Paxos to cover the whole spectrum of failure thresholds and such that -- the number of processes that we show to be optimal
Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics
No full textDiffusion models for continuous state spaces based on Gaussian noising processes are now relatively well understood, as many works have focused on their theoretical analysis. In contrast, results for diffusion models on discrete state spaces remain limited and pose significant challenges, particularly due to their combinatorial structure and their more recent introduction in generative modelling. In this work, we establish new and sharp convergence guarantees for three popular discrete diffusion models (DDMs). Two of these models are designed for finite state spaces and are based respectively on the random walk and the masking process. The third DDM we consider is defined on the countably infinite space and uses a drifted random walk as its forward process. For each of these models, the backward process can be characterized by a discrete score function that can, in principle, be estimated. However, even with perfect access to these scores, simulating the exact backward process is infeasible, and one must rely on approximations. In this work, we study Euler-type approximations and establish convergence bounds in both Kullback-Leibler divergence and total variation distance for the resulting models, under minimal assumptions on the data distribution. In particular, we show that the computational complexity of each method scales linearly in the dimension, up to logarithmic factors. Furthermore, to the best of our knowledge, this study provides the first non-asymptotic convergence guarantees for these noising processes that do not rely on boundedness assumptions on the estimated score
Stabilization of a Wave-Heat Cascade System
No full textWe consider the output-feedback stabilization of a one-dimensional cascade coupling a reaction-diffusion equation and a wave equation through an internal term, with Neumann boundary control acting at the wave endpoint. Two measurements are available: the wave velocity at the controlled boundary and a temperature-type observation of the reaction-diffusion component, either distributed or pointwise. Under explicit, necessary and sufficient conditions on the coupling and observation profiles, we show that the generator of the open-loop system is a Riesz-spectral operator. Exploiting this structure, we design a finite-dimensional dynamic output-feedback law, based on a finite number of parabolic modes, which achieves arbitrary exponential decay in both the natural energy space and a stronger parabolic norm. The construction relies on a spectral reduction and a Lyapunov argument in Riesz bases. We also extend the design to pointwise temperature or heat-flux measurements