Nicolas Gast
email: nicolas.gast@inria.fr

Luca Bortolussi
email: lbortolussi@units.it

Mirco Tribastone
email: mirco.tribastone@imtlucca.it

Size Expansions of Mean Field Approximation: Transient and Steady-State Analysis Extended abstract *

. In this paper, we show how to obtain the same result for the transient regime and we provide a further refinement by expanding the term in 1/N 2 (both for transient and steady-state regime). Our derivations are inspired by moment-closure approximation. We provide a number of examples that show this new approximation is usable in practice for systems with up to a few tens of dimensions.

INTRODUCTION

Mean field approximation is a widely used technique in the performance evaluation community (e.g., to study loadbalancing strategies [START_REF] David | The Power of Two Random Choices in Randomized Load Balancing[END_REF][START_REF] Vvedenskaya | Queueing system with selection of the shortest of two queues: An asymptotic approach[END_REF] to mention a popular application). The focus of this approximation is to study the performance of systems composed of a large number of interacting objects. This approximation can be used to study transient (for example the time to fill a cache [START_REF] Gast | Transient and steady-state regime of a family of list-based cache replacement algorithms[END_REF]) or steadystate properties (for example the steady-state response time of a system [START_REF] David | The Power of Two Random Choices in Randomized Load Balancing[END_REF][START_REF] Vvedenskaya | Queueing system with selection of the shortest of two queues: An asymptotic approach[END_REF]). One of the reasons of the success of mean field approximation is that it is often very accurate as soon as N , the number of objects in the system, exceeds a few hundreds. In fact, this approximation can be proven to be asymptotically exact as N goes to infinity, see for example [START_REF] Thomas | Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes[END_REF][START_REF] Benaim | A class of mean field interaction models for computer and communication systems[END_REF] and explicit bounds for the convergence rate exist [START_REF] Bortolussi | Bounds on the deviation of discrete-time markov chains from their mean-field model[END_REF][START_REF] Gast | Expected values estimated via mean-field approximation are 1/n-accurate[END_REF][START_REF] Ying | On the approximation error of mean-field models[END_REF].

Recently, the authors of [START_REF] Gast | A refined mean field approximation[END_REF] proposed what they call a refined mean field approximation that can be used to characterize steady-state performance metrics more precisely. Their refinement uses that for many models, a steady-state expected performance metric of a system with N objects E[h(X)] is equal to its mean field approximation h(π) plus a term in 1/N :

E [h(X)] = h(π) + 1 N V (h) + o 1 N , ( 1
)
where π is the fixed point of the ODE that describes the mean field approximation and V (h) is a constant that can be easily evaluated numerically. By using a number of examples, they show that the refined approximation h(π)+ 1 N V (h) is much more accurate than the mean field approximation for moderate system sizes (i.e., a few tens of objects).

MAIN RESULTS

In [START_REF] Gast | Size expansions of mean field approximation: Transient and steady-state analysis[END_REF], we extend this method in two directions: First we generalize Equation (1) to the transient behavior; second we establish the existence of a second order term in 1/N 2 (both in transient and steady-state regimes). More precisely, we establish conditions such that for any smooth function h, there exist constants V (h) and A (h) such that for any time t ∈ [0; ∞) ∪ {∞}:

E [h(X(t))] = h(x(t)) + 1 N V (h) (t) + 1 N 2 A (h) (t) + o 1 N 2 .
We show that for the transient regime t ∈ [0, ∞), V (h) (t) and A (h) (t) satisfy a linear time-inhomogeneous differential equation that can be easily integrated numerically. For the steady-state, the constants V (h) (∞) and A (h) (∞) correspond to the fixed point of this differential equation. We use the above expansion to propose two new approximations that depend on the system size N and that are expansions of the classical mean field approximation to the order 1/N and 1/N 2 . This gives three approximations:

• The mean field approximation: h(x(t));

• 1/N -expansion: h(x(t)) + V (h) (t)/N ; • 1/N 2 -expansion: h(x(t)) + V (h) (t)/N + A (h) (t)/N 2 .
We derive our results for the classical model of densitydependent population process [START_REF] Thomas | Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes[END_REF].

NUMERICAL COMPARISON

In [START_REF] Gast | Size expansions of mean field approximation: Transient and steady-state analysis[END_REF], we study numerically the accuracy of the approximation by considering three examples: two malware propagation models and the classical supermarket models of [START_REF] David | The Power of Two Random Choices in Randomized Load Balancing[END_REF][START_REF] Vvedenskaya | Queueing system with selection of the shortest of two queues: An asymptotic approach[END_REF]. Our numerical results shows that the two expansions very accurately capture the transient behavior of such a system even when N ≈ 10. Moreover, they are generally much more accurate than the classical mean field approximation for small values of N (for transient and steady-state regimes). Our experiments also confirm the good accuracy of the 1/N -expansion approximation that was observed for steady-state values in [START_REF] Gast | A refined mean field approximation[END_REF]: In most cases, the largest gain in accuracy comes from the 1/N -term (both for the transient and steady-state values). The 1/N 2 -term does improve the accuracy but only marginally. We also study the limit of the method by studying an unstable mean field model that has an unstable fixed point.

The Supermarket Model. To give a flavor of the results, let us consider the supermarket model (more examples can be found in the full paper). The system is composed of N identical servers. Jobs arrive at a central broker according to a Poisson process of rate ρN and are dispatched towards the servers by using the JSQ(2) policy: for each incoming job, the broker samples 2 servers at random and sends the jobs to the server that has the smallest number of jobs in its queue (ties are broken at random). The time to process a job is exponentially distributed with mean 1. In Figure 1, we plot how the expected queue length evolves with time for the supermarket model with N = 10 servers and ρ = 0.9. We start in a system where 8 queues have 3 jobs and 2 queues have two jobs. We observe that the two expansions are much more accurate than the classical mean field approximation and that the 1/N 2 -expansion provides a slightly better approximation than the 1/N -expansion.

In Table 1, we show the average queue length for different values of ρ and N . Again, we observe that the values coming from the two expansions are much closer to the values obtained by simulation than the classical mean field approximation. Again, most of the gain seems to come from the 1/N -term.

N k ρ Mean field1/N -expansion1/N 2 -

CONCLUSION

To summarize, we show in [START_REF] Gast | Size expansions of mean field approximation: Transient and steady-state analysis[END_REF] how mean field approximation can be refined by a first term in 1/N and a second term 1/N 2 where N is the size of the system. We exhibit conditions that ensure that this asymptotic expansion can be applied for the transient as well as the steady-state regimes. In the transient regime, these constants satisfy ordinary differential equations that can be easily integrated numerically. We provide a few examples that show that the 1/N and 1/N 2 expansions are much more accurate than the classical mean field approximation. We also study the limitations of the approach and show that, when the mean field approximation does not have an attractor, these new approximations might be unstable for large time horizons. Obtaining a better approximation in this case remains a challenge that we leave for future work.

Finally, we show that, despite the complexity of the formulas, it is relatively easy to compute the 1/N and 1/N 2 terms (in the transient and steady-state regimes) for realistic models such as the supermarket model. The developed method is generic and is implemented in a tool [START_REF] Gast | Refined mean field tool[END_REF].

Reproducibility. The code to reproduce the paper -including simulations, figures and text -is available at [START_REF] Gast | Size expansions of mean field approximation: Transient and steady-state analysis[END_REF].

Figure 1 :

 1 Figure 1: Supermarket model : expected queue length as a function of time.

Table 1 :

 1 Supermarket model, steady-state average queue length : comparison of the value computed by simulation with the three approximations.

					expansionSimulation
	10 2	0.9	2.3527	2.7513	2.8045	2.8002
	20 2	0.9	2.3527	2.5520	2.5653	2.5662
	10 2 0.95 3.2139	4.1017	4.3265	4.2993
	20 2 0.95 3.2139	3.6578	3.7140	3.7124


Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

Harilaos Christos
email: christos@berkeley.edu

Georgios Papadimitriou
email: georgios@sutd.edu.sg.

Piliouras

Christos Papadimitriou

AND Georgios Piliouras

Cycles in adversarial regularized learning

Keywords: Regret, multiplicative weights update, zero-sum games, dueling algorithms

come

Introduction

Regularization is a fundamental and incisive method in optimization, its present zeitgeist and its entry into machine learning. Through the introduction of a new component in the objective, regularization techniques overcome ill-conditioning and overfitting, and they yield algorithms that achieve sparsity and parsimony without sacrificing efficiency [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF][START_REF] Ben-Tal | Lectures on modern convex optimization: analysis, algorithms, and engineering applications[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF].

In the context of online optimization, these features are exemplified in the family of learning algorithms known as "Follow the Regularized Leader" (FoReL) [START_REF] Shalev-Shwartz | Convex repeated games and Fenchel duality[END_REF]. FoReL represents an important archetype of adaptive behavior for several reasons: it provides optimal min-max regret guarantees (O(t -1/2 ) in an adversarial setting), it offers significant flexibility with respect to the geometry of the problem at hand, and it captures numerous other dynamics as special cases (hedge, multiplicative weights, gradient descent, etc.) [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Hazan | Introduction to online convex optimization[END_REF]. As such, given that these regret guarantees hold without any further assumptions about how payoffs/costs are determined at each stage, the dynamics of FoReL have been the object of intense scrutiny and study in algorithmic game theory.

The standard way of analyzing such no-regret dynamics in games involves a two-step approach. The first step exploits the fact that the empirical frequency of play under a no-regret algorithm converges to the game's set of coarse correlated equilibria (CCE). The second involves proving some useful property of the game's CCE: For instance, leveraging (λ, µ)-robustness [START_REF] Roughgarden | Intrinsic robustness of the price of anarchy[END_REF] implies that the social welfare at a CCE lies within a small constant of the optimum social welfare; as another example, the product of the marginal distributions of CCE in zero-sum games is Nash. In this way, the no-regret properties of FoReL can be turned into convergence guarantees for the players' empirical frequency of play (that is, in a time-averaged, correlated sense).

Recently, several papers have moved beyond this "black-box" framework and focused instead on obtaining stronger regret/convergence guarantees for systems of learning algorithms coupled together in games with a specific structure. Along these lines, Daskalakis et al. [START_REF] Daskalakis | Near-optimal no-regret algorithms for zero-sum games[END_REF] and Rakhlin and Sridharan [START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF] developed classes of dynamics that enjoy a O(log t/t) regret minimization rate in two-player zerosum games. Syrgkanis et al. [START_REF] Syrgkanis | Fast convergence of regularized learning in games[END_REF] further analyzed a recency biased variant of FoReL in more general multi-player games and showed that it is possible to achieve an O(t -3/4 ) regret minimization rate. The social welfare converges at a rate of O(t -1 ), a result which was extended to standard versions of FoReL dynamics in [START_REF] Foster | Learning in games: Robustness of fast convergence[END_REF].

Whilst a regret-based analysis provides significant insights about these systems, it does not answer a fundamental behavioral question: Does the system converge to a Nash equilibrium? Does it even stabilize?

The dichotomy between a self-stabilizing, convergent system and a system with recurrent cycles is of obvious significance, but a regret-based analysis cannot distinguish between the two. Indeed, convergent, recurrent, and even chaotic [START_REF] Palaiopanos | Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos[END_REF] systems may exhibit equally strong regret minimization properties in general games, so the question remains: What does the long-run behavior of FoReL look like, really? This question becomes particularly interesting and important under perfect competition (such as zero-sum games and variants thereof). Especially in practice, zero-sum games can capture optimization "duels" [START_REF] Immorlica | Dueling algorithms[END_REF]: for example, two Internet search engines competing to maximize their market share can be modeled as players in a zero-sum game with a convex strategy space. In [START_REF] Immorlica | Dueling algorithms[END_REF] it was shown that the time-average of a regret-minimizing class of dynamics converges to an approximate equilibrium of the game. Finally, zero-sum games have also been used quite recently as a model for deep learning optimization techniques in image generation and discrimination [START_REF] Goodfellow | Generative adversarial nets[END_REF][START_REF] Schuurmans | Deep learning games[END_REF].

In each of the above cases, min-max strategies are typically thought of as the axiomatically correct prediction. The fact that the time average of the marginals of a FoReL procedure converges to such states is considered as further evidence of the correctness of this prediction. However, the long-run behavior of the actual sequence of play (as opposed to its time-averages) seems to be trickier, and a number of natural questions arise:

-Does optimization-driven learning converge under perfect competition? -Does fast regret minimization necessarily imply (fast) equilibration in this case?

Our results. We settle these questions with a resounding "no". Specifically, we show that the behavior of FoReL in zero-sum games with an interior equilibrium (e.g. Matching Pennies) is Poincaré recurrent, implying that almost every trajectory revisits any (arbitrarily small) neighborhood of its starting point infinitely often. Importantly, the observed cycling behavior is robust to the agents' choice of regularization mechanism (each agent could be using a different regularizer), and it applies to any positive affine transformation of zero-sum games (and hence all strictly competitive games [START_REF] Adler | A note on strictly competitive games[END_REF]) even though these transformations lead to different trajectories of play. Finally, this cycling behavior also persists in the case of networked competition, i.e. for constant-sum polymatrix games [START_REF] Cai | Zero-sum polymatrix games: A generalization of minmax[END_REF][START_REF] Cai | On minmax theorems for multiplayer games[END_REF][START_REF] Daskalakis | On a network generalization of the minmax theorem[END_REF].

Given that the no-regret guarantees of FoReL require a decreasing step-size (or learning rate), 1 we focus on a smooth version of FoReL described by a dynamical system in continuous time. The resulting FoReL dynamics enjoy a particularly strong O(t -1 ) regret minimization rate and they capture as a special case the replicator dynamics [START_REF] Schuster | Replicator dynamics[END_REF][START_REF] Taylor | Evolutionarily stable strategies with two types of player[END_REF][START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF] and the projection dynamics [START_REF] Friedman | Evolutionary games in economics[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Sandholm | The projection dynamic and the replicator dynamic[END_REF], arguably the most widely studied game dynamics in biology, evolutionary game theory and transportation science [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF][START_REF] Sandholm | Population Games and Evolutionary Dynamics[END_REF][START_REF] Weibull | Evolutionary Game Theory[END_REF]. In this way, our analysis unifies and generalizes many prior results on the cycling behavior of evolutionary dynamics [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF][START_REF] Piliouras | Persistent patterns: Multi-agent learning beyond equilibrium and utility[END_REF][START_REF] Piliouras | Optimization despite chaos: Convex relaxations to complex limit sets via poincaré recurrence[END_REF][START_REF] Sato | Chaos in learning a simple two-person game[END_REF] and it provides a new interpretation of these results through the lens of optimization and machine learning.

From a technical point of view, our analysis touches on several issues. Our first insight is to focus not on the simplex of the players' mixed strategies, but on a dual space of payoff differences. The reason for this is that the vector of cumulative payoff differences between two strategies fully determines a player's mixed strategy under FoReL, and it is precisely these differences that ultimately drive the players' learning process. Under this transformation, FoReL exhibits a striking property,

1

A standard trick is to decrease step-sizes by a constant factor after a window of "doubling" length [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF].

incompressibility: the flow of the dynamics is volume-preserving, so a ball of initial conditions in this dual space can never collapse to a point.

That being said, the evolution of such a ball in the space of payoffs could be transient, implying in particular that the players' mixed strategies could converge (because the choice map that links payoff differences to strategies is nonlinear). To rule out such behaviors, we show that FoReL in zero-sum games with an interior Nash equilibrium has a further important property: it admits a constant of motion. Specifically, if x * = (x * i ) i∈N is an interior equilibrium of the game and y i is an arbitrary point in the payoff space of player i, this constant is given by the coupling function

G(y) = i∈N [h * i (y i ) -y i , x * i ],
where

h * i (y i ) = max xi { y i , x i -h i (x i )}
is the convex conjugate of the regularizer h i that generates the learning process of player i (for the details, see Sections 3 and 4). Coupled with the dynamics' incompressibility, this invariance can be used to show that FoReL is recurrent: after some finite time, almost every trajectory returns arbitrarily close to its initial state.

On the other hand, if the game does not admit an interior equilibrium, the coupling above is no longer a constant of motion. In this case, G decreases over time until the support of the players' mixed strategies matches that of a Nash equilibrium with maximal support: as this point in time is approached, G essentially becomes a constant. Thus, in general zero-sum games, FoReL wanders perpetually in the smallest face of the game's strategy space containing all of the game's equilibria; indeed, the only possibility that FoReL converges is if the game admits a unique Nash equilibrium in pure strategies -a fairly restrictive requirement.

Definitions from game theory

2.1. Games in normal form. We begin with some basic definitions from game theory. A finite game in normal form consists of a finite set of players N = {1, . . . , N }, each with a finite set of actions (or strategies) A i . The preferences of player i for one action over another are determined by an associated payoff function u i : A ≡ i A i → R which assigns a reward u i (α i ; α -i ) to player i ∈ N under the strategy profile (α i ; α -i ) of all players' actions. 2 Putting all this together, a game in normal form will be written as a tuple Γ ≡ Γ(N , A, u) with players, actions and payoffs defined as above.

Players can also use mixed strategies, i.e. mixed probability distributions x i = (x iαi ) αi∈Ai ∈ ∆(A i ) over their action sets A i . The resulting probability vector x i is called a mixed strategy and we write X i = ∆(A i ) for the mixed strategy space of player i. Aggregating over players, we also write X = i X i for the game's strategy space, i.e. the space of all strategy profiles x = (x i ) i∈N .

In this context (and in a slight abuse of notation), the expected payoff of the i-th player in the profile x = (x 1 , . . . , x N ) is

u i (x) = α1∈A1 • • • α N ∈A N u i (α 1 , . . . , α N ) x 1α1 • • • x N α N . (2.1)
To keep track of the payoff of each pure strategy, we also write v iαi (x) = u i (α i ; x -i ) for the payoff of strategy α i ∈ A i under the profile x ∈ X and v i (x) = (v iαi (x)) αi∈Ai for the resulting payoff vector of player i. We then have

u i (x) = v i (x), x i = αi∈Ai x iαi v iαi (x), (2.2)
where v, x ≡ v x denotes the ordinary pairing between v and x.

The most widely used solution concept in game theory is that of a Nash equilibrium (NE), defined here as a mixed strategy profile x * ∈ X such that

u i (x * i ; x * -i ) ≥ u i (x i ; x * -i ) (NE)
for every deviation x i ∈ X i of player i and all i ∈ N . Writing supp(

x * i ) = {α i ∈ A i : x * i > 0} for the support of x * i ∈ X i , a Nash equilibrium x * ∈ X is called pure if supp(x * i ) = {α * i } for some α * i ∈ A i and all i ∈ N .
At the other end of the spectrum, x * is said to be interior (or fully mixed ) if supp(x * i ) = A i for all i ∈ N . Finally, a coarse correlated equilibrium (CCE) is a distribution π over the set of action profiles A ≡ i A i such that, for every player i ∈ N and every action

β i ∈ A i , we have α∈A v i (α)π(α) ≥ α-i∈A-i v i (β i , α -i )π i (α -i ), where π i (α -i ) = αi∈αi π(α i , α -i )
is the marginal distribution of π with respect to i.

2.2.

Zero-sum games and zero-sum polymatrix games. Perhaps the most widely studied class of finite games (and certainly the first to be considered) is that of 2player zero-sum games, i.e. when N = {1, 2} and u 1 = -u 2 . Letting u ≡ u 1 = -u 2 , the value of a 2-player zero-sum game Γ is defined as

u Γ = max x1∈X1 min x2∈X2 u(x 1 , x 2 ) = min x2∈X2 max x1∈X1 u(x 1 , x 2 ), (2.3)
with equality following from von Neumann's celebrated min-max theorem [START_REF] Neumann | Zur Theorie der Gesellschaftsspiele[END_REF]. As is well known, the solutions of this saddle-point problem form a closed, convex set consisting precisely of the game's Nash equilibria; moreover, the players' equilibrium payoffs are simply u Γ and -u Γ respectively. As a result, Nash equilibrium is the standard game-theoretic prediction in such games. An important question that arises here is whether the straightforward equilibrium structure of zero-sum games extends to the case of a network of competitors. Following [START_REF] Cai | Zero-sum polymatrix games: A generalization of minmax[END_REF][START_REF] Cai | On minmax theorems for multiplayer games[END_REF][START_REF] Daskalakis | On a network generalization of the minmax theorem[END_REF], an N -player pairwise zero-/constant-sum polymatrix game consists of an (undirected) interaction graph G ≡ G(N , E) whose set of nodes N represents the competing players, with two nodes i, j ∈ N connected by an edge e = (i, j) in E if and only if the corresponding players compete with each other in a two-player zero-/constant-sum game.

To formalize this, we assume that a) every player has a finite set of actions A i (as before); and b) to each edge e = {i, j} ∈ E is associated a two-player game zero-/constant-sum Γ e with player set N e = {i, j}, action sets A i and A j , and payoff functions u ij = γ {i,j} -u ji : A i × A j → R respectively. 3 The space of mixed strategies of player i is again X i = ∆(A i ), but the player's payoff is now determined by aggregating over all games involving player i, i.e.

u i (x) = j∈Ni u ij (x i , x j ), (2.4)
where N i = {j ∈ N : {i, j} ∈ E} denotes the set of "neighbors" of player i. In other words, the payoff to player i is simply the the sum of all payoffs in the zero-/constant-sum games that player i plays with their neighbors.

In what follows, we will also consider games which are payoff-equivalent to positive-affine transformations of pairwise constant-sum polymatrix games. Formally, we will allow for games Γ such that there exists a pairwise constant-sum polymatrix game Γ and constants a i > 0 and b i ∈ R for each player i such that

u Γ i (α) = a i u Γ i (α) + b i for each outcome α ∈ A.

No-regret learning via regularization

Throughout this paper, our focus will be on repeated decision making in lowinformation environments where the players don't know the rules of the game (perhaps not even that they are playing a game). In this case, even if the game admits a unique Nash equilibrium, it is not reasonable to assume that players are able to pre-compute their component of an equilibrium strategy -let alone assume that all players are fully rational, that there is common knowledge of rationality, etc.

With this in mind, we only make the bare-bones assumption that every player seeks to at least minimize their "regret", i.e. the average payoff difference between a player's mixed strategy at time t ≥ 0 and the player's best possible strategy in hindsight. Formally, assuming that play evolves in continuous time, the regret of player i along the sequence of play x(t) is defined as

Reg i (t) = max pi∈Xi 1 t t 0 [u i (p i ; x -i (s)) -u i (x(s))] ds, (3.1)
and we say that player i has no regret under x(t) if lim sup t→∞ Reg i (t) ≤ 0.

The most widely used scheme to achieve this worst-case guarantee is known as "Follow the Regularized Leader" (FoReL), an exploitation-exploration class of policies that consists of playing a mixed strategy that maximizes the player's expected cumulative payoff (the exploitation part) minus a regularization term (exploration). In our continuous-time framework, this is described by the learning dynamics

y i (t) = y i (0) + t 0 v i (x(s)) ds, x i (t) = Q i (y i (t)), (FoReL)
where the so-called choice map Q i : R Ai → X i is defined as

Q i (y i ) = arg max xi∈Xi { y i , x i -h i (x i )}. (3.2)
In the above, the regularizer function h i : X i → R is a convex penalty term which smoothens the "hard" arg max correspondence y i → arg max xi∈Xi y i , x i that maximizes the player's cumulative payoff over [0, t]. As a result, the "regularized leader"

Q i (y i ) = arg max xi∈Xi { y i , x i -h i (x i )} is biased towards the prox-center p i = arg min xi∈Xi h i (x i ) of X i .
For most common regularizers, the prox-center is interior (and usually coincides with the barycenter of X ), so the regularization in (3.2) encourages exploration by favoring mixed strategies with full support.

In Appendix A, we present in detail two of the prototypical examples of (FoReL): i ) the multiplicative weights (MW) dynamics induced by the entropic regularizer function h i (x) = αi∈Ai x iαi log x iαi (which lead to the replicator dynamics of evolutionary game theory); and ii) the projection dynamics induced by the Euclidean

regularizer h i (x) = 1 2 x i 2 .
For concreteness, we will assume in what follows that the regularizer of every player i ∈ N satisfies the following minimal requirements:

(1) h i is continuous and strictly convex on X i .

(2) h i is smooth on the relative interior of every face of X i (including X i itself). Under these basic assumptions, the "regularized leader" Q i (y i ) is well-defined in the sense that (3.2) admits a unique solution. More importantly, we have the following no-regret guarantee: Theorem 3.1. A player following (FoReL) enjoys an O(1/t) regret bound, no matter what other players do. Specifically, if player i ∈ N follows (FoReL), then, for every continuous trajectory of play x -i (t) of the opponents of player i, we have

Reg i (t) ≤ Ω i t , (3.3)
where

Ω i = max h i -min h i is a positive constant.
To streamline our discussion, we relegate the proof of Theorem 3.1 to Appendix C; we also refer to [START_REF] Kwon | A continuous-time approach to online optimization[END_REF] for a similar regret bound for (FoReL) in the context of online convex optimization. Instead of discussing the proof, we close this section by noting that (3.3) represents a striking improvement over the Θ(t -1/2 ) worst-case bound for FoReL in discrete time [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF]. In view of this, the continuous-time framework we consider here can be seen as particularly amenable to learning because it allows players seek to minimize their regret (and thus converge to coarse correlated equilibria) at the fastest possible rate.

Recurrence in adversarial regularized learning

In this section, our aim is to take a closer look at the ramifications of fast regret minimization under (FoReL) beyond convergence to the set of coarse correlated equilibria. Indeed, as is well known, this set is fairly large and may contain thoroughly non-rationalizable strategies: for instance, Viossat and Zapechelnyuk [START_REF] Viossat | No-regret dynamics and fictitious play[END_REF] recently showed that a coarse correlated equilibrium could assign positive selection probability only to strictly dominated strategies. Moreover, the time-averaging that is inherent in the definition of the players' regret leaves open the possibility of complex day-to-day behavior e.g. periodicity, recurrence, limit cycles or chaos [START_REF] Palaiopanos | Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos[END_REF][START_REF] Papadimitriou | From nash equilibria to chain recurrent sets: Solution concepts and topology[END_REF][START_REF] Piliouras | Optimization despite chaos: Convex relaxations to complex limit sets via poincaré recurrence[END_REF][START_REF] Sato | Chaos in learning a simple two-person game[END_REF]. Motivated by this, we examine the long-run behavior of the (FoReL) in the popular setting of zero-sum games (with or without interior equilibria) and several extensions thereof.

A key notion in our analysis is that of (Poincaré) recurrence. Intuitively, a dynamical system is recurrent if, after a sufficiently long (but finite) time, almost every state returns arbitrarily close to the system's initial state. 4 More formally, given a dynamical system on X that is defined by means of a semiflow Φ : X × [0, ∞) → X , we have: 5 Definition 4.1. A point x ∈ X is said to be recurrent under Φ if, for every neighborhood U of x in X , there exists an increasing sequence of times t n ↑ ∞ such that 4 Here, "almost" means that the set of such states has full Lebesgue measure. 5 Recall that a continuous map Φ : X ×[0, ∞) → X is a semiflow if Φ(x, 0) = x and Φ(x, t+s) = Φ(Φ(x, t), s) for all x ∈ X and all s, t ≥ 0. Heuristically, Φt(x) ≡ Φ(x, t) describes the trajectory of the dynamical system starting at x. Φ(x, t n ) ∈ U for all n. Moreover, the flow Φ is called (Poincaré) recurrent if, for every measurable subset A of X , the set of recurrent points in A has full measure.

An immediate consequence of Definition 4.1 is that, if a point is recurrent, there exists an increasing sequence of times t n ↑ ∞ such that Φ(x, t n ) → x. On that account, recurrence can be seen as the flip side of convergence: under the latter, (almost) every initial state of the dynamics eventually reaches some well-defined end-state; instead, under the former, the system's orbits fill the entire state space and return arbitarily close to their starting points infinitely often (so there is no possibility of convergence beyond trivial cases).

4.1. Zero-sum games with an interior equilibrium. Our first result is that (FoReL) is recurrent (and hence, non-convergent) in zero-sum games with an interior Nash equilibrium: Theorem 4.2. Let Γ be a 2-player zero-sum game that admits an interior Nash equilibrium. Then, almost every solution trajectory of (FoReL) is recurrent; specifically, for (Lebesgue) almost every initial condition x(0) = Q(y(0)) ∈ X , there exists an increasing sequence of times t n ↑ ∞ such that x(t n ) → x(0).

The proof of Theorem 4.2 is fairly complicated, so we outline the basic steps below:

(1) We first show that the dynamics of the score sequence y(t) are incompressible, i.e. the volume of a set of initial conditions remains invariant as the dynamics evolve over time. By Poincaré's recurrence theorem (cf. Appendix B), if every solution orbit y(t) of (FoReL) remains in a compact set for all t ≥ 0, incompressibility implies recurrence. (2) To counter the possibility of solutions escaping to infinity, we introduce a transformed system based on the differences between scores (as opposed to the scores themselves). To establish boundedness in these dynamics, we consider the "primal-dual" coupling

G(y) = i∈N [h * i (y i ) -y i , x * i ], (4.1)
where x * is an interior Nash equilibrium and h * i (y i ) = max xi∈Xi { y i , x ih i (x i )} denotes the convex conjugate of h i . 6 The key property of this coupling is that it remains invariant under (FoReL); however, its level sets are not bounded so, again, precompactness of solutions is not guaranteed.

(3) Nevertheless, under the score transformation described above, the level sets of G are compact. Since the transformed dynamics are invariant under said transformation, Poincaré's theorem finally implies recurrence.

Proof of Theorem 4.2. To make the above plan precise, fix some "benchmark" strategy αi ∈ A i for every player i ∈ N and, for all α i ∈ A i \{α i }, consider the corresponding score differences z iαi = y iαi -y i, αi . (4.2) Obviously, z i αi = y i αi -y i αi is identically zero so we can ignore it in the above definition. In so doing, we obtain a linear map Π i : R Ai → R Ai\{ αi} sending y i → z i ; aggregating over all players, we also write Π for the product map Π = (Π 1 , . . . , Π N ) sending y → z. For posterity, note that this map is surjective but not injective,7 so it does not allow us to recover the score vector y from the score difference vector z. Now, under (FoReL), the score differences (4.2) evolve as

żiαi = v iαi (x(t)) -v i αi (x(t)). (4.3)
However, since the right-hand side (RHS) of (4.3) depends on x = Q(y) and the mapping y → z is not invertible (so y cannot be expressed as a function of z), the above does not a priori constitute an autonomous dynamical system (as required to apply Poincaré's recurrence theorem). Our first step below is to show that (4.3) does in fact constitute a well-defined dynamical system on z.

To do so, consider the reduced choice map Qi : R Ai\{ αi} → X i defined as

Qi (z i ) = Q i (y i ) (4.4)
for some y i ∈ R Ai such that Π i (y i ) = z i . That such a y i exists is a consequence of Π i being surjective; furthemore, that Qi (z i ) is well-defined is a consequence of the fact that Q i is invariant on the fibers of Π i . Indeed, by construction, we have Π i (y i ) = Π i (y i ) if and only if y iαi = y iαi + c for some c ∈ R and all α i ∈ A i . Hence, by the definition of Q i , we get

Q i (y i ) = arg max xi∈Xi y i , x i + c αi∈Ai x iαi -h i (x i ) = arg max xi∈Xi { y i , x i -h i (x i )} = Q i (y i ), (4.5)
where we used the fact that αi∈Ai x iαi = 1. The above shows that Q i (y i ) = Q i (y i ) if and only if Π i (y i ) = Π i (y i ), so Qi is well-defined.

Letting Q ≡ ( Q1 , . . . , QN ) denote the aggregation of the players' individual choice maps Qi , it follows immediately that Q(y) = Q(Π(y)) = Q(z) by construction. Hence, the dynamics (4.3) may be written as

ż = V (z), (4.6)
where

V iαi (z) = v iαi ( Qi (z)) -v i αi ( Qi (z)). (4.7)
These dynamics obviously constitute an autonomous system, so our goal will be to use Liouville's formula and Poincaré's theorem in order to establish recurrence and then conclude that the induced trajectory of play x(t) is recurrent by leveraging the properties of Q.

As a first step towards applying Liouville's formula, we note that the dynamics (4.6) are incompressible. Indeed, we have

∂V iαi ∂z iαi = βi∈Ai ∂V iαi ∂x iβi ∂x iβi ∂z iαi = 0, (4.8)
because v i does not depend on x i . We thus obtain div z V (z) = 0, i.e. the dynamics (4.6) are incompressible. We now show that every solution orbit z(t) of (4.6) is precompact, that is, sup t≥0 z(t) < ∞. To that end, note that the coupling G(y) = i∈N [h * i (y i ) -y i , x * i ] defined in (4.1) remains invariant under (FoReL) when Γ is a 2-player zero-sum game. Indeed, by Lemma C.1, we have

dG dt = i∈N v i (x), x i -x * i = v 1 (x), x 1 -x * 1 + v 2 (x), x 2 -x * 2 = u 1 (x 1 , x 2 ) -u 1 (x * 1 , x 2 ) + u 2 (x 1 , x 2 ) -u 2 (x 1 , x * 2 ) = 0, (4.9)
where we used the fact that Q i = ∇h * i in the first line (cf. (C.2) above), and the assumption that x * is an interior Nash equilibrium of a 2-player zero-sum game in the last one. We conclude that G(y(t)) remains constant under (FoReL), as claimed.

By Lemma D.2 in Appendix D, the invariance of G(y(t)) under (FoReL) implies that the score differences z iαi (t) = y iαi (t)-y i αi (t) also remain bounded for all t ≥ 0. Hence, by Liouville's formula and Poincaré's recurrence theorem, the dynamics (4.6) are recurrent, i.e. for (Lebesgue) almost every initial condition z 0 and every neighborhood U of z 0 , there exists some τ U such that z(τ U ) ∈ U (cf. Definition 4.1). Thus, taking a shrinking net of balls B n (z 0 ) = {z : z -z 0 ≤ 1/n} and iterating the above, it follows that there exists an increasing sequence of times t n ↑ ∞ such that z(t n ) → z 0 . Therefore, to prove the corresponding claim for the induced trajectories of play x(t) = Q(y(t)) = Q(z(t)) of (FoReL), fix an initial condition x 0 ∈ X • and take some z 0 such that x 0 = Q(z 0 ). By taking t n as above, we have

z(t n ) → z 0 so, by continuity, x(t n ) = Q(z n ) → Q(z 0 ) = x 0 .
This shows that any solution orbit x(t) of (FoReL) is recurrent and our proof is complete.

Remark. We close this section by noting that the invariance of (4.1) under (FoReL) induces a foliation of X , with each individual trajectory of (FoReL) living on a "leaf" of the foliation (a level set of G). Fig. 1 provides a schematic illustration of this foliation/cycling structure. 4.2. Zero-sum games with no interior equilibria. At first sight, Theorem 4.2 suggests that cycling is ubiquitous in zero-sum games; however, if the game does not admit an interior equilibrium, the behavior of (FoReL) turns out to be qualitatively different. To state our result for such games, it will be convenient to assume that the players' regularizer functions are strongly convex, i.e. each h i can be bounded from below by a quadratic minorant:

h i (tx i + (1 -t)x i ) ≤ th i (x i ) + (1 -t)h i (x i ) -1 2 K i t(1 -t) x i -x i 2 , (4.10)
for all x i , x i ∈ X i and for all t ∈ [0, 1]. Under this technical assumption, we have:

Theorem 4.3.
Let Γ be a 2-player zero-sum game that does not admit an interior Nash equilibrium. Then, for every initial condition of (FoReL), the induced trajectory of play x(t) converges to the boundary of X . Specifically, if x * is a Nash equilibrium of Γ with maximal support, x(t) converges to the relative interior of the face of X spanned by supp(x * ).

Theorem 4.3 is our most comprehensive result for the behavior of (FoReL) in zero-sum games, so several remarks are in order. First, we note that Theorem 4.3 complements Theorem 4.2 in a very natural way: specifically, if Γ admits an interior Nash equilibrium, Theorem 4.3 suggests that the solutions of (FoReL) will stay within the relative interior X • of X (since an interior equilibrium is supported on all actions). Of course, Theorem 4.2 provides a stronger result because it states that, within X • , (FoReL) is recurrent. Hence, applying both results in tandem, we obtain the following heuristic for the behavior of (FoReL) in zero-sum games:

In the long run, (FoReL) wanders in perpetuity in the smallest face of X containing the equilibrium set of Γ.

This leads to two extremes: On the one hand, if Γ admits an interior equilibrium, (FoReL) is recurrent and cycles in the level sets of the coupling function (4.1). At the other end of the spectrum, if Γ admits only a single, pure equilibrium, then (FoReL) converges to it (since it has to wander in a singleton set). In all other "in-between" cases, (FoReL) exhibits a hybrid behavior, converging to the face of X that is spanned by the maximal support equilibrium of Γ, and then cycling in that face in perpetuity.

The reason for this behavior is that the coupling (4.1) is no longer a constant of motion of (FoReL) if the game does not admit an interior equilibrium. As we show in Appendix C, the coupling (4.1) is strictly decreasing when the support of x(t) is strictly greater than that of a Nash equilibrium x * with maximal support. When the two match, the rate of change of (4.1) drops to zero, and we fall back to a "constrained" version of Theorem 4.2. We make this argument precise in Appendix C (where we present the proof of Theorem 4.3).

4.3.

Zero-sum polymatrix games & positive affine payoff transformations. We close this section by showing that the recurrence properties of (FoReL) are not unique to "vanilla" zero-sum games, but also occur when there is a network of competitors -i.e. in N -player zero-sum polymatrix games. In fact, the recurrence results carry over to any N -player game which is isomorphic to a constant-sum polymatrix game with an interior equilibrium up to a positive-affine payoff transformation (possibly different transformation for each agent). For example, this class of games contains all strictly competitive games [START_REF] Adler | A note on strictly competitive games[END_REF]. Such transformations do not affect the equilibrium structure of the game, but can affect the geometry of the trajectories; nevertheless, the recurrent behavior persists as shown by the following result: Theorem 4.4. Let Γ = (Γ e ) e∈E be a constant-sum polymatrix game (or a positive affine payoff transformation thereof ). If Γ admits an interior Nash equilibrium, almost every solution trajectory of (FoReL) is recurrent; specifically, for (Lebesgue) almost every initial condition x(0) = Q(y(0)) ∈ X , there exists an increasing sequence of times t n ↑ ∞ such that x(t n ) → x(0).

We leave the case of zero-sum polymatrix games with no interior equilibria to future work.

Conclusions

Our results show that the behavior of regularized learning in adversarial environments is considerably more intricate than the strong no-regret properties of FoReL might at first suggest. Even though the empirical frequency of play under FoReL converges to the set of coarse correlated equilibria (possibly at an increased rate, depending on the game's structure), the actual trajectory of play under FoReL is recurrent and exhibits cycles in zero-sum games. We find this property particularly interesting as it suggests that "black box" guarantees are not the be-all/end-all of learning in games: the theory of dynamical systems is rife with complex phenomena and notions that arise naturally when examining the behavior of learning algorithms in finer detail.

Appendix A. Examples of FoReL dynamics

Example A.1 (Multiplicative weights and the replicator dynamics). Perhaps the most widely known example of a regularized choice map is the so-called logit choice map

Λ i (y) = (exp(y iαi )) αi∈Ai βi∈Ai exp(y iβi ) . (A.1)
This choice model was first studied in the context of discrete choice theory by McFadden [START_REF] Mcfadden | Conditional logit analysis of qualitative choice behavior[END_REF] and it leads to the multiplicative weights (MW) dynamics:

8 ẏi = v i (x), x i = Λ i (y i ). (MW)
As is well known, the logit map above is obtained by the model (3.2) by considering the entropic regularizer

h i (x) = αi∈Ai x iαi log x iαi , (A.2)
i.e. the (negative) Gibbs-Shannon entropy function. A simple differentiation of (MW) then shows that the players' mixed strategies evolve according to the dynamics

ẋiαi = x iαi   v iαi (x) - βi∈Ai x iβi v iβi (x)   , (RD)
This equation describes the replicator dynamics of [START_REF] Taylor | Evolutionary stable strategies and game dynamics[END_REF], the most widely studied model for evolution under natural selection in population biology and evolutionary game theory. The basic relation between (MW) and (RD) was first noted in a single-agent environment by [START_REF] Rustichini | Optimal properties of stimulus-response learning models[END_REF] and was explored further in game theory by [START_REF] Hofbauer | Time average replicator and best reply dynamics[END_REF][START_REF] Mertikopoulos | The emergence of rational behavior in the presence of stochastic perturbations[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Sorin | Exponential weight algorithm in continuous time[END_REF] and many others.

Example A.2 (Euclidean regularization and the projection dynamics). Another widely used example of regularization is given by the quadratic penalty

h i (x i ) = 1 2 αi∈Ai x 2 iαi . (A.3)
The induced choice map (3.2) is the (Euclidean) projection map

Π i (y i ) = arg max xi∈Xi y i , x i -1 2 x i 2 2 = arg min xi∈Xi y i -x i 2 2 , (A.4)
leading to the projected reinforcement learning process ẏi = v i (x),

x i = Π i (y i ). (PL)
x iα i (t + 1) = x iα i (t)e η i v iα i (x(t))

β i ∈A i x iβ i (t)e η i v iβ i (x(t)) , (MWU)
where η i > 0 is the scheme's "learning rate". For more details about (MWU), we refer the reader to [START_REF] Arora | The multiplicative weights update method: a metaalgorithm and applications[END_REF].

Proof. We begin by recalling the "maximizing argument" identity

Q i (y i ) = ∇h * i (y i ) (C.2)
which expresses the choice map Q i as a function of the convex conjugate of h i [40, p. 149]. With this at hand, a simple differentiation gives

d dt G i (y i (t)) = d dt h * i (y i (t)) -ẏi (t), p i = ẏi (t), ∇h * i (y i (t)) -p i = v i (x(t)), x i (t) -p i , (C.3)
where the last step follows from the fact that x i (t) = Q i (y i (t)) = ∇h * i (y i (t)). Armed with this lemma, we proceed to prove the no-regret guarantees of (FoReL):

Proof of Theorem 3.1. Fix some base point p i ∈ X i and let L i (t) = G i (y i (t)) h i (y i (t)) -y i (t), p i . Then, by Lemma C.1, we have

L i (t) = v i (x(t)), x i (t) -p i (C.4)
and hence, after integrating and rearranging, we get

t 0 [u i (p i ; x -i (s))-u i (x(s))]ds = t 0 v i (x(s)), p i -x i (s) ds = L i (0)-L i (t), (C.5)
where we used the fact that u i (p i ;

x -i ) = v i (x), p i -cf. Eq. (2.
2) in Section 2. However, expanding the RHS of (C.5), we get

L i (0) -L i (t) = h * i (y i (0)) -y i (0), p i -h * i (y i (t)) + y i (t), p i ≤ h * i (y i (0)) -y i (0), p i + h i (p i ) = h i (p i ) -h i (Q i (y i (0))) ≤ max h i -min h i ≡ Ω i , (C.6)
where we used the defining property of convex conjugation in the second and third lines above -i.e. that h * i (y i ) ≥ y i , x i -h i (x i ) for all x i ∈ X i , with equality if and only if x i = Q i (y i ). Thus, maximizing (C.5) over p i ∈ X i , we finally obtain

Reg i (t) = max pi∈Xi 1 t t 0 [u i (p i ; x -i (s)) -u i (x(s))] ds ≤ Ω i t , (C.7)
as claimed.

We now turn to two-player zero-sum games that do not admit interior equilibria. To describe such equilibria in more detail, we consider below the notion of essential and non-essential strategies: Definition C.2. A strategy α i of agent i ∈ {1, 2} in a zero sum game is called essential if there exists a Nash equilibrium in which player i plays α i with positive probability. A strategy that is not essential is called non-essential.

As it turns out, the Nash equilibria of a zero-sum game admit a very useful characterization in terms of essential and non-essential strategies:

Lemma C.3. Let Γ be a 2-player zero-sum game that does not admit an interior Nash equilibrium. Then, there exists a mixed Nash equilibrium (x 1 , x 2 ) such that a) each agent plays each of their essential strategies with positive probability; and b) for each agent deviating to a non-essential strategy results to a strictly worse performance than the value of the game.

The key step in proving this characterization is Farkas' lemma; the version we employ here is due to Gale, Kuhn and Tucker [START_REF] Gale | Linear Programming and the Theory of Games -Chapter XII) in Koopmans, Activity Analysis of Production and Allocation[END_REF]):

Lemma C.4 (Farkas' lemma). Let P ∈ R m×n and b ∈ R m . Then exactly one of the following two statements is true:

• There exists a x ∈ R m such that P x ≥ 0 and b x < 0.

• There exists a y ∈ R n such that P • y = b and y ≥ 0.

With this lemma at hand, we have:

Proof of Lemma C.3. Assume without loss of generality that the value of the zerosum game is zero. and that the first agent is a maximizing agent. Let A be the payoff matrix of the first agent and hence A T = A the payoff matrix of the second/minimizing agent. We will show first that for any non-essential strategy α i of each agent there exists a Nash equilibrium strategy of his opponent such that the expected performance of α i is strictly worse than the value of the game (i.e. zero). It suffices to argue this for the first agent. Let α i be one of his non-essential strategies then by definition there does not exist any Nash equilibrium strategy of that agent that chooses α i with positive probability. This is equivalent to the negation of the following statement:

There exists a x ∈ R m such that P x ≥ 0 and b x < 0 where

P = A I m×m =             a
            , (C.8) 1
and b = -e i = (0, . . . , 0, -1, 0, . . . , 0) T , the standard basis vector of dimension m that "chooses" the i-th strategy. By Farkas' lemma, there exists a y ∈ R m+n such that Py = b and y ≥ 0. It is convenient to express y = (z; w) where z ∈ R n and w ∈ R m . Hence, for all j = i ∈ {1, 2, . . . , m} : (Py) j = (Az) j + w j = 0 and thus (Az) j ≤ 0. Finally, for j = i : (Py) i = (Az) i + w i = -1 and thus (Az) i < 0. Hence z is a Nash equilibrium strategy for the second player such that when the first agent chooses the non-essential strategy α i he receives payoff which is strictly worse than his value (zero).

To complete the proof, for each essential strategy of the first agent there exists one equilibrium strategy of his that chooses it with positive probability (by definition). Similarly, for each non-essential strategy of the second agent there exists one equilibrium strategy of the first agent such that makes the expected payoff of that non-essential strategy strictly worse than the value of the game. The barycenter of all the above equilibrium strategies is still an equilibrium strategy (by convexity) and has all the desired properties. conclude that the support of x must be a subset of the support of x * . Since Γ does not admit an interior equilibrium, x * does not have full support, so every ω-limit of x(t) lies on the boundary of X , as claimed.

We close this appendix with the proof of our result on constant-sum polymatrix games (and positive affine transformations thereof):

Proof of Theorem 4.4. Our proof follows closely that of Theorem 4.2; to streamline our presentation, we only highlight here the points that differ due to working with (an positive-affine transformations of) a network of constant-sum games (as opposed to a single 2-player zero-sum game).

The first such point is the incompressibility of the "reduced" dynamics (4.6). By definition, we have u i (x) = j∈Ni u ij (x i , x j ), so we also have

v iαi (x) = j∈Ni u ij (α i , x j ).
(C.10) Since u ij (α i , x j ) does not depend on x i , we readily obtain ∂ αi v iαi (x) = 0 and incompressibility follows as before.

Let the network game in question be isomorphic to a network of constantsum games after the following positive-affine transformation of utilities, u i (x) ← a i u i (x) + b i where a i > 0. The second point of interest is the use of the coupling G(y) = i∈N a i [h * i (y i ) -y i , x * i ] as a constant of motion for (FoReL). Indeed, adapting the derivation of (C.1), we now get

dG dt = ẏ, ∇G(y) = i∈N v i (x), a i (∇h * i (y i ) -x * i ) = i∈N a i v i (x), x i -x * i = i∈N j∈Ni a i v ij (x), x i -x * i
and construct the required partition {A + , A -} according to the following procedure:

0: Set A + ← {α + }, A -= A \ A + 1: while δ α < ∞ for some α ∈ A -do 2:

pick α * such that δ α * < ∞;

3:

set A + ← A + ∪ {α * }, A -← A -\{α * };

4:

descend to a subsequence of y n that realizes δ α * ;

5:

redefine δ α for all α ∈ A based on chosen subsequence; 6: end while 7: return A + , A - Thus, if we let x n = Q(y n ) we readily obtain: where we used the fact that α∈A p α = α∈A x α,n = 1 in the first line. The first sum above is bounded by assumption. As for the second one, the fact that y α + ,n -y α,n = y + n -y α,n → ∞ implies that x α,n → 0 for all α ∈ A -(by Lemma D.1 above). We thus get lim inf n (p α -x α,n ) > 0 (recall that p ∈ ∆ • ), and hence, α∈A -(y α,n -y + n )(p α -x α,n ) → -∞. From the above, we conclude that y n , p -x n → -∞ as n → ∞. However, by construction, we also have G n = h * (y n ) -y n , x * = y n , x n -h(x n ) -y n , x * = y n , p -x n -h(x n ). (D.5) Since h is finite on x, it follows that G n → -∞, contradicting our assumption that G n is bounded. Retracing our steps, this implies that sup n |y α,n -y β,n | < ∞, as claimed.

The final result we state here is a technical result regarding the asymptotic behavior of the derivative of functions with a finite limit at infinity: Lemma D.3. Suppose that L : [0, ∞) → R is differentiable with Lipschitz continuous derivative. If lim t→∞ L(t) exists and is finite, we have lim t→∞ L (t) = 0.

Proof. Assume ad absurdum that lim t→∞ L (t) = 0. Then, without loss of generality, we may assume there exists some ε > 0 and an increasing sequence t n ↑ ∞ such that L (t n ) ≥ ε for all n ∈ N. Thus, if M denotes the Lipschitz constant of L and t ∈ [t n , t n + ε/(2M )], we readily obtain

|L (t) -L (t n )| ≤ M |t -t n | ≤ M • ε 2M = ε 2 (D.

Figure 1 .

 1 Figure1. Evolution of the dynamics of FoReL in a 3-player zero-sum polymatrix game with entropic and Euclidean regularization (left and right respectively). The game considered is a graphical variant of Matching Pennies with three players. As can be seen, the trajectories of FoReL orbit the game's line of Nash equilibria (dark red). The kinks observed in the Euclidean case occur when the support of the trajectory of play changes; by contrast, the multiplicative weights dynamics (left) are interior, so they do not exhibit such kinks.

11 a 21 .

 21

Figure 2 .

 2 Figure2. Evolution of the multiplicative weights dynamics (MW) in a 3-player zero-sum polymatrix game. In the left subfigure, each pair of players faces off in a game of standard (symmetric) Matching Pennies; in the right, the game on each pair is weighted by a different factor. In both cases, we plot the solution trajectories of (MW) for the same initial conditions. Even though the different weights change the trajectories of (MW) and the game's equilibrium set, the cycling behavior of the dynamics remains unaffected.

  y n , p -x n = α∈A y α,n (p α -x α,n ) = α∈A (y α,n -y + n )(p α -x α,n ) = α∈A + (y α,n -y + n )(p α -x α,n ) + α∈A - (y α,n -y + n )(p α -x α,n ), (D.4)

  [START_REF] Cai | Zero-sum polymatrix games: A generalization of minmax[END_REF] by the Lipschitz continuity of L . Since L (t n ) ≥ ε by assumption, we conclude that L (t) ≥ ε/2 for all t ∈ [t n , t n + ε/(2M )]. Hence, by integrating, we get L(t

n + ε/(2M )) ≥ L(t n ) + ε/(2M ) • (ε/2) = L(t n ) + ε 2 /(4M ) for all n ∈ N. Taking n → ∞ and recalling that L ∞ ≡ lim t→∞ L(t) exists and is finite, we get L ∞ = L ∞ + ε 2 /(4M ) > L ∞ , a contradiction.

In the above, we use the standard shorthand (β i ; α -i ) for the profile (α 1 , . . . , β i , . . . , α N ).

In a zero-sum game, we have γ {i,j} = 0 by default. Since the underlying interaction graph is assumed undirected, we also assume that the labeling of the players' payoff functions is symmetric. At the expense of concision, our analysis extends to directed graphs, but we stick with the undirected case for clarity.

This coupling is closely related to the so-called Bregman divergence -for the details, see[START_REF] Attouch | Singular Riemannian barrier methods and gradient-projection dynamical systems for constrained optimization[END_REF][START_REF] Kiwiel | Free-steering relaxation methods for problems with strictly convex costs and linear constraints[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF].

Specifically, Π i (y i ) = Π i (y i ) if and only if y iα i = y iα i + c for some c ∈ R and all α i ∈ A i .

The terminology "multiplicative weights" refers to the fact that (MW) is the continuous version of the discrete-time multiplicative weights update rule:

Panayotis Mertikopoulos was partially supported by the French National Research Agency (ANR) project ORACLESS (ANR-GAGA-13-JS01-0004-01) and the Huawei Innovation Research Program ULTRON. Georgios Piliouras would like to acknowledge SUTD grant SRG ESD 2015 097 and MOE AcRF Tier 2 Grant 2016-T2-1-170.

The players' mixed strategies are then known to follow the projection dynamics

over all intervals for which the support of x(t) remains constant [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF]. The dynamics (PD) were introduced in game theory by [START_REF] Friedman | Evolutionary games in economics[END_REF] as a geometric model of the evolution of play in population games; for a closely related approach, see also [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF][START_REF] Nagurney | Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria[END_REF] and references therein.

Appendix B. Liouville's formula and Poincaré recurrence

Below we present for completeness some basic results from the theory of dynamical systems.

Liouville's Formula. Liouville's formula can be applied to any system of autonomous differential equations with a continuously differentiable vector field ξ on an open domain of S ⊂ k . The divergence of ξ at x ∈ S is defined as the trace of the corresponding Jacobian at x, i.e., div[ξ(x)] = k i=1 ∂ξi ∂xi (x). Since divergence is a continuous function we can compute its integral over measurable sets A ⊂ S. Given any such set A, let A(t) = {Φ(x 0 , t) : x 0 ∈ A} be the image of A under map Φ at time t. A(t) is measurable and is volume is vol[A(t)] = A(t) dx. Liouville's formula states that the time derivative of the volume A(t) exists and is equal to the integral of the divergence over A(t):

A vector field is called divergence free if its divergence is zero everywhere. Liouville's formula trivially implies that volume is preserved in such flows.

Poincaré's recurrence theorem. The notion of recurrence that we will be using in this paper goes back to Poincaré and specifically to his study of the threebody problem. In 1890, in his celebrated work [START_REF] Poincaré | Sur le problème des trois corps et les équations de la dynamique[END_REF], he proved that whenever a dynamical system preserves volume almost all trajectories return arbitrarily close to their initial position, and they do so an infinite number of times. More precisely, Poincaré established the following:

Poincaré Recurrence: [START_REF] Barreira | Poincare recurrence: old and new[END_REF][START_REF] Poincaré | Sur le problème des trois corps et les équations de la dynamique[END_REF] If a flow preserves volume and has only bounded orbits then for each open set there exist orbits that intersect the set infinitely often.

Appendix C. Technical proofs

The first result that we prove in this appendix is a key technical lemma concerning the evolution of the coupling function (4.1):

for every trajectory of play x -i (t) of all players other than i.

With all this at hand, we are finally in a position to prove Theorem 4.3:

Proof of Theorem 4.3. We first show that the coupling

given any fully mixed initial condition strictly increases under (FoReL) when Γ is a 2-player zero-sum game that does not have an equilibrium with full support.

Indeed, by (C.3) there exists a mixed Nash equilibrium (x * 1 , x * 2 ) such that i) both players employ each of their essential strategies with positive probability over time; and ii) every player deviating to a non-essential strategy obtains a payoff lower than the value of the game. As a result, any player playing an interior (fully mixed) strategy against such an equilibrium strategy must receive less utility than their value. In more detail, we have

where we used the fact that Q i = ∇h * i in the first line (cf. Appendix D), and the assumption that x * is a Nash equilibrium of a 2-player zero-sum game such that any agent playing an interior (fully mixed) strategy against such an equilibrium strategy must receive less utility than their value (and hence the agent himself receives more utility than the value of the game). We thus conclude that G(y(t)) strictly increases under (FoReL), as claimed.

Let x * = (x * 1 , x * 2 ) be the Nash equilibrium identified in (C.9) and let

denote the primal-dual coupling (4.1) between y(t) and x * . From (C.9), we have that starting from any fully mixed strategy profile x(0) ∈ i int(X i ) and for all t ≥ 0, L (t) = ẏ(t), ∇G(y(t)) < 0. However, G is bounded from below byi max xi∈Xi h i (x i ), and since G(y(t)) is strictly decreasing, it must exhibit a finite limit.

We begin by noting that x(t) = Q(y(t)) is Lipschitz continuous in t. Indeed, v is Lipschitz continuous on X by linearity; furthermore, since the regularizer functions h i are assumed K i -strongly convex, it follows that Q i is (1/K i )-continuous by standard convex analysis arguments [START_REF] Rockafellar | Variational Analysis[END_REF]Theorem 12.60]. In turn, this implies that the field of motion V (y) ≡ v(Q(y)) of (FoReL) is Lipschitz continuous, so the dynamics are well-posed and y(t) is differentiable. Since ẏ = v and, in addition, v is bounded on X , we conclude that ẏ is bounded so, in particular, y(t) is Lipschitz continuous on [0, ∞). We thus conclude that x(t) = Q(y(t)) is Lipschitz continuous as the composition of Lipschitz continuous functions.

We now further claim that L (t) is also Lipschitz continuous in t. Indeed, by (C.1), we have L (t) = i∈N v i (x(t)), x i (t) -x * i ; since v i is Lipschitz continuous in x and x(t) is Lipschitz continuous in t, our claim follows trivially. Hence, by Lemma D.3, we conclude that lim t→∞ L (t) = lim →∞ i∈N v i (x(t), x i (t)-x * i = 0. By (C.9), we know that L (t) < 0 as long as x(t) is interior. Hence, any ω-limit x of x(t) cannot be interior (given that the embedded game does not have any interior Nash equilibria). Moreover, we can repeat this argument for any subspace such that the restriction of the game on that subspace (when ignoring the strategies that are played with probability zero) does not have a fully mixed NE. We thus

where the third line follows by regrouping the summands in the second line by edge, and the last line follows as in the case of (C.1). This implies that G(y(t)) remains constant along any solution of (FoReL), so the rest of the proof follows as in the case of Theorem 4.2.

Appendix D. Auxiliary results

In this appendix, we provide two auxiliary results that are used in the proof of Theorem 4.2. The first one shows that if the score difference between two strategies grows large, the strategy with the lower score becomes extinct: Lemma D.1. Let A be a finite set and let h be a regularizer on X ≡ ∆(A). If the sequence y n ∈ R A is such that y β,n -y α,n → ∞ for some α, β ∈ A, then lim n→∞ Q α (y n ) = 0.

Proof. Set x n = Q(y n ) and, by descending to a subsequence if necessary, assume there exists some ε > 0 such that x α,n ≥ ε > 0 for all n. Then, by the defining relation Q(y) = arg max{ y, x -h(x)} of Q, we have:

for all x ∈ ∆. Therefore, taking x n = x n + ε(e β -e α ), we readily obtain

which contradicts our original assumption that y α,n -y β,n → -∞. With ∆ compact, the above shows that x * α = 0 for any limit point x * of x n , i.e. Q α (y n ) → 0. A key step of the proof of Theorem 4.2 consists of showing that the level sets of the Fenchel coupling G(p, y) become bounded under the coordinate reduction transformation y → Π(y) = z, so every solution orbit z(t) of (4.6) also remains bounded. We encode this in the following lemma: Lemma D.2. Let A be a finite set, let h be a regularizer on X ≡ ∆(A), and fix some interior p ∈ X . If the sequence y n ∈ R A is such that sup n |h * (y n ) -y n , p | < ∞, the differences y β,n -y α,n also remain bounded for all α, β ∈ A.

Proof. We argue by contradiction. Indeed, assume that the sequence G n ≡ h * (y n )y n , p is bounded but lim sup n→∞ |y α,n -y β,n | = ∞ for some α, β ∈ A. Letting y + n = max α y α,n and y - n = min α∈A y α,n , this implies that lim sup n→∞ (y + n -y - n ) = ∞. Hence, by descending to a subsequence if necessary, there exist α + , α -∈ A such that a) y ± n = y α ± ,n for all n; and b) y α + ,n -y α -,n → ∞ as n → ∞. By construction, we have y α -,n = y - n ≤ y α,n ≤ y + n = y α + ,n for all α ∈ A. Thus, by descending to a further subsequence if necessary, we may assume that the index set A can be partitioned into two nonempty sets A + and A -such that (1) y + n -y α,n is bounded for all α ∈ A + . (2) y + n -y α,n → ∞ for all α ∈ A -. In more detail, consider the quantity δ α = lim inf n→∞ (y + n -y α,n ), (D.3)


Léo Ducas

Cécile Pierrot

Polynomial Time Bounded Distance Decoding near Minkowski's Bound in Discrete Logarithm Lattices

Keywords: Dense lattices, Bounded Distance Decoding (BDD), Minkoswki's bound, Mathematics Subject Classification (2010) 94B35, 94B65, 11H31, 11H71

We propose a concrete family of dense lattices of arbitrary dimension n in which the lattice Bounded Distance Decoding (BDD) problem can be solved in deterministic polynomial time. This construction is directly adapted from the Chor-Rivest cryptosystem (IEEE-TIT 1988).

The lattice construction needs discrete logarithm computations that can be made in deterministic polynomial time for well-chosen parameters. Each lattice comes with a deterministic polynomial time decoding algorithm able to decode up to large radius. Namely, we reach decoding radius within O(log n) Minkowski's bound, for both 1 and 2 norms.

Introduction

Sphere Packing. Given a large number of equal non-overlapping spheres, the question of finding the most efficient way to pack them together is quite an old problem. Arranging the spheres so that their centers form an Euclidean lattice (a.k.a quadratic form) helps to find solutions. For instance, in two dimensions and with the Euclidean norm, Kepler already conjectured in 1610 that the familiar hexagonal lattice solves the packing problem but the first proof was only given in 1940 by Tóth [START_REF] László | Uber einen geometrischen satz[END_REF]. However all ball arrangements are not of a lattice nature, and, with arbitrary norm and dimension, the question whether or not the best density is achieved on the lattice arrangements is still open. Yet, a classical method to find (maybe not the best but) a solution to this sphere packing problem is to aim at constructing dense lattices.

Intuitively, the density of a lattice is the proportion of the space that is occupied by maximum radius non-overlapping spheres centered in the lattice points. For instance the density of the hexagonal lattice in the plane is π/ √ 12 ≈ 0.907. Forgetting about spheres, the density λ(p) 1 (L) of a lattice L of rank n (in the p -norm) can be measured by the normalized length of its shortest vector:

λ(p) 1 (L) := λ (p)
1 (L) Vol(L) 1/n , where λ (1)

Minkowski's theorem provides an upper bound on the density of any lattice, generically:

λ(p) 1 (L) ≤ M (p) n (2)
where M n depends on dimension and norm only. In particular, for the 1 -norm (resp. 2 -norm), the density of any n-dimensional lattice is upperbounded by M

(1) n (resp. M

(2) n ) where:

M (1) n = (n!) 1/n ∼ n/e (3)
M (2) n = 2 • Γ n 2 + 1 1/n √ π ∼ 2n/πe. (4)
For the 2 norm, we know this bound to be tight up to constant factors. Indeed, there exists sequences of lattices for which λ(2)

1 (L) = Θ( √ n)
, to be compared with Minkowski's bound which has equivalent 2n/πe in this case. It is for example known that random lattices have with high probability a first normalized minima very close to this bound [START_REF] Ajtai | Generating random lattices according to the invariant distribution[END_REF]. Explicit constructions are also known, from Martinet [START_REF] Martinet | Tours de corps de classes et estimations de discriminants[END_REF] and from Shioda [START_REF] Shioda | Mordell-Weil lattices and sphere packings[END_REF][START_REF] Elkies | Mordell-Weil lattices in characteristic 2: I. construction and first properties[END_REF], the latter being known as Mordell-Weil lattices.

A simpler family A (k)

n of lattices was given by Craig (called repeated difference lattices in [CS13, Chapter 8, Section 6]), and for k = Θ(n/ log n), the minimal distance of these lattices are logarithmically close to Minkowski's bound in both 1 and 2 norms:

λ(1) 1 (A (k) n ) ≥ Θ(n/ log n) (5) λ(2) 1 (A (k) n ) ≥ Θ( √ n/ log n). (6)
Bounded Distance Decoding. The Bounded Distance Decoding (BDD) problem is the algorithmic facet of sphere packing.

Definition 1 (Bounded Distance Decoding problem in p -norm.). For a full-rank lattice L ⊂ R n , and a bounded decoding radius r (p) ≤ λ (p) 1 (L)/2, given a target:

t = v + e,
where v ∈ L and ||e|| p < r (p) , recover v and e.

As for the density we will note r(p) the normalized decoding radius r(p) = r (p) /Vol(L) 1/n . Note that the condition r (p) ≤ λ (p) 1 (L)/2 guarantees the unicity of the solution, but we cannot insure it beyond this radius. Indeed, let x be a short vector such that ||x|| p = λ (p) 1 then, for an error e = x/2, namely for an instance t = 3x/2, we cannot tell if t comes from the lattice vectors x or 2x.

The Bounded Distance Decoding problem plays a crucial role in communication over a noisy channel, as it allows to separate a codeword v ∈ L from the noise e introduced by the channel. For the square lattice Z n , this problem is trivial since we just need to round each coordinate to the nearest integer. Yet, this is far from one could hope for in term of error tolerance, since the best radius r(2) = r (2) = λ

(2) 1 (Z n )/2 = 1/2 is constant. One instead hopes to get a decoding radius as close as possible to half of Minkowski's bound, namely of the order of magnitude of √ n. Unfortunately, efficient decoding algorithm are not known for very dense lattices as random ones, Martinet's, Mordell-Weil's or Craig's lattices.

Currently, the best normalized decoding radius achievable in polynomial time was given by Micciancio and Nicolosi [START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF] over Barnes-Wall lattices BW N (of dimension n = 2 N ). It reaches the maximal decoding radius in 2 -norm and can even be efficiently extended to list-decoding [START_REF] Grigorescu | List decoding Barnes-Wall lattices[END_REF], but remains quite far from Minkowski's bound. Indeed, the maximal decoding radius r (2) = λ

(2) 1 (BW N )/2 is only such that:

r(2) = Θ( 4 √ n).
While strict BDD close to Minkowski's bound was still an open problem, a relaxed variant allowing a small probability of failure over the randomess of the error term e was recently solved by Yan et al. [START_REF] Yan | Construction of capacityachieving lattice codes: Polar lattices[END_REF] using construction D over Polar-codes.

Related Work. Quickly leaving lattices for Error Correcting Codes (ECC), we mention a recent work of Brier, Coron, Géraud, Maimut and Naccache [BCG + 15] that is very similar in spirit: they extract an efficiently decodable binary error correcting code for the Hamming weight out of Naccache and Stern's cryptosystems [START_REF] Naccache | A new public-key cryptosystem[END_REF][START_REF] Chevallier-Mames | Linear bandwidth Naccache-Stern encryption[END_REF]. Our paper explores a different notion of density coming from different metrics, namely we focus on both 1 and 2 norms instead of Hamming distance, and we do not construct a binary code but a decodable family of lattices, which can be seen as continuous error correcting codes.

While our work was rather based on the public key encryption schemes of [CR88, Len91, OTU00], these schemes, together with Naccache and Stern's ones [START_REF] Naccache | A new public-key cryptosystem[END_REF][START_REF] Chevallier-Mames | Linear bandwidth Naccache-Stern encryption[END_REF], form a common family of cryptosystems.

Relation to efficient decoding for the AWGN channel. For applications to communication over noisy channels, the noise e is typically modeled as having independent gaussian coordinates e i ∼ N (0, σ) 2 , and Minkowski's bounds translate to a maximal noise parameter σ 2 max = Vol(L) 2/n 2πe [START_REF] Poltyrev | On coding without restrictions for the awgn channel[END_REF]. In this setting, our decoding algorithms is able to decode up to a parameter σ = σ max /O(log n), except with probability exponentially small in the dimension n over the randomness of the error e.

We nevertheless note that our result is not sufficient for such applications: indeed, while we do have an efficient decoding algorithm, we do not have an efficient encoding algorithm. Namely, one would ideally be able to sample short vectors L following a discrete gaussian distribution, such as done in [START_REF] Yan | Construction of capacityachieving lattice codes: Polar lattices[END_REF]. Unfortunately, for the lattices constructed in this paper, it is not even clear how to efficiently construct a single short vector.

Contribution

In this paper, we show how to construct dense lattices admitting efficient BDD algorithm for a radius near Minkowski's bound for both 1 and 2 norms. Namely, for the 2 -norm we reach:

r(2) = Θ √ n ln n ,
to be compared with the best known radius over Barnes-Wall lattices that is Θ( 4 √ n) and with the theoretical Minkowski's bound that is equivalent to Θ( √ n). For the 1 -norm we reach:

r(1) = Θ n ln n ,
to be compared with the theoretical Minkowski's bound that is equivalent to Θ(n). Constructing a lattice and running the associated decoding algorithm have both polynomial time complexity. Moreover, we emphasize that neither the construction nor the decoding algorithm make use of a quantum computer: their construction rely on discrete logarithm computations, which can be made easy by appropriate parametrization. The construction is not so new, since it is directly inspired from deprecated knapsackbased cryptosystems first proposed in 1988 by Chor and Rivest [START_REF] Chor | A knapsack-type public key cryptosystem based on arithmetic in finite fields[END_REF][START_REF] Lenstra | On the Chor-Rivest knapsack cryptosystem[END_REF]. Their construction is based on discrete logarithm over finite-field extension, yet a very similar construction was proposed by Okamoto et al. [START_REF] Okamoto | Quantum publickey cryptosystems[END_REF] relying merely on discrete logarithm of modular integers. For ease of presentation, we base ourselvesz on the later.

The core idea behind those cryptosystems is that the subset-prime-product problem over the integers is an easy problem. More precisely, if p 1 , . . . , p m ≤ B are primes, given t = p e i i mod m for positive integers e i , and assuming B ||e|| 1 ≤ m, recovering e can easily be done by trial divisions. Taking discrete logarithms allows to convert this to a subset-sum problem, that was the underlying hard problem of these protocols.

Ignoring the cryptographic countermeasures making this subset-sum instance hard to an adversary, we re-interpret this construction as a lattice error-correction scheme. This construction is done in Paragraph 3.1. Discrete logarithm computations occur while constructing such a lattice, but they can be made easy by appropriate choice of m, and do not need any quantum computer algorithm.

In order to decode such a lattice, the only remaining technicality to be dealt with is the fact that, in these previous protocols, the decoded error e is assumed to have positive integer coefficients. The integrality condition is easily solved by rounding. The positivity condition can also be removed by rational reconstruction, i.e. solving the shortest-vector problem in dimension 2. Our decoding algorithm is detailed in Paragraph 3.2. In Paragraph 3.3 we propose concrete well-chosen parameters to build a family of dense lattices with polynomial time decoding algorithms. Finally in Section 4 we discuss about some generalizations of the scheme that could help in practice to obtain better decoding radius -but all these slight changes do not interfere with our asymptotic results.

Preliminaries

Notation. In the sequel, if x ∈ R n is a vector, then x i denotes its i-th coordinate. The p -norm of a vector x is noted ||x|| p , and is defined by ||x|| p = ( |x i | p ) 1/p . Moreover we denote by x the coefficient-wise rounding to Z n . Useful inequalities. We make use of the following statements:

∀x ∈ R n , ||x|| 1 ≤ √ n • ||x|| 2 . (7) ∀x ∈ R n , || x || 1 ≤ 2||x|| 1 . (8)
Inequality ( 7) is an application of Cauchy-Schwarz's inequality in the Euclidean space R n . Besides, Inequality (8) comes from inequality | y | ≤ 2|y| for any real number y.

Factoring.

Definition 1. Let B be a natural integer. An integer is B-smooth if all its factors are lower or equal to B.

Factoring is considered as a hard problem in cryptography. Yet, when we know we have a smooth number, it becomes much more easy to factorize it.

Proposition 1 (Factorisation by trial division). If B is a natural integer and n a B-smooth integer with k factors, then one can find the whole factorization of n with complexity:

O(B • k • (log n) 2 ).
Proof. Let n be the target number we want to factorize. With these hypotheses, the simplest algorithm consists in trying all prime p lower than B and to see if it factors n or not. If it does, we pursue with the quotient n/p. The algorithm ends when we have found all its k factors (with multiplicity). Each trial division costs O((log n) 2 ) bit operations. Note that this exponent 2 depends on the underlying multiplication algorithm, so it can be improved with fast algorithms.

Remark 1. If B gets large, algorithms such as Pollard-ρ [START_REF] Pollard | Monte Carlo methods for index computations mod p[END_REF], or even Lenstra's Elliptic Curve Method [START_REF] Lenstra | Factoring integers with elliptic curves[END_REF] will eventually become much faster for factorization. Yet for our application B will be no larger than Θ(n log n) where n is the dimension of the considered lattice: it is plausible that trial division remains the fastest method for parameters of interest.

Discrete Logarithm. As for factoring, computing discrete logarithms in a group that has a smooth order is easier than in a generic group of the same order of magnitude. It comes from the fact that Pohlig-Hellman algorithm [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.)[END_REF] helps to reduce the problem to computing discrete logarithms in all the subgroups, so that the main parameter to discuss with the hardness of computing discrete logarithms is not the size of the group itself, but the size of its largest subgroup of prime order. This remark will help to construct a family of lattices without being bothered by these computations. More precisely: Proposition 2. For any group G of order p a i i , where the p i 's' are distinct prime numbers, using a combination of Pohlig-Hellman [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.)[END_REF] and Pollard-ρ [START_REF] Pollard | Monte Carlo methods for index computations mod p[END_REF] algorithms permits to compute discrete logarithms in G in:

O a i (ln(|G|) + √ p i )
group operations.

3 Discrete logarithm based family of lattices

Settings and construction

Let us fix n a natural integer and m an integer such that (Z/mZ) * is a cyclic group.

ψ : Z n → (Z/mZ) * (x 1 , • • • , x n ) → n i=1 p x i i mod m.
1 Later we relax this assumption and discuss about m.

The lattice of multiplicative relation between p 1 , • • • , p n is defined as:

L := ker ψ = x = (x 1 , • • • , x n ) ∈ Z n | n i=1 p x i i = 1 mod m .
As L is a full rank sublattice of Z n , we have Vol(L) = |Z n /L| = | Im ψ|. In consequence Vol(L) ≤ ϕ(m), with equality if and only if ψ is surjective. Calling g a generator of the multiplicative cyclic group (Z/mZ) * , we see that L is a lattice of dimension n that can be rewritten as:

L = x = (x 1 , • • • , x n ) ∈ Z n | n i=1 x i log g p i = 0 mod ϕ(m) . (9)
Note that the above equation holds independently of the choice of the generator g. If one of the prime p ∈ F is a generator of (Z/mZ) * we are even able to explicit a basis of this lattice. Indeed, let's assume that g = p n is a generator of (Z/mZ) * . An explicit basis of L can be constructed as the row vectors of the following matrix:

M =        1 -log g p 1 1 -log g p 2 . . . . . . 1 -log g p n-1 ϕ(m)       
where blank entries should be read as 0. Indeed, by definition of the discrete logarithm, we have p i • g -log g p i = p i • p -1 i = 1 mod m, so each row M belong to L (for the last row, one needs to resort to Fermat's theorem). Note that p n = g is a generator of (Z/mZ) * , therefore the morphism ψ is surjective, which imply Vol(L) = φ(m). Since det(M ) = φ(M ) = Vol(L), we conclude that M is indeed a basis of L.

Explicit bases can also be efficiently constructed without the assumption that p n generates (Z/mZ) * but requires more care. We emphasize that the volume of L is then not necessarily equal to ϕ(m), but cannot be larger.

Remark 2. Thus to explicitly construct the basis we need to compute all the discrete logarithms in F modulo ϕ(m). We will discuss about complexity and efficiency in Section 3.3, while choosing some relevant parameters.

Decoding algorithm

Beware that in this Section 3.2 all the radiuses are taken without any consideration of the volume -namely, they are not normalized yet.

Positive discrete errors in 1 -norm

In this paragraph we present how to recover x from a given vector t = x + e where:

• x ∈ L
• e is a positive discrete bounded error, namely e ∈ N n such that ||e|| 1 r (1) N , for some yet to determine bound r

(1) N .

The first step of the decoding algorithm consist in computing the following product modulo m:

n i=1 p t i i = n i=1 p x i i n i=1 p e i i = n i=1 p e i i mod m.
From ||e|| 1 r

(1)

N and p B for any p ∈ F we get n i=1 p e i i B r (1) N . Efficient decoding can be ensured up to the following 1 radius:

r (1) N = ln m ln B . ( 10
)
Indeed, in that case, B r (1) N = m so the product n i=1 p e i i , which is lower than m, can be computed in Z, and not only modulo m. Then we factorize this integer, which is easy since it's a smooth number. From this factorization we recover the error vector e.

Discrete errors in 1 -norm

If e is again a discrete bounded error such that ||e|| 1 r

(1)

Z , but without any constraint on the sign of its coefficients, namely e ∈ Z n , we need to slightly change the decoding algorithm. Here we compute again f = n i=1 p t i i mod m, yet this is no longer equal to a product but to a fraction of the form:

f = n i s.t. e i >0 p e i i • i s.t. e i <0
p e i i = u/v mod m.

To recover u = n i s.t. e i >0 p e i i and v = i s.t. e i <0 p -e i i not only modulo m but in Z, we use the following rational reconstruction Lemma, already stated in [BCG + 15]. Lemma 1. If u, v are positive coprime integers and invertible modulo m such that u, v < m/2, and if f = u/v mod m, then ±(u, v) are the shortests vector of the 2-dimensional lattice L = {(x, y) ∈ Z 2 |x -f y = 0 mod m} for the 2 -norm.

In particular, given f and m, one can recover (u, v) in polynomial time.

Proof. Let us assume that there exists a non-zero vector (u , v ) ∈ L shorter than (u, v). First note that (u , v ) ∈ L ⊂ Z 2 must be R-linearly independent of (u, v), since u and v are coprime. Indeed, since (u, v) are coprime, we have (u, v)R ∩ Z 2 = (u, v)Z. Now consider the lattice L generated by (u, v) and (u , v ). Because L is a full-rank sublattice of L we have Vol(L ) ≥ Vol(L). Since (f, 1) and (m, 0) form a basis of L we have Vol(L) = m. It leads to:

Vol(L ) ≥ m.

On the other hand, by Hadamard inequality we have:

Vol(L ) ≤ ||(u, v)|| 2 • ||(u , v )|| 2 ≤ ||(u, v)|| 2 2 < m.
By contradiction this concludes that ±(u, v) are the shortest vectors of L. The vector (u, v) is then easy to recover in polynomial time since L has a fixed dimension 2, for example using Gauss' algorithm (also known as Lagrange's algorithm).

Having recovered the vector (u, v), it remains to recover e by factorization of u and v. In conclusion, we have a decoding algorithm for any integer errors up to 1 radius:

r (1) Z = ln(m/2) 2 • ln B . (11)
Indeed, an error bounded by this radius ensures u and v to be strictly lower than m/2.

Continuous error in 1 -norm

The generalization to continuous error is rather straightforward, and consists simply in first rounding the target t coordinate-wise, to reduce the problem to the discrete case. Indeed, let t = x + e where x ∈ L and e is a small error. Set t = t , and note that since x ∈ L ⊂ Z n , we have t = x + e . Applying the previous decoding algorithm to t will yield the correct answer

x if || e || 1 ≤ r (1) Z .
Recalling Inequality (8): || x || 1 ≤ 2||x|| 1 , we conclude that this algorithm provides a 1 decoding radius r (1) = r

(1) Z /2, namely:

r (1) = ln(m/2) 4 • ln B . (12)
3.2.4 Continuous error in 2 -norm Inequality (7) ensures that the above algorithm also decodes errors up to 2 radius r (2) = r (1) / √ n, namely:

r (2) = ln(m/2) 4 √ n • ln B . ( 13
)
Remark 3 (Generalization to p -norm). Even if the Euclidean norm (or 2 -norm) is of major interest in practice while dealing with BDD, note that the key of our algorithm is to decode in 1 -norm. Actually we could generalize this decoding to any norm, by relying on inequality ||x|| 1 ≤ n (p-1)/p ||x|| p that is true for any x ∈ R n . As in Paragraph 3.2.4 above, it yields a decoding algorithm for errors up to p radius:

r (p) = ln(m/2) 4n (p-1)/p • ln B .
Remark 4. As for lattice construction, the asymptotic complexity of this algorithm is detailed later for some well-chosen parameters.

3.3 A family of lattices approaching Minkowski's bound.

Proposition 3. For every natural integer n, we are able to construct in polynomial time an n-dimensional lattice with a polynomial time algorithm decoding errors up to normalized decoding radius:

r(2) = Θ √ n ln n
, for the Euclidean norm, and r(1) = Θ n ln n , for the 1 -norm.

In both 1 and 2 norms we reach Minkowski's bound up to logarithmic factors. Indeed the normalized radius of Proposition 3 needs to be compared with Minkowski's bounds M where c is a constant given by Equation (3). Moreover, we only use classical algorithms so there is no need to have a quantum computer to construct the lattice or decode it.

Proof. Efficient construction. Let q be a prime number such that q 3, and n > 0 a natural integer. Take: m = q n . Theorem 1. The group (Z/mZ) * is cyclic if and only if m is 1, 2, 4, q k or 2q n , where q is an odd prime and n > 0 a natural integer. For all other values of m the group is not cyclic.

Theorem 1 (see for instance [Sha93, page 92] for more details) indicates that G = (Z/mZ) * is a cyclic group of order ϕ(m) = (q -1)q n-1 . Now consider the lattice L defined by (9). We define B as the (n + 2)-th prime number, so that F precisely has order n. In the sequel we use an equivalent for B which is easier to manipulate than the formal definition. We have B ∼ (n + 2) log(n + 2) so:

B ∼ n log n. ( 14
)
To explicitly construct L we need to find n discrete logarithms modulo ϕ(m). Namely if g is a generator of G and if )) group operations. Plugging with our value |G| = ϕ(m) = (q -1)q n-1 we obtain one of these discrete logarithms in quadratic time with respect to n. Thus, we are able to construct the lattice L in cubic time. Again, it's the extremely high smoothness of m that makes this computation feasible.

F = {p 1 , • • • , p n },
Decoding a large ball. From Section 3.2 we can decode up to 1 -radius (resp. 2 -radius) r (1) (resp. r (2) ) given as in Equation (12) (resp. Equation ( 13)). To conclude we just need to compute the two corresponding normalized radius r(i) = r (i) /Vol(L) 1/n for i = 1, 2. From Vol(L) ≥ ϕ(m) we are able to decode up to: r(2) = ln(m/2) 4((q -1)q n-1 ) 1/n √ n • ln B and r(1) = ln(m/2) 4((q -1)q n-1 ) 1/n • ln B .

From log m ∼ n and B ∼ n ln n we have:

r(2) = Θ √ n ln n and r(1) = Θ n ln n .
To deal with complexity, we recall that our decoding algorithm is simply:

1. Rounding a n-dimensional vector (namely t)

2. Computing a product modulo m (namely f ) 3. Finding the shortest vector of a 2-dimensional integer lattice (namely (u, v))

4. and Factoring two B-smooth integers (namely u and v).

The first step is linear in n. The second one is linear as well. Thanks to Lemma 1 the third one is polynomial. Concerning the last step, in order to factor u for instance, plugging k = ||e|| 1 in Proposition 1 make the complexity become O(B • ||e|| 1 • (log u) 2 ). From (14), ||e|| 1 < r (1) , r (1) = O(n), u < m and log m = O(n) we get at worst a complexity in O(n 4 ln(n)) for factoring the two B-smooth integers. Thus, our whole decoding algorithm for both 1 and 2 norms runs in polynomial time.

Generalizations

For a fixed n, in the previous discussion the size of the normalized radius up to which we are able to decode varies with the ratio: ln m ϕ(m) .

Here comes some variants that could help in practice to increase a bit this quantity. First one can notice that, according to Theorem 1, choosing m = 2q n instead of m = q n maintain the cyclicity and the size of the group (Z/mZ) * , sligthly improving the ratio ln m/ϕ(m).

Construction in a non-cyclic multiplicative group

In Section 3.1 we make the assumption that m is chosen such that (Z/mZ) * is a cyclic group. Indeed, we can deal with more general constructions where m has no special form, except that it is not divisible by 8. Let's write its factorisation:

m = k i=1 p e i i
where p i are prime numbers and e i natural integers. If (Z/mZ) * is not cyclic then there is no generator, and talking about discrete logarithm may seem meaningless. Yet thanks to the Chinese Reminder Theorem:

(Z/mZ) * k i=1 (Z/p e i i Z) * .
For all p i > 2 we know from Theorem 1 that (Z/p e i i Z) * is cyclic. If p i = 2 then as soon as e i = 0 or e 1 = 1 the corresponding group is still cyclic. In these cyclic groups we can define a discrete logarithm modulo their order. To construct our lattice we just need to define the discrete logarithm of an element in (Z/mZ) * as a k-dimensional vector where its coordinates are the discrete logarithms of its image in each cyclic group. Namely, the function log is here defined as a morphism: log : (Z/mZ) * → k i=1 (Z/ϕ(p e i i )Z).

To put it in a nutshell, our construction works as soon as m is not divisible by 8. This permits to increase a bit the previous ratio: indeed, for two integers m of the same order of magnitude, ϕ(m) decreases as m gets more and more smooth.

Adapting the construction to Finite Fields

We have described a construction based on the multiplicative group (Z/mZ) × , but the original construction of Chorr and Rivest was working over the multiplicative group of a finite field extension F × p d . The drawback is that while the decoding algorithm remains polynomial time, the explicit construction of the lattice (computation of discrete logarithm) is not polynomial time anymore; though it can heuristically be made quasi-polynomial time [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF]. This drawback can be cicumvented by resorting to product of finite fields, as recently done in the cryptosystem of Li et al. [START_REF] Li | On the closest vector problem for lattices constructed from polynomials and their cryptographic applications[END_REF].

Nevertheless, asymptotically we were not able to decode better radii with such constructions.

  ) := min x∈L\{0} ||x|| p .

n

  ) denotes the volume of the unit ball in p -norm in R n . Note that this Minkowski's bound M (p)

  for the Euclidean norm, and Θ(n),for the 1 -norm,

1

  Recall that the size of the group (Z/mZ)

* is ϕ(m), where ϕ denotes Euler's totient function. Now let B be a natural integer depending on n such that the set of prime numbers F ⊂ N defined as:

F = {p ∈ N | p

prime, p does not divide m and p B}, has exactly n elements p 1 , • • • , p n . Recall that the k-th prime number is asymptotically equivalent to k log k. Thus we have B ∼ n log n asymptotically. Now, consider the group morphism:

  then we compute all log g p i for i = 1, • • • , n. To compute one of these discrete logarithms we use a combination of Pohlig-Hellman [PH78] and Pollard-Rho [Pol78] algorithms. Proposition 2 underlines that for any group G of order t a i i this can be done in O( t i /|G | a i (ln(|G |) +

	√	t i

Acknowledgment

We would like to thank Steven Galbraith, Cong Ling, Dan Shepherd and Chaoping Xing for their interesting discussions and precious comments about this work. We are also grateful for the helpful comments of the anonymous reviewers of Design, Code and Cryptography.

Supported by a Veni Innovational Research Grant from NWO under project number 639.021.645.