Search

In this short note, we provide a simple version of an accelerated forward-backward method (a.k.a. Nesterov's accelerated proximal gradient method) possibly relying on approximate proximal operators and allowing to exploit strong convexity of the objective function. The method supports both relative and absolute errors, and its behavior is illustrated on a set of standard numerical experiments. Using the same developments, we further provide a version of the accelerated proximal hybrid extragradient method of Monteiro and Svaiter (2013) possibly exploiting strong convexity of the objective function., Comment: Published in Open Journal on Mathematical Optimization (https://ojmo.centre-mersenne.org/item/10.5802/ojmo.12.pdf). Code available at https://github.com/mathbarre/StronglyConvexForwardBackward

We study a geometric construction of certain finite index subgroups of Aut(F2).

We prove non asymptotic linear convergence rates for the constrained Anderson acceleration extrapolation scheme. These guarantees come from new upper bounds on the constrained Chebyshev problem, which consists in minimizing the maximum absolute value of a polynomial on a bounded real interval with $l_1$ constraints on its coefficients vector. Constrained Anderson Acceleration has a numerical cost comparable to that of the original scheme.

Hyperspectral satellite images report greenhouse gas concentrations worldwide on a daily basis. While taking simple averages of these images over time produces a rough estimate of relative emission rates, atmospheric transport means that simple averages fail to pinpoint the source of these emissions. We propose using Wasserstein barycenters coupled with weather data to average gas concentration data sets and better concentrate the mass around significant sources.

We study a family of tessellations of the Euclidean plane which are obtained by local developments of algebraic equations satisfied by the Pauli matrices.

In two dimensions, a system of self-gravitating particles collapses and forms a singularity in finite time below a critical temperature $T_c$. We investigate experimentally a quasi two-dimensional cloud of cold neutral atoms in interaction with two pairs of perpendicular counter-propagating quasi-resonant laser beams, in order to look for a signature of this ideal phase transition: indeed, the radiation pressure forces exerted by the laser beams can be viewed as an anisotropic, and non-potential, generalization of two-dimensional self-gravity. We first show that our experiment operates in a parameter range which should be suitable to observe the collapse transition. However, the experiment unveils only a moderate compression instead of a phase transition between the two phases. A three-dimensional numerical simulation shows that both the finite small thickness of the cloud, which induces a competition between the effective gravity force and the repulsive force due to multiple scattering, and the atomic losses due to heating in the third dimension, contribute to smearing the transition., Comment: 11 pages, 8 figures, accepted in Physical Review A

Proximal operations are among the most common primitives appearing in both practical and theoretical (or high-level) optimization methods. This basic operation typically consists in solving an intermediary (hopefully simpler) optimization problem. In this work, we survey notions of inaccuracies that can be used when solving those intermediary optimization problems. Then, we show that worst-case guarantees for algorithms relying on such inexact proximal operations can be systematically obtained through a generic procedure based on semidefinite programming. This methodology is primarily based on the approach introduced by Drori and Teboulle (2014) and on convex interpolation results, and allows producing non-improvable worst-case analyzes. In other words, for a given algorithm, the methodology generates both worst-case certificates (i.e., proofs) and problem instances on which those bounds are achieved. Relying on this methodology, we study numerical worst-case performances of a few basic methods relying on inexact proximal operations including accelerated variants, and design a variant with optimized worst-case behaviour. We further illustrate how to extend the approach to support strongly convex objectives by studying a simple relatively inexact proximal minimization method., Comment: A-HPE and inexact forward-backward methods for strongly convex objectives were removed in this version, they can now be found in the work entitled "A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives". Code available at https://github.com/mathbarre/InexactProximalOperators/tree/version-2

We study a population of $N$ particles, which evolve according to a diffusion process and interact through a dynamical network. In turn, the evolution of the network is coupled to the particles' positions. In contrast with the mean-field regime, in which each particle interacts with every other particle, i.e. with $O(N)$ particles, we consider the a priori more difficult case of a sparse network; that is, each particle interacts, on average, with $O(1)$ particles. We also assume that the network's dynamics is much faster than the particles' dynamics, with the time-scale of the network described by a parameter $\epsilon>0$. We combine the averaging ($\epsilon \rightarrow 0$) and the many particles ($N \rightarrow \infty$) limits and prove that the evolution of the particles' empirical density is described (after taking both limits) by a non-linear Fokker-Planck equation; we moreover give conditions under which such limits can be taken uniformly in time, hence providing a criterion under which the limiting non-linear Fokker-Planck equation is a good approximation of the original system uniformly in time. The heart of our proof consists of controlling precisely the dependence in $N$ of the averaging estimates., Comment: 33 pages

In smooth strongly convex optimization, knowledge of the strong convexity parameter is critical for obtaining simple methods with accelerated rates. In this work, we study a class of methods, based on Polyak steps, where this knowledge is substituted by that of the optimal value, $f_*$. We first show slightly improved convergence bounds than previously known for the classical case of simple gradient descent with Polyak steps, we then derive an accelerated gradient method with Polyak steps and momentum, along with convergence guarantees., Comment: Accepted to COLT2020

We study a geometric action on a CAT(0) space of a finite index subgroup of the quotient group of the braid group on 4 strands by its center.

Producing intense radioactive beams, in particular those consisting of short-lived isotopes requires the control of the release efficiency. The released fractions of 11 elements were measured on 14 samples that were characterized by various physicochemical analyses in a correlated paper (Part 1). A multivariate statistical approach, using the principal component analysis, was performed to highlight the impact of the microstructure on the release properties. Samples that best release fission products consist of grains and aggregates with small size and display a high porosity distributed on small diameter pores. They were obtained applying a mixing of ground uranium dioxide and carbon nanotubes powders leading to homogeneous uranium carbide samples with a porous nanostructure. A modelling under on-line ALTO conditions was carried out using the FLUKA code to compare the yields released by an optimized and a conventional target.

We consider extended slow-fast systems of N interacting diffusions. The typical behavior of the empirical density is described by a nonlinear McKean-Vlasov equation depending on , the scaling parameter separating the time scale of the slow variable from the time scale of the fast variable. Its atypical behavior is encapsulated in a large N Large Deviation Principle (LDP) with a rate functional. We study the $\Gamma$-convergence of as $\rightarrow$ 0 and show it converges to the rate functional appearing in the Macroscopic Fluctuations Theory (MFT) for diffusive systems.

We propose a classification of bifurcations of Vlasov equations, based on the strength of the resonance between the unstable mode and the continuous spectrum on the imaginary axis. We then identify and characterize a new type of generic bifurcation where this resonance is weak, but the unstable mode couples with the Casimirs, which are constants of motion, to form a size 3 Jordan block. We derive a three-dimensional reduced noncanonical Hamiltonian system describing this bifurcation: coupling with the Casimirs controls the phase space portrait. Comparison of the reduced dynamics with direct numerical simulations on a test case gives excellent agreement. We finally discuss the relevance of this bifurcation to specific physical situations., Comment: 6 pages, 2 figures. Supplemental material available at the URL https://www.idpoisson.fr/barre/publications-et-preprints/

Accelerated algorithms for minimizing smooth strongly convex functions usually require knowledge of the strong convexity parameter $\mu$. In the case of an unknown $\mu$, current adaptive techniques are based on restart schemes. When the optimal value $f^*$ is known, these strategies recover the accelerated linear convergence bound without additional grid search. In this paper we propose a new approach that has the same bound without any restart, using an online estimation of strong convexity parameter. We show the robustness of the Fast Gradient Method when using a sequence of upper bounds on $\mu$. We also present a good candidate for this estimate sequence and detail consistent empirical results.

Motivated by experiments on cell segregation, we present a two-species model of interacting particles, aiming at a quantitative description of this phenomenon. Under precise scaling hypothesis, we derive from the microscopic model a macroscopic one and we analyze it. In particular, we determine the range of parameters for which segregation is expected. We compare our analytical results and numerical simulations of the macroscopic model to direct simulations of the particles, and comment on possible links with experiments.

Tracking expensive goods and/or targeted individuals with high-tech devices has been of high interest for the last 30 years. More recently, other use cases such as parents tracking their children have become popular. One primary functionality of these devices has been the collection of GPS coordinates of the location of the trackers, and to send these to remote servers through a cellular modem and a SIM card. Reviewing existing devices, it has been observed that beyond simple GPS trackers many devices intend to enclose additional features such as microphones, cameras, or Wi-Fi interfaces enabling advanced spying activities. In this study, we propose to describe the methodology applied to evaluate the security level of GPS trackers with different capabilities. Several security flaws have been discovered during our security assessment highlighting the need of a proper hardening of these devices when used in critical environments., Comment: 13 pages, 10 figures

We model a particulate flow of constant velocity through confined geometries, ranging from a single channel to a bundle of $N_c$ identical coupled channels, under conditions of reversible blockage. Quantities of interest include the exiting particle flux (or throughput) and the probability that the bundle is open. For a constant entering flux, the bundle evolves through a transient regime to a steady state. We present analytic solutions for the stationary properties of a single channel with capacity $N\le 3$ and for a bundle of channels each of capacity $N = 1$. For larger values of $N$ and $N_c$, the system's steady state behavior is explored by numerical simulation. Depending on the deblocking time, the exiting flux either increases monotonically with intensity or displays a maximum at a finite intensity. For large $N$ we observe an abrupt change from a state with few blockages to one in which the bundle is permanently blocked and the exiting flux is due entirely to the release of blocked particles. We also compare the relative efficiency of coupled and uncoupled bundles. For $N=1$ the coupled system is always more efficient, but for $N>1$ the behavior is more complex., Comment: 14 pages, 15 figures

We study the isomorphism types of simply connected complexes of rank 7/4 using a local invariant called the parity. We show that the parity can be computed explicitly in certain constructions arising from surgery.