Publications associées à Majorant ou minorant

Improving SAM Requires Rethinking its Optimization Formulation

Volkan Cevher, Kimon Antonakopoulos, Thomas Michaelsen Pethick, Wanyun Xie, Fabian Ricardo Latorre Gomez

This paper rethinks Sharpness-Aware Minimization (SAM), which is originally formulated as a zero-sum game where the weights of a network and a bounded perturbation try to minimize/maximize, respectively, the same differentiable loss. We argue that SAM shou ...

2024

On the number of regions of piecewise linear neural networks

Michaël Unser, Alexis Marie Frederic Goujon

Many feedforward neural networks (NNs) generate continuous and piecewise-linear (CPWL) mappings. Specifically, they partition the input domain into regions on which the mapping is affine. The number of these so-called linear regions offers a natural metric ...

2024

Peak Value-at-Risk Estimation for Stochastic Differential Equations using Occupation Measures

Matteo Raphael Tacchi

This paper proposes an algorithm to upper-bound maximal quantile statistics of a state function over the course of a Stochastic Differential Equation (SDE) system execution. This chance-peak problem is posed as a nonconvex program aiming to maximize the Va ...

IEEE2023

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Maryam Kamgarpour, Tony Alan Wood

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

2023

The first Grushin eigenvalue on cartesian product domains

Joachim Stubbe, Luigi Provenzano, Paolo Luzzini

In this paper, we consider the first eigenvalue.1(O) of the Grushin operator.G :=.x1 + |x1|2s.x2 with Dirichlet boundary conditions on a bounded domain O of Rd = R d1+ d2. We prove that.1(O) admits a unique minimizer in the class of domains with prescribed ...

WALTER DE GRUYTER GMBH2023

Chung-type law of the iterated logarithm and exact moduli of continuity for a class of anisotropic Gaussian random fields

Cheuk Yin Lee

We establish a Chung-type law of the iterated logarithm and the exact local and uniform moduli of continuity for a large class of anisotropic Gaussian random fields with a harmonizable-type integral representation and the property of strong local nondeterm ...

INT STATISTICAL INST2023

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game. ...

Siam Publications2023

Upper bounds on technoemission rates from 60 years of "silence"

Claudio Grimaldi

The lack of detection to date of electromagnetic technosignatures implies either that we have been unable to detect them due to incomplete sampling of the search space or that we cannot detect them because the Earth has been located during the entire histo ...

PERGAMON-ELSEVIER SCIENCE LTD2023

Intrinsic area near the origin for self-similar growth-fragmentations and related random surfaces

François Gaston Ged

We study the behaviour of a natural measure defined on the leaves of the genealogical tree of some branching processes, namely self-similar growth-fragmentation processes. Each particle, or cell, is attributed a positive mass that evolves in continuous tim ...

2022

Lower-bounds on the Bayesian Risk in Estimation Procedures via f–Divergences

Michael Christoph Gastpar, Amedeo Roberto Esposito, Adrien Vandenbroucque

We consider the problem of parameter estimation in a Bayesian setting and propose a general lower-bound that includes part of the family of f-Divergences. The results are then applied to specific settings of interest and compared to other notable results i ...

2022

Differential Entropy of the Conditional Expectation Under Additive Gaussian Noise

Michael Christoph Gastpar, Alper Köse, Ahmet Arda Atalik

The conditional mean is a fundamental and important quantity whose applications include the theories of estimation and rate-distortion. It is also notoriously difficult to work with. This paper establishes novel bounds on the differential entropy of the co ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

A Functional Perspective on Information Measures

Amedeo Roberto Esposito

Since the birth of Information Theory, researchers have defined and exploited various information measures, as well as endowed them with operational meanings. Some were born as a "solution to a problem", like Shannon's Entropy and Mutual Information. Other ...

EPFL2022

IR side of positivity bounds

Francesco Riva, Marc Riembau Saperas, Brando Bellazzini

We show how calculable IR loop effects impact positivity bounds in effective field theories with causal and unitary UV completions. We identify infrared singularities that appear in dispersion relations at |t| less than or similar to m(2). In the massless ...

American Physical Society2022

The completeness of the generalized eigenfunctions and an upper bound for the counting function of the transmission eigenvalue problem for Maxwell equations

Hoài-Minh Nguyên, Jean Louis-Alexandre Fornerod

Cakoni and Nguyen recently proposed very general conditions on the coefficients of Maxwell equations for which they established the discreten ess of the set of eigenvalues of the transmission problem and studied their locations. In this paper, we establish ...

2021

Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Ola Nils Anders Svensson, Adam Teodor Polak, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Xinrui Jia

We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A k-clustering is said to be explainable if it is given by a decision tree where each internal node splits data point ...

2021

Sequential metric dimension for random graphs

Patrick Thiran, Gergely Odor

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

2021

Differential Entropy of the Conditional Expectation under Gaussian Noise

Michael Christoph Gastpar, Alper Köse, Ahmet Arda Atalik

This paper considers an additive Gaussian noise channel with arbitrarily distributed finite variance input signals. It studies the differential entropy of the minimum mean-square error (MMSE) estimator and provides a new lower bound which connects the diff ...

IEEE2021

Deep Boltzmann Machines: Rigorous Results at Arbitrary Depth

Emanuele Mingione, Diego Alberici

A class of deep Boltzmann machines is considered in the simplified framework of a quenched system with Gaussian noise and independent entries. The quenched pressure of a K-layers spin glass model is studied allowing interactions only among consecutive laye ...

2021

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2020

Understanding and Mitigating Latency Variability of Latency-Critical Applications

Mia Primorac

A major theme of IT in the past decade has been the shift from on-premise hardware to cloud computing. Running a service in the public cloud is practical, because a large number of resources can be bought on-demand, but this shift comes with its own set of ...

EPFL2020