Cássio F Dantas
email: cassio.fraga-dantas@inrae.fr

Emmanuel Soubies

Fellow, IEEE Cédric Févotte

Sphere Refinement in Gap Safe Screening

Keywords: Sparse optimization, Safe screening, Kullback-Leibler regression, Logistic regression

The Gap safe screening technique is a powerful tool to accelerate the convergence of sparse optimization solvers. Its performance is largely based on the ability to determine the smallest "sphere", centered at a given feasible dual point, that contains the dual solution. This can be achieved through an inner sphere refinement loop, applied at each screening step. In this work, we show that this refinement loop actually converges to the solution of a fixed-point equation for which we derive a closed-form expression for two common loss functions. This allows us to develop an analytic (i.e., non iterative), more concise and theoretically-grounded variant of the sphere refinement step.

I. INTRODUCTION

S PARSE optimization problems are encountered in fields such as signal processing, inverse problems, statistics, and machine learning. A very common formulation is given by

x ∈ argmin x∈C P λ (x) := m i=1 f i ([Ax] i ) + λ x 1 (1)
where A ∈ R m×n , C ∈ {R n , R n ≥0 }, λ > 0, and each scalar function f i : R → R ∪ {+∞} is proper convex, and differentiable. As such, numerous algorithms have been developed to tackle problems of the form [START_REF] Combettes | Signal recovery by proximal forwardbackward splitting[END_REF]. These include, but are not limited to, proximal gradient [START_REF] Combettes | Signal recovery by proximal forwardbackward splitting[END_REF]- [START_REF] Harmany | This is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms-Theory and Practice[END_REF], coordinate descent [START_REF] Fu | Penalized regressions: The bridge versus the lasso[END_REF], [START_REF] Yuan | A comparison of optimization methods and software for large-scale l1-regularized linear classification[END_REF], and majorization-minimization [START_REF] Figueiredo | Majorization-minimization algorithms for wavelet-based image restoration[END_REF] methods.

Within this context, the promise of safe screening is to identify zero coordinates in x so as to reduce the size of the problem and, consequently, accelerate the convergence of the solver. This identification can be performed before or within the course of iterations, leading respectively to the so-called static [START_REF] Ghaoui | Safe feature elimination for the lasso and sparse supervised learning problems[END_REF] and dynamic [START_REF] Bonnefoy | Dynamic screening: Accelerating first-order algorithms for the lasso and grouplasso[END_REF] screening approaches. Although originally proposed for the Lasso problem [START_REF] Ghaoui | Safe feature elimination for the lasso and sparse supervised learning problems[END_REF] (i.e., f i (z) = (y i -z) 2 where y i is the ith entry of a data vector y ∈ R m ), safe screening techniques have then been extended to a large variety of sparse-regularized problems [START_REF] Bonnefoy | Dynamic screening: Accelerating first-order algorithms for the lasso and grouplasso[END_REF]- [START_REF] Dantas | Safe Screening for Sparse Regression with the Kullback-Leibler Divergence[END_REF]. The case where the 1 -norm in [START_REF] Combettes | Signal recovery by proximal forwardbackward splitting[END_REF] is replaced by a generic group separable norm has also been treated in [START_REF] Ndiaye | Gap safe screening rules for sparsity enforcing penalties[END_REF], [START_REF]Expanding boundaries of Gap Safe screening[END_REF].

Notations: We let [n] = {1, . . . , n}. For a vector x ∈ R n , we denote x i its ith entry. Given a subset of indices g ⊆ [n] with cardinality |g| = n g , x g ∈ R ng is the restriction of x to its elements indexed by g. For a matrix A, we similarly define the restrictions a j and A g with respect to the columns of A.

The complement of A ⊆ [n] is denoted A c = [n] \ A.
Safe Screening in a Nutshell: Safe screening techniques rely on the first-order primal-dual optimality conditions of [START_REF] Combettes | Signal recovery by proximal forwardbackward splitting[END_REF]. More precisely, we get the key property that [START_REF] Ghaoui | Safe feature elimination for the lasso and sparse supervised learning problems[END_REF], [START_REF]Expanding boundaries of Gap Safe screening[END_REF] ∀j ∈

[n], |φ(a T j θ )| < 1 =⇒ x j = 0, (2)
where

φ(x) = x if C = R n or φ(x) = max(x, 0) if C = R n ≥0 , and θ * ∈ R m is the solution of the dual problem θ = argmin θ∈∆ A D λ (θ) := - m i=1 f * i (-λθ i ). (3)
In the dual formulation (3), f * i stands for the Fenchel-Legendre conjugate of f i while

∆ A := {θ ∈ R m | ∀j ∈ [n], |φ(a T j θ)| ≤ 1} ∩ dom(D λ
) corresponds to the dual feasible set, with dom(D λ ) denoting the domain of the dual function.

One sees from (2) that the knowledge of θ allows us to identify zero coordinates in x . Yet, this is not practical as θ is unknown. The main task in safe screening is thus to define a safe region S θ from which we can derive the following safe screening rule for the jth component

max θ∈S |φ(a T j θ)| < 1 =⇒ |φ(a T j θ )| < 1 =⇒ x j = 0. (4)
Clearly, in order to maximize screening performance, the safe region S should be as small as possible (to increase the number of screened variables) while allowing an efficient computation of the screening test given by max θ∈S |φ(a T j θ)| < 1 (to minimize the computational overhead).

Among existing safe regions, the Gap safe sphere [START_REF] Ndiaye | Gap safe screening rules for sparsity enforcing penalties[END_REF] leads to state-of-the-art screening performance. Given any primaldual pair (x, θ), it reads as S = B(θ, 2Gap λ (x, θ)/α R m ), where Gap λ (x, θ) = P λ (x) -D λ (θ) ≥ 0 and α R m > 0 corresponds to the strong concavity constant of D λ over R m . Not only is its geometry simple (allowing fast screening tests), but its radius vanishes upon convergence of the primal-dual iterates when strong duality holds (i.e., Gap λ (x , θ ) = 0). Yet, it requires the dual function D λ to be globally strongly concave which precludes its use for an important class of functions f i such as the β-divergences with β ∈ [1, 2) [START_REF] Févotte | Algorithms for nonnegative matrix factorization with the β-divergence[END_REF].

In a previous work [START_REF]Expanding boundaries of Gap Safe screening[END_REF], we overcame this limitation by computing local strong concavity bounds on well-chosen subsets of the domain. Moreover, by re-evaluating the strongconcavity bound on the current safe sphere, we proposed a sphere refinement loop that improves screening performance.

Contributions: In this letter, we scrutinize the sphere refinement loop proposed in [START_REF]Expanding boundaries of Gap Safe screening[END_REF] and recalled in Sec. II. We prove that it converges to the solution of a fixed-point equation (Proposition 1). This allows us to derive a new algorithm that is exempt of the inner loop, when the fixed-point equation admits a closed-form solution (Alg. 2). We derive in Sec. IV such closed-from expressions for two popular loss functions: the Kullback-Leibler (KL) divergence and the logistic function. Numerical evaluations are reported in Sec. V. Finally, all proof are deferred to the Supplementary Material.

Algorithm 1 GSS with iterative sphere refinement [START_REF]Expanding boundaries of Gap Safe screening[END_REF] 1: Inputs:

x 0 ∈ C, ε gap > 0 2: A ← [n], S 0 ← ∆ A , ε r ← 10 -3 3: repeat (loop over k) 4:
Primal and Dual updates 5:

x k A ← PrimalUpdate(x k-1 A , A A ), x k A c ← 0 6: θ k ← DualUpdate(x k ) ∈ ∆ A 7:
Safe region with iterative refinement 8:

S ← S k-1

9:

if θ k / ∈ S then Inflate previous safe region 10:

S ← B θ k-1 , θ k -θ k-1 11: end if 12: S k ← B θ k , 2 Gap λ (x k ,θ k ) α S
Init. safe region 13:

if α S k > α S then 14:

α 0 ← α S k 15:
repeat (loop over j) Sphere refinement 16:

r j ← 2 Gap λ (x k , θ k ) /αj-1 17: α j ← α B(θ k ,rj )
18:

until |r j -r j-1 | < ε r • r j-1
19:

S k ← B(θ k , r j ) 20:
end if

21:

Screening

22: A ← {j ∈ A| max θ∈S k |φ(a T j θ)| ≥ 1} 23: until Gap λ (x k , θ k ) ≤ ε gap II.
GSS WITH ITERATIVE SPHERE REFINEMENT The Gap safe screening (GSS) with iterative sphere refinement proposed in [START_REF]Expanding boundaries of Gap Safe screening[END_REF] is recalled in Alg. 1. There, PrimalUpdate (resp., DualUpdate) refers to the update step of any iterative primal (resp., dual) solver for (1) (resp., (3)). Given a subset S ⊂ R m , α S stands for the strong concavity constant of D λ over S, i.e., a lower bound on f * i over S and ∀i ∈ [m] (c.f. [START_REF] Dantas | Supplementary Material to Sphere Refinement in Gap Safe Screening[END_REF], [START_REF]Expanding boundaries of Gap Safe screening[END_REF]Proposition 11]). Then, the construction of the safe region, starting at line 7, is made of three steps.

• First, if the new dual point does not belong to the previous safe region, the latter is inflated (Line 10) to make the next step possible with θ k ∈ S. • Second, as θ k ∈ S, Theorem 5 in [START_REF]Expanding boundaries of Gap Safe screening[END_REF] can be invoked to build a new safe region centered at θ k using α S (Line 12). • Third, if the strong concavity constant over this new safe region improves (Line 13), this safe region is iteratively refined (lines [START_REF] Johnson | Discovering Discrete Dynamical Systems[END_REF][START_REF] Granas | Fixed point theory[END_REF][START_REF] Globerson | Euclidean Embedding of Co-occurrence Data[END_REF][START_REF] Tseng | A coordinate gradient descent method for nonsmooth separable minimization[END_REF]. From [START_REF]Expanding boundaries of Gap Safe screening[END_REF]Proposition 7], this refinement loop generates a sequence of nested Gap safe spheres (i.e., with decreasing radius), all centered in θ k . Finally, the refined safe region is used at Line 22 to safely screen out zero-coordinates of the solution vector x .

III. GSS WITH ANALYTIC SPHERE REFINEMENT

The proposed Gap safe screening with analytic sphere refinement is presented in Alg. 2. Its main novelties with respect to Alg. 1 are outlined in the next three sections.

A. Tracking the Best Strong Concavity Constant

As opposed to Alg. 1, in Alg. 2 we keep track of the safe region S b over which the best (i.e., largest) constant α S b has Algorithm 2 Proposed GSS with analytic sphere refinement 1: Inputs:

x 0 ∈ C, ε gap > 0 2: A ← [n], S b ← ∆ A 3: repeat (loop over k) 4:
Primal and Dual updates 5:

x k A ← PrimalUpdate(x k-1 A , A A ), x k A c ← 0 6: θ ← DualUpdate(x k ) ∈ ∆ A 7: θ k ← P S b ( θ) Projection onto S b (c.f. [14]) 8:
Safe region with analytic refinement 9:

S k ← B θ k , 2 Gap λ (x k ,θ k ) α S b
Init. safe region 10:

if θ k -θ S b > r S k -r S b then 11:
if ᾱk > α S b then ᾱk fixed-point of (8)

12:

S k ← B θ k , 2 Gap λ (x k ,θ k )
A ← {j ∈ A| max θ∈S k |φ(a T j θ)| ≥ 1} 18: until Gap λ (x k , θ k ) ≤ ε gap
been computed so far. As such, we ensure the construction of a non-decreasing sequence of strong concavity constants. Then, to ensure that the new dual point θ k belongs to S b , we replaced the inflation step at Line 10 of Alg. 1 by the projection step at Line 7 of Alg. 2. The benefit of this modification is twofold.

• It discards the need of recomputing the strong concavity constant (on the inflated region) before refinement. • It leads to improved dual points. Indeed, given that S b is convex and θ ∈ S b , we have for all θ ∈ ∆ A P S b ( θ) -

θ 2 ≤ θ -θ 2 .

B. Avoiding Unnecessary Refinement Attempts

In Alg. 2, we added the test at Line 10 to avoid unnecessary refinement attempts. Indeed, one can see that the refinement step will improve the initial kth Gap safe sphere

S k = B θ k , r k with r k = 2 Gap λ (x k , θ k ) α S b , (5)
only if α S k > α S b (i.e., the strong concavity constant on the new S k is better than the best one α S b computed so far).

From the definition of strong concavity, 1 we can thus derive the following three situations (illustrated in Fig. 1 (a-c)),

• Improvement if S k ⊆ S b =⇒ α S k ≥ α S b • No Improvement if S k ⊇ S b =⇒ α S k ≤ α S b • Indecisive otherwise.
A typical situation of improvement arises when the duality Gap (and thus the radius) decreases more than the displacement of the dual point from one iteration to the next. Indeed, let θ S b ∈ ∆ A and r S b > 0 denote respectively the center and the radius of S b , then S k ⊆ S b is equivalent to (see Fig. 1-a) Similarly, we get that S k ⊇ S b (i.e., no improvement case) is equivalent to

θ k -θ S b ≤ r S b -r k . (6)
θ k -θ S b ≤ r k -r S b . (7)
Hence, the complement of ( 7) includes all improvement and indecisive cases (see Fig. 2). It can be used as a test that does not require to compute any strong concavity constant to decide whether to perform the refinement step (Line 10 of Alg. 2). Yet, a second test involving strong concavity constants (Line 11 of Alg. 2) is required to deal with indecisive cases.

C. Dropping the Refinement Loop

In Proposition 1, we prove that the sequence of strong concavity constants generated by the refinement loop at lines 15-18 of Alg. 1 converges to the solution ᾱk of a fixed-point equation. This is illustrated in Fig. 1 (d-e). As such, provided that one has access to a closed-form expression for ᾱk (see Sec. IV), the refinement is no longer iterative, as implemented at Line 12 of Alg. 2.

Proposition 1 (Fixed point equation). Assume that D λ is twice differentiable and let (x k , θ k ) ∈ C × ∆ A be the kth primaldual iterate pair and

G k := Gap λ (x k , θ k ). Define h k (α) = min i∈[m] inf θi∈B(θ k i , 2G k α )∩dom f * i (-λ•) λ 2 f * i (-λθ i ) (8)
with unconstrained inf when α = 0. Then, the refinement loop (lines 15-18 in Alg. 1) converges to the safe region S k = B θ k , 2G k /ᾱ k with ᾱk a non-repelling2 fixed point of h k .

IV. CLOSED-FORM EXPRESSIONS OF FIXED POINTS

The practical relevance of Alg. 2 depends on our ability to derive closed-form expressions of fixed points of h k in [START_REF] Bonnefoy | Dynamic screening: Accelerating first-order algorithms for the lasso and grouplasso[END_REF]. We show that this is possible for two very common loss functions. More general properties of h k are given in [START_REF] Dantas | Supplementary Material to Sphere Refinement in Gap Safe Screening[END_REF]Sec. 1.3].

A. Kullback-Leibler Divergence

Here, the scalar data-fidelity functions f i and their convex conjugates are given by:

f i (z) = y i log (y i /(z + )) + z + -y i , (9)
f * i (u) = -y i log(1 -u) -u, (10)
where y i is the ith entry of the data vector y ∈ R m ≥0 , > 0 is a smoothing factor that avoids singularities around zero and

dom(f * i ) = {u ∈ R | u ≤ 1}. Finally, in this case we have C = R n ≥0 , and A ∈ R m×n ≥0 . Proposition 2. Assume that y i > 0 for all i ∈ [m]. Let (x k , θ k ) ∈ R n ≥0 × ∆ A and G k := Gap λ (x k , θ k ). Then, h k in (8) with f * i in (
with ᾱk i =        0 if G k ≥ y i 2 λ 2 √ y i - √ 2G k 2 (1 + λθ k i ) 2 otherwise. (12)
Remark 1. Following [12, Sec. 4.2.2], Proposition 2 can be generalized to the situation where there exists i ∈ [m] such that y i = 0. This is achieved by searching for the min in (11) within I 0 rather than [m], where

I 0 = {i ∈ [m] | y i = 0}.

B. Logistic Function

For an input signal y ∈ R m , the data-fidelity functions f i and their convex conjugates f * i are given by:

f i (z) = log (1 + e z ) -y i z (13) f * i (u) = (y i +u) log(y i +u) + (1-y i -u) log(1-y i -u) with dom(f * i ) = {u ∈ R | 0 ≤ u + y i ≤ 1} = [-y i , 1 -y i ]. In this case, we have C = R n . Proposition 3. Let (x k , θ k ) ∈ R n × ∆ A and G k := Gap λ (x k , θ k ). Then h k in (8) with f * i in (13) has a unique
τ i = |λθ k i -y i + 1 2 | ≤ 1 2 , ᾱk i =                4λ 2 if G k ≥ 2τ 2 i λ 2 (2G k + 1) 2 2G k if G k < 2τ 2 i and τ i = 1 2 -4τiλ √ 2G k +2λ √ 2G k +1-4τ 2 i 1-4τ 2 i 2 if G k < 2τ 2 i and τ i < 1 2 (14)

C. Complexity Analysis

The computation of the fixed point from the closed-form expressions derived in propositions 2 and 3 is of the order of O(m) (due to the min operations). This is about the same complexity as for the evaluation of the strong concavity constant on any ball [12, Table 1]. As such, denoting by P the number of sphere refinement iterations in Alg. 1, the analytic version of Alg. 2 allows for reducing the overall sphere refinement complexity from O(P m) to O(m).

V. NUMERICAL ILLUSTRATION

In this section, we illustrate the behavior of the sphere refinement procedure with the following two examples:

• KL regression with a proximal gradient (PG) solver [START_REF] Harmany | This is SPIRAL-TAP: Sparse Poisson Intensity Reconstruction ALgorithms-Theory and Practice[END_REF] for archetypal analysis on the NIPS papers dataset [START_REF] Globerson | Euclidean Embedding of Co-occurrence Data[END_REF]. The size of the problem is (m×n) = (2483×14035) and λ/λ max = 10 -1 (λ max being the regularization above which the zero vector is a solution of (1) [12, Sec. 4.1.2]). • Logistic regression with a coordinate descent (CoD) solver [START_REF] Tseng | A coordinate gradient descent method for nonsmooth separable minimization[END_REF] for binary classification of the Leukemia dataset [START_REF] Golub | Molecular classification of cancer: class discovery and class prediction by gene expression monitoring[END_REF]. The size of the problem is (m × n) = (71 × 7129) and λ/λ max = 10 -2 . We report in Table I, for each of the three situations described in Fig. 1, the distribution of times where ᾱk > α S b and ᾱk ≤ α S b . The reported distributions have been experimentally observed to depend mostly on the underlying solver rather than other parameters like regularization and problem instance. Therefore, the reported scenarios in Table I are quite representative of CoD and PG solver typical behaviors [START_REF] Dantas | Supplementary Material to Sphere Refinement in Gap Safe Screening[END_REF]. An interesting observation is that, for both experiments, the proportion of indecisive situations is very low (1.9% for Logistic regression with CoD and 1.2% for KL-regression with proximal gradient). In particular, the proportion of times where the fixed point ᾱk has been computed without being used Fig. 3: Evolution of ᾱk and α S b (top), the duality gap G k (middle), and the number of inner refinement iterations performed by Alg. 1 (bottom), as a function of the outer iteration number k. Green, grey (very rare) and red backgrounds depict respectively the improvement, indecisive, and no-improvement situations. The initial white region corresponds to a "burn-in" phase where ᾱk < α S b = α ∆ A . Indeed, here α S b has been initialized with α ∆ A which is known.

(bold values in Table I) is even smaller. These observations show the efficiency of the simple test at Line 10 of Alg. 2 in discriminating improvement from no-improvement situations. If, for a given problem, indecisive cases are more abundant, often leading to useless computations of ᾱk , one can modify the test in Line 10 so as to exclude such indecisive cases.

To further illustrate the sphere refinement behavior, we report in Fig. 3 the evolution of the best strong concavity constant α S b , the kth fixed point ᾱk , and the duality gap G k = Gap λ (x k , θ k ) as a function of the iteration number k. We observe that, in general, no-improvement situations (red areas) occur at iterations where the duality gap increased. This behavior can be more frequent for some solvers (e.g., PG) than others (e.g., CoD). Moreover, we see that the fixed point ᾱk (blue curves) can be significantly degraded in such noimprovement situations. This shows the importance of updating the strong concavity constant only when it improves over the current one (α S b ).

The number of refinement iterations performed by Alg. 1 is also reported in Fig. 3. We see that, in the coordinate descent (resp. proximal gradient) case, a total of 37 (resp. 69) inner iterations are avoided by the proposed approach (more extensive experiments are available in [START_REF] Dantas | Supplementary Material to Sphere Refinement in Gap Safe Screening[END_REF]).

VI. CONCLUSION

In this work, we made a detailed theoretical analysis of the sphere refinement loop proposed in [START_REF]Expanding boundaries of Gap Safe screening[END_REF], by reformulating it as fixed point iterations and characterizing its convergence point. Not only does it shed new light on this refinement step, but it allows us to derive a non-iterative version that is more elegant, more concise, and enjoys a better computational complexity. Proof. By assumption on the h i , we have h i (ᾱ i ) = ᾱi and h i (α) < α, ∀α ∈ ( ᾱi , +∞) and h i (α) > α, ∀α ∈ (0, ᾱi ).

Denoting i = argmin i∈[m] ᾱi , we get h(α) ≤ h i (α) < α, ∀α ∈ (ᾱ i , +∞) (15) h(α) > α, ∀α ∈ (0, ᾱi ), (16)
The continuity of h i and h completes the proof.

Define h k i such that h k in (8) can be written as

h k (α) = min i∈[m] h k i (α). (17)
Then, to prove Propositions 2 and 3, it suffices to show that the corresponding h k i fulfill the conditions of Lemma 2.

Proof of Proposition 2

We get from [12, Proposition 36] (with r =

√ 2G k /α) that h k i (α) := λ 2 y i α √ α(1 + λθ k i ) + λ √ 2G k 2 , (h k i ) (α) := λ 3 y i √ 2G k √ α(1 + λθ k i ) + λ √ 2G k 3 .
In order to invoke Lemma 2, let us analyze the fixed point of h k i . Clearly, we always have

h k i (0) = 0 showing that 0 is a fixed point of h k i . Moreover, from Lemma 1, it is attracting iff (h k i ) (0) = y i /(2G k ) < 1 ⇔ G k > y i /2. Concerning non-zero fixed points, they satisfy α(1 + λθ k i ) 2 + 2 √ α(1 + λθ k i )λ √ 2G k + λ 2 (2G k -y i ) = 0.
This is a quadratic equation in √ α with solutions

√ α = λ(- √ 2G k ± √ y i ) 1 + λθ k i . (18)
Because -√ 2G k ≤ 0, only the "plus" solution is admissible when G k < y i /2. Moreover, we get from Lemma 1 that G k < y i /2 also implies that this non-zero fixed point is attracting.

Combining the previous results, we have that • if G k ≥ y i /2, then h k i has a unique fixed point, ᾱi = 0, which is attracting, 3• if G k < y i /2, then h k i has two fixed points: 0 which is repelling and ᾱi > 0 (in ( 18)), which is attracting.

Proof of Proposition 3

Let

τ i = |λθ k i -y i + 1 2 | ≤ 1/
h k i (α) =      4λ 2 if α ≤ 2λ 2 G k τ 2 i 4λ 2 1-4 τi-λ 2G k α 2 if α ≥ 2λ 2 G k τ 2 i (h k i ) (α) =        0 if α ≤ 2λ 2 G k τ 2 i 16λ 3 √ 2G k τi-λ 2G k α α 3 2 1-4 τi-λ 2G k α 2 2 if α ≥ 2λ 2 G k τ 2 i Note that (h k i ) is continuous at 2λ 2 G k τ 2 i
and thus h k i ∈ C 1 . Then, from the definition of h k i , we distinguish two cases.

• ᾱi = 4λ 2 is a fixed point of h k i if 4λ 2 ≤ 2λ 2 G k /τ 2 i ⇐⇒ G k ≥ 2τ 2 i .
Moreover it is attracting (Lemma 1 with (h k i ) (ᾱ i ) = 0 < 1).

√ α = -4τ i λ √ 2G k ± 2λ 2G k + 1 -4τ 2 i 1 -4τ 2 i . (21)
As τ i < 1 2 , we have 1-4τ 2 i > 0 and 4τ i λ

√ 2G k < 2λ √ 2G k < 2λ 2G k + 1 -4τ 2
i , showing that the solution with the plus sign is admissible. Denoting ᾱi this solution, we have ᾱi > 2λ 2 G k /τ 2 i ⇐⇒ G k < 2τ 2 i . Moreover, one can show that (see details in [START_REF] Dantas | Supplementary Material to Sphere Refinement in Gap Safe Screening[END_REF]Sec. 1.4])

(h k i ) ( ᾱi ) = √ 2G k (2τ i 2G k + 1 -4τ 2 i - √ 2G k ) 1 -4τ 2 i . (22)
is bounded by 1 2 (1 -1 -4τ 2 i ) when G k < 2τ 2 i . Then, with τ i < 1 2 , we get that (h k i ) (ᾱ i ) < 1 2 . This shows (with Lemma 1) that ᾱi is attracting. Combining all these disjoint cases complete the proof.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Sphere refinement behavior. In case (a), computing the fixed point ᾱk would improve over α S b . The refinement loop would follow the green path in (d-e). On the contrary, in case (c), computing the fixed point ᾱk would degrade w.r.t. α S b . There, running the refinement loop would follow the red path in (d-e). This situation is avoided in Alg. 1 (resp. Alg. 2) by the test at Line 13 (resp. Lines 10-11). Finally, the intermediate case (b) may lead to both mentioned behaviors.

10 )

 10 has a unique attracting fixed-point ᾱk

B. Proof of Propositions 2 and 3

 3 Lemma 1. [15, Theorem 2.1] Let h ∈ C 1 having a fixed point at ᾱ. Then ᾱ is attracting if |h (ᾱ)| < 1 and repelling if |h ( ᾱ)| > 1.Lemma 2. For i ∈ [m], let h i : R ≥0 → R ≥0 be a continuous function that has i) a unique attracting fixed point ᾱi ≥ 0 and ii) potentially 0 as repelling fixed point. Then ᾱ = min i∈[m] ᾱi is the unique attracting fixed point of h : α → min i∈[m] h i (α).

2 (

 2 the upper bound comes from dom(f * i (-λ•)) = [(y i -1)/λ, y i /λ]). Then we get from [12, Proposition 23, see proof] (with r = √ 2G k /α) that

TABLE I :

 I Proportion of times (%) where ᾱk ≤ α S b or ᾱk > α S b for each case of Fig.1. Results are averaged over a regularization grid of 100 points λ/λ max ∈ [10 -3 , 1) (standard deviation is shown in parentheses). Bold numbers emphasize the most critical case where ᾱk is computed but not used.

		COD FOR LOGISTIC		PROX. GRAD. FOR KL
		ᾱk ≤ αS b	ᾱk > αS b		ᾱk ≤ αS b	ᾱk > αS b
	IMPROV.	0	92.2 (5.3)		0	45.6 (6.1)
	NO-IMPROV. 5.9 (4.6)	0	53.2 (6.4)	0
	INDEC.	1.0 (0.7)	0.9 (0.7)		0.6 (1.1)	0.6 (1.2)
	attracting fixed-point ᾱk = min i∈[m]	ᾱk i with, for

If a function f is α 1 -strongly concave on S 1 , then it is α

≥ α 1 strongly concave on any S 2 ⊂ S 1 .

See [15, Definitions 1.3 and 1.4] or [16, Definitions 6.5 and 6.8] for a definition of attracting and repelling fixed points.

When G k = y i /2, while it is clear from the proof that 0 is the unique fixed-point, the fact that it is attracting does not come from Lemma 1 (as here (h k i ) (0) = 1). It comes from the fact that here h k i (α) < α ∀α = 0.

This work was supported by the European Research Council (FACTORY, ERC-CoG-6681839), the French ANR (EROSION, ANR-22-CE48-0004) and the NRF in Singapore (DesCartes, CREATE program).

CFD is with TETIS,

SUPPLEMENTARY MATERIAL A. Proof sketch of Proposition 1

From the definition of h k in (8), we get that the refinement loop at lines 15-18 of Alg. 1 amounts to the fixed-point iteration α j = h k (α j-1 ). Moreover, we know from [START_REF]Expanding boundaries of Gap Safe screening[END_REF]Proposition 7] that this refinement loop builds a sequence of nested Gap Safe spheres (i.e., with decreasing radius). Hence, the sequence (α j ) j converges and its limit point ᾱk is a fixedpoint of h k . Moreover, it is non-repelling as it can be reached with the fixed-point iteration at least from one initial point. A detailed proof of Proposition 1 is provided in [START_REF] Dantas | Supplementary Material to Sphere Refinement in Gap Safe Screening[END_REF]Sec. 1.2].


Fahima Djelil
email: fahima.djelil@imt-atlantique.fr

Eric Sanchez
email: eric.sanchez@unige.ch

Game Design and Didactic Transposition of Knowledge. The case of Progo, a Game Dedicated to Learning Object-Oriented Programming

Keywords: Game Design, Didactic Transposition, Metaphors, Ludicisation, Programming Learning, Progo

Game based-learning have been widely promoted to overcome the difficulties encountered by beginners to learn programming. However, there are many issues to address for the implementation of game-based learning. Indeed, game-based learning is not limited to adding game elements such as rewards to a learning situation, but it rather consists of transforming the learning situation so that it becomes playful. This work contributes to computer science education research, especially to game design for learning programming. We design a novel environment dedicated to learning object-oriented programming for beginners called Progo. It is based on a metaphor of a three-dimensional (3D) construction and animation game. We present an a priori analysis of the Progo environment on the basis of a didactic transposition framework. The framework highlights the ludicisation and metaphorisation process by which educational content is integrated into the game. This allows for the analysis of the transformation of the computing knowledge by the game design, and to verify whether analogies are maintained between the knowledge and what the learner should experience through play. This work contributes to a framework for the integration of educational content during learning game design.

Introduction

Learning and teaching programming to beginners is proven to be difficult, it is considered as one of the major challenges in computer science education [START_REF] Bennedsen | Teaching and learning introductory programming: a model-based approach[END_REF][START_REF] Medeiros | A systematic literature review on teaching and learning introductory programming in higher education[END_REF][START_REF] Piteira | Learning computer programming: study of difficulties in learning programming[END_REF]. Recent works focused on teaching and learning object-oriented programming, which is one of the most difficult paradigm for beginners [START_REF] Abbasi | A systematic review of learning object oriented programming through serious games and programming approaches[END_REF][START_REF] Abidin | Oop-ar: Learn object oriented programming using augmented reality[END_REF][START_REF] Keung | Bluej-uml: Learning object-oriented programming paradigm using interactive programming environment[END_REF][START_REF] Seng | Computer game as learning and teaching tool for object oriented programming in higher education institution[END_REF]. The main difficulty that students face, lies in abstract basic concepts, and they struggle to understand more complex concepts, when they cannot grasp the basics.

Previous research emphasises that a curriculum may focus on the use of concrete and visible objects, and games to motivate and engage students to develop their computing competences [START_REF] Webb | Computer science in k-12 school curricula of the 2lst century: Why, what and when?[END_REF]. Many works on introductory programming teaching are directed towards the use of microworlds [START_REF] Costa | Relation between alice software and programming learning: A systematic review of the literature and metaanalysis[END_REF][START_REF] Michaelson | Microworlds, objects first, computational thinking and programming[END_REF][START_REF] Woei | Learning programming using objects-first approach through folktales[END_REF][START_REF] Yukselturk | An investigation of the effects of programming with scratch on the preservice it teachers' self-efficacy perceptions and attitudes towards computer programming[END_REF]. Microworlds are visual and interactive environments, that aim to help students to understand abstract concepts through play and visible objects (Papert, 1980(Papert, /2020)). For instance, programming microworlds such as Scratch [START_REF] Resnick | Scratch: programming for all[END_REF], Alice [START_REF] Cooper | Alice: a 3-d tool for introductory programming concepts[END_REF] and Greenfoot [START_REF] Kölling | Introduction to programming with greenfoot[END_REF] allow students to manipulate visible and concrete objects and create their own game scenarios, leading to playful and engaging learning activities.

Game-based learning consists of offering the learner to participate in a playful situation, and to develop reflexivity towards his learning experience [START_REF] Sanchez | Game-based learning[END_REF]. The design of such playful situation involves transforming a learning situation in a way that allows the learner to adopt a playful attitude [START_REF] Sanchez | Game-based learning[END_REF]. This process, called ludicisation [START_REF] Genvo | Penser les phénomènes de ludicisation du numérique: pour une théorie de la jouabilité[END_REF] is a common implementation of programming microworlds, in which the concept of metaphor is very apparent [START_REF] Djelil | Microworlds for learning object-oriented programming: Considerations from research to practice[END_REF]. Indeed, metaphors allow to describe abstract concepts in a more comprehensible and concrete way for beginners, by providing analogies from familiar domains [START_REF] Lakoff | Metaphors we live by[END_REF]. Through these two properties, ludicisation and metaphorisation, microworlds provide learning experiences that aim, on the one hand, to make programming concepts concrete to be more easily graspable by beginners, and on the other hand, to make programming learning attractive to capture students' attention and increase their motivation and interest [START_REF] Moskal | Evaluating the effectiveness of a new instructional approach[END_REF]Papert, 1980Papert, /2020)).

In this paper, ludicisation and metaphorisation are approached from the perspective of the didactic transposition framework [START_REF] Colomb | Chevallard (yves).-la transposition didactique: du savoir savant au savoir enseigné[END_REF], as a process by which academic knowledge is transformed to become learning objects, allowing students to learn through experience. Thus, didactic transposition serves as a framework for game design. In this framework, ludicisation implies metaphorisation to reshape the concepts to be learned. This framework has been displayed outside the French-speaking community, and applied for the teaching of many disciplines [START_REF] Bosch | Twenty-five years of the didactic transposition[END_REF]. However, existing works addressing the question of didactic transposition relate mainly to the domain of mathematics and sciences and rarely to the domain of computer science [START_REF] Hazzan | Didactic transposition in computer science education[END_REF]. Indeed, in the didactics of computer science, existing work [START_REF] Orange | Didactique de l'informatique et pratiques sociales de référence[END_REF] focuses more on the analysis of learners' skills and difficulties, than on the transposition of knowledge for designing learning situations.

We, therefore, contribute with this paper to the growing research in the field of computer science education, raising questions on how to make programming learning attractive and effective to beginners. Our work relies on the introduction of object-oriented principles for beginners and on ludicisation for the design of a new environment called Progo. We refer to beginners by novice students that are introduced to basic concepts of object-oriented programming instead of advanced concepts. Based on the didactic transposition framework, we analyse the Progo game design, to understand how the objectoriented programming concepts are transformed in a playful situation through a construction game metaphor, and how the meaning of these concepts is maintained after transformation. Thus, the research questions we address are the following: 1) How computing knowledge is transformed by game design ? 2) To what extent analogical relations are maintained between the computing knowledge and the concrete and visible objects ?

The purpose of this paper is threefold, both theoretical, empirical and policy relevant. First, we present a theoretical model of didactic transposition for the design of learning situations, leading students to learn through discovery and play. Then, we apply this model to the case of Progo. This empirical work consists of an a priori analysis of the game design, and more specifically, of how teaching knowledge is integrated into the game. Finally, we aim to bring a broader contribution in terms of implications for learning game design in the filed of computer science education.

In the following sections, we first trace previous work on the learning design inherent to the objects-first approach for the introduction of object-oriented principles for beginners, as well as on game-based programming learning. We describe the didactic transposition model for game design which is based on the concepts of ludicisation and metaphorisation. Then, we describe our method used to analyse and discuss the Progo game with the lenses of the ludicisation framework. The last sections emphasize the limitations, conclusions and implications of this work.

2 Related work

Objects-first approach for teaching object-oriented programming to beginners

Programming is what allows a sequence of operations to be executed on a computer. The goal of any program is to compute and return valid and reliable results. A program is defined as a sequence of actions that a computer must perform in a finite time to resolve a problem [START_REF] Dabancourt | Apprendre à programmer: algorithmes et conception objet[END_REF]. These operations are called instructions and are translated into a programming language. The way a program is constructed constitutes a programming style or a programming paradigm.

The concepts of object and class are the basic concepts that govern the object-oriented paradigm. A class is often defined as a structure representing a mould or a template for the object, while the object is an embodiment, a reproducible copy of its class [START_REF] Bersini | La programmation orientée objet[END_REF]. Different approaches exist for teaching programming and the object-oriented paradigm [START_REF] Roberts | Computing curricula[END_REF]. Objects-first approach focuses on the fundamentals of object-oriented programming and design at the very beginning of curriculum. It is one of the most quoted approach in the literature, reflecting its interest in practice and its potential to overcome learning and teaching difficulties [START_REF] Bennedsen | Teaching and learning introductory programming: a model-based approach[END_REF][START_REF] Krugel | Strictly objects first: A multipurpose course on computational thinking[END_REF][START_REF] Michaelson | Microworlds, objects first, computational thinking and programming[END_REF][START_REF] Woei | Learning programming using objects-first approach through folktales[END_REF]. For instance, searching "objects-first approach" in the ACM Digital Library returns 561,358 results (October, 2021).

Many authors described their experiences for the introduction of objectoriented courses with respect to the object-first approach. The approach described by [START_REF] Woodworth | Integrating console and event-driven models in cs1[END_REF] and [START_REF] Adams | Object centered design for java: teaching ood in cs-1[END_REF], guides the learner for the design and the use of programming abstractions, by modelling properties of objects used in a previous problem-solving step. [START_REF] Buck | Design early considered harmful: graduated exposure to complexity and structure based on levels of cognitive development[END_REF] argue on an approach that allows the students to start by changing the computer code and later, designing parts of the object-oriented system. Programming language concepts are introduced as needed during the problem-solving tasks. Similarly, [START_REF] Becker | Teaching cs1 with karel the robot in java[END_REF] describes a learning scenario that consists of starting by instantiating and using objects and then extending existing classes. Programming language fundamentals are introduced progressively. This learning scenario includes the use of the microworld Karel [START_REF] Xinogalos | An introduction to object-oriented programming with a didactic microworld: objectkarel[END_REF]. [START_REF] Kölling | Guidelines for teaching object orientation with java[END_REF] suggest a set of guidelines for teaching introductory object-oriented programming: Starting with objects from the beginning instead of a small program in an imperative paradigm, modifying existing code, reading a well-structured code, etc. This approach is implemented in the Greenfoot microworld [START_REF] Kolling | Introduction to programming with greenfoot: Objectoriented programming in java with games and simulations[END_REF].

These experiences are very similar as they do not focus on programming languages at the beginning of teaching, but rather on Object-Oriented concepts, through problem-solving tasks using significant learning environments, such as microworlds. This approach was further conceptualised on the basis of analysis of more than 200 contents in the literature [START_REF] Bennedsen | What does" objects-first" mean? an international study of teachers' perceptions of objects-first[END_REF], allowing the definition of three steps through which it is implemented in practice:

1. Using objects: the learner uses objects defined before programming classes.

The focus is on the use of objects before their implementation (objects interaction introduced before methods implementation). Once the learner masters the concept of object, he moves onto the concept of classes. 2. Creating classes: the learner defines and implements classes and creates instances of classes (data fields and methods). The focus is on writing and using classes before algorithms. The concept of a class is often approached in a concrete and creative programming way. 3. Concepts: the learner learns general principles of the object-oriented paradigm, through the creation of models. The focus is on the conceptual aspects of object-orientation. The objective is to learn to model a real world as objects and to map these objects to classes of code.

It is worthy to consider the learning design [START_REF] Brousseau | Theory of didactical situations in mathematics: Didactique des mathématiques[END_REF] that defines the objects-first approach to introduce the object-oriented paradigm to beginners. Objects-first approach allows for the introduction of object-oriented programming principles through the embedding of three categories of concepts [START_REF] Djelil | Une approche didactique pour l'introduction de la programmation orientée-objet en classe[END_REF]. At each level, the objective is to help the beginner to focuse on a category of concepts, while the successive ones are temporally hidden. The categories are embedded since they encapsulate object-oriented concepts that are interdependent (objects, classes and design principles) (Fig. 1). As a result, beginners are expected to progressively acquire prerequisites before handling complex concepts, when they are involved in modelling and coding object-oriented programs for problem-solving.

Game-based programming learning

According to [START_REF] Plass | Foundations of game-based learning[END_REF], game-based learning depends on the alignment between the game characteristics and learning outcomes. However this issue is relatively unaddressed. A meta-analysis published in 2016, highlighted only 8 articles out of 69 that explicitly addressed this issue [START_REF] Ke | Designing and integrating purposeful learning in game play: A systematic review[END_REF].

Yet, as soon as 2007, [START_REF] Habgood | The effective integration of digital games and learning content[END_REF] distinguished between games that are described as extrinsic games, for which the game content and academic exercises alternate (the game then appears to be a reward for having succeeded in the exercise), and intrinsic games, for which the targeted knowledge is necessary to deal with the objectives of the game. Thus, using a game-based approach to teach programming leads to integrating educational content with playful aspects. This is what is referred to intrinsic metaphor for a successful integration [START_REF] Fabricatore | Learning and videogames: An unexploited synergy[END_REF].

In the field of computer science education, programming microworlds are designed as intrinsic games, since they are based on playful learning situations rather than game rewards. In fact popular microworlds such as Scratch [START_REF] Resnick | Scratch: programming for all[END_REF], Alice [START_REF] Cooper | Alice: a 3-d tool for introductory programming concepts[END_REF] and Greenfoot [START_REF] Kölling | Introduction to programming with greenfoot[END_REF] are used to overcome difficulties in learning programming to beginners through play and metaphors [START_REF] Djelil | Microworlds for learning object-oriented programming: Considerations from research to practice[END_REF].

Ludicisation and programming microworlds

Ludicisation allows for the design of learning situations that foster playful attitude, leading students to use artefacts that are not necessarily games [START_REF] Genvo | Penser les phénomènes de ludicisation du numérique: pour une théorie de la jouabilité[END_REF]. Ludicisation differs from gamification, which provides students with engaging activities through rewards and positive reinforcements [START_REF] Genvo | La théorie de la ludicisation: une approche anti-essentialiste des phénomènes ludiques[END_REF]. Ludicisation is thus a way of designing playful and interactive learning situations. It is a common practice for programming learning [START_REF] Combéfis | Learning programming through games and contests: overview, characterisation and discussion[END_REF][START_REF] Seralidou | Learning programming by creating games through the use of structured activities in secondary education in greece[END_REF].

Programming microworlds also implement ludicisation, e.g. Scratch [START_REF] Resnick | Scratch: programming for all[END_REF], Alice [START_REF] Cooper | Alice: a 3-d tool for introductory programming concepts[END_REF] and Greenfoot [START_REF] Kölling | Introduction to programming with greenfoot[END_REF] aim, from one hand, to allow students to develop autonomously, through personal discovery and exploration, complex and abstract knowledge [START_REF] Kafai | Playing and making games for learning: Instructionist and constructionist perspectives for game studies[END_REF]Papert, 1980Papert, /2020)). The learning situation induced using these environments also involves problem-solving. As a principle of the constructionism paradigm [START_REF] Harel | Constructionism[END_REF][START_REF] Perkins | Knowledge as design[END_REF], this allows for exploring a domain in a rich and meaningful way [START_REF] Rieber | Seriously considering play: Designing interactive learning environments based on the blending of microworlds, simulations, and games[END_REF]. From another hand, the goal consists of providing students with engaging learning situations that allow for intrinsically motivating learning activities connected with learners' expectations through play (Papert, 1980(Papert, /2020)). These environments provide meaningful experiences for learning programming, by offering students the opportunity to design and develop their own games. They allow students to create game scenarios by designing programs, leading to playful learning situations. Ludicisation is therefore an essential design principle for programming microworlds.

Metaphors and programming learning

Programming microworlds use metaphors to make abstract concepts more easily graspable by beginners [START_REF] Xinogalos | An introduction to object-oriented programming with a didactic microworld: objectkarel[END_REF]. In such environments, programming concepts are experienced in a graphical scene as a narrative, an animation or a significant phenomenon [START_REF] Cooper | Alice: a 3-d tool for introductory programming concepts[END_REF][START_REF] Kölling | Introduction to programming with greenfoot[END_REF][START_REF] Resnick | Scratch: programming for all[END_REF].

In computer science, the most important computing concepts are funded on metaphors. Therefore, explicit metaphors are often used to teach beginner students how to code computer programs [START_REF] Mcconnell | Code complete[END_REF]. According to [START_REF] Travers | Programming with agents new metaphors for thinking about computation[END_REF], computation itself is a structuring metaphor and programming models are built on metaphors. This includes the object-oriented paradigm, in which computational objects are depicted metaphorically in terms of physical and social objects [START_REF] Travers | Programming with agents new metaphors for thinking about computation[END_REF]: As physical objects, they have properties and state. As social objects, they communicate and interact.

Metaphors enable the formalisation and communication of new knowledge in an understandable way for learners, and provide students with analogies that foster learning [START_REF] Carroll | Metaphor, computing systems, and active learning[END_REF]. Indeed, metaphors make programming tangible and provide students with means to understand the abstract operations of the computer in terms borrowed from more familiar domains [START_REF] Travers | Programming with agents new metaphors for thinking about computation[END_REF]. This is very useful for learning concepts that cannot be directly perceived. In this sense, a metaphor is defined as a way to structure and transform the knowledge from one domain through mapping concepts and relations to build another domain that is already familiar. This new domain is expected to enabling learning since the "essence of metaphor is understanding and experiencing one kind of thing in terms of another" [START_REF] Lakoff | Metaphors we live by[END_REF].

This transformation of knowledge consists of didactic transposition. In the following, we describe the didactic transposition framework in which programming knowledge is transformed using a metaphor in the game design.

Didactic transposition and game design

Didactic transposition is defined by a process by which knowledge (academic knowledge) is transformed to become learning objects (knowledge to teach) [START_REF] Botet | Petit traité de la métaphore, un panorama des théories modernes de la métaphore[END_REF][START_REF] Colomb | Chevallard (yves).-la transposition didactique: du savoir savant au savoir enseigné[END_REF]. The process does not only consist of the simplification of knowledge but rather to significantly change academic knowledge to be taught and learned. Didactic transposition is a process of deconstruction and rebuilding of academic knowledge with the aim of making it teachable [START_REF] Bosch | Twenty-five years of the didactic transposition[END_REF]. This process includes two main steps, including how the scholarly knowledge is shaped to become knowledge to be taught, and how the teacher contextualises the knowledge to be taught into meaningful learning situations. Bonnat, Sanchez, Paukovics, and Kramar (n.d.) proposed a framework as an alternative to the classical model of didactic transposition. In this model, didactic transposition is approached from the perspective of ludicisation and metaphors. A metaphor is an implicit analogy that operates a transfer of meaning from an abstract target domain to a concrete source domain, in other words, it allows a target domain to be understood from a source domain. Thus, the didactic transposition corresponds to a conversion of a target situation into a source situation (Fig. 2). The target situation is the target abstract learning domain, and the source situation is the concrete learning situation provided to the learner.

According to this model, learning is defined as the ability for the learner to identify analogies and relationships between the source and the target situations [START_REF] Hofstadter | Surfaces and essences: Analogy as the fuel and fire of thinking[END_REF]. The metaphor is a figurative meaning of the teaching domain. As a result, there is an isotopy, a common meaning, between the elements of the source situation (the game) and the elements of the target situation (the concepts to be learnt). Nevertheless, to perceive this isotopy, the learner must follow an interpretative path that will allow him to deconstruct the metaphor. This de-metaphorisation takes place during the debriefing carried out by the instructor after the game session (Bonnat et al., n.d.).

Method

In this paper, we aim to analyse the didactic transposition by which the academic computing knowledge is contextualised in a new game-based learning environment called Progo. This analysis is conducted from two perspectives:

(1) the design inherent to the objects-first approach for the introduction of object-oriented principles to beginners, and (2) the didactic transposition with the metaphorisation and ludicisation processes that operates in the game design. Our main objective is to characterise how the object-oriented concepts are transformed and reshaped in the Progo game design and the resulting learning situation. This analysis aims to evaluate the distance between the target situation (the knowledge to be taught) and the source situation (the game situation induced by Progo). Although several empirical studies have been conducted to analyse the use of Progo and its learning effectiveness [START_REF] Djelil | Towards a 3d virtual game for learning object-oriented programming fundamentals and c++ language theoretical considerations and empirical results[END_REF][START_REF] Djelil | Investigating learners' behaviours when interacting with a programming microworld[END_REF][START_REF] Djelil | Acquisition de connaissances de programmation en fonction des stratégies d'apprentissage: une étude empirique du micromonde progo[END_REF], we do not focus in this study on the analysis of the learning experience, but we rather aim to analyse the game design based on the didactic transposition model.

Our method relies, on the one hand, on an analysis of the curriculum in order to identify the knowledge to be taught and, on the other hand, on an a priori analysis of the Progo game. This a priori analysis [START_REF] Artigue | Ingénierie didactique[END_REF], consists of determining in what way the choices made in the design of the game (didactic transposition) are expected to impact the learners' behaviour and the learning process. The a priori analysis is based on the identification of the different elements of the game, the tasks they provide with and the knowledge mobilised by these tasks. This analysis aims to describe the source situation and thus to characterise the transformation of knowledge during the design of the game (RQ 1) and the analogical relations between the source situation and the target situation (RQ 2). The a priori analysis has close connections with conjecture mapping (W. [START_REF] Sandoval | Conjecture mapping: An approach to systematic educational design research[END_REF], a design method developed for design-based research. The close analysis of a learning device allows for the identification of design conjectures i.e. "conjectures about how to support learning in a specific context, that are themselves based on theoretical conjectures of how learning occurs in particular domains" (W.A. [START_REF] Sandoval | Design-based research methods for studying learning in context: Introduction[END_REF]. Design conjectures are implemented as design elements that are expected to produce specific effects on the learning process. The a priori analysis is performed by the authors of this article: a game-based learning scholar and a computer science education scholar.

4 Analysis of the Progo game design 4.1 Analysis of academic curricula for teaching object-oriented basics

In higher education and more particularly in the French educational system, computer science curricula include object-oriented programming from the beginning of cycle 1, and often during the core curricula (before specialisation, e.g. object-oriented design and programming courses in Universities and Engineering Schools [START_REF] Roberts | Computing curricula[END_REF], National Pedagogical Programme of the computer science undergraduate degree). Computing curricula generally include courses which are spread over several weeks, due to a large number of concepts and knowledge to be taught. Object-oriented programming introduction courses come often after the course "introduction to programming and algorithms". Instructors choose to use programming languages that are widespread in industries, such as Java and C++. Students therefore have some programming skills, but very often they are beginners on object-orientation and its programming languages.

According to the didactic transposition framework, the target situation consists of the object-oriented programming basics as defined in computer science curricula. We have analysed the academic curricula according to the objects-first approach, to describe the target situation. We describe the objectoriented basics with respect to the didactic engineering of the objects-first approach that embeds the fundamental concepts within the three didactic steps: 1) using objects, 2) creating classes and 3) design principles. Table 1 lists, for each didactic step, the corresponding object-oriented basics with respect to the academic curricula. These programming concepts are the target learning concepts, i.e. the knowledge to be taught (or learning outcomes). In what follows, we analyse how these concepts are transformed and how their meaning is preserved by the analogical relationships between the target and the source situations.

Knowledge transformation in the Progo game design

The didactic transposition framework defines a target situation and a source situation: In our context, the target situation is the object-oriented programming paradigm (design and coding principles), the source situation is the Progo environment, which is based on a metaphor of construction and animation (Fig 3).

The Progo interface comprises a three-dimensional (3D) scene, which allows the learner to design his own constructions by assembling, colouring and rotating 3D components. The interface also comprises a code editor, entirely synchronised with the 3D scene. The learner can interact with the 3D components by viewing and entering code. Therefore, the game-play consists in building and animating robots or 3D mechanical structures (Fig 4).

The 3D components visible at the user interface and the interactions they provide allow to shape object-oriented basics through metaphorisation and ludicisation. The design of Progo embeds object-oriented concepts through three steps: 1) using objects, 2) creating classes and 3) design principles. In the following, we describe how ludicisation and metaphorisation reshape the object-oriented concepts in a meaningful and playful way, with regard to the three didactic steps (RQ 1). We also describe the analogical relationships between the source situation and the target situation (RQ 2). We first consider the analogy between using existing 3D components in the Progo game with the didactic step using objects. Second, we consider the analogy between the creation of a new 3D construction and the didactic step creating classes. Finally, we consider the analogy between 3D constructions with the didactic step using design principles.

Using existing 3D components

During the first didactic step, the learner starts with manipulating objects. As a result, he experiences the following concepts: 1) The relationship between an object and its class, 2) The setting object attributes, 3) The modification of attribute values and method calls (Table 1).

The Progo interface makes visible the concept of a class through a 3D graphical model. Each time a model is instantiated, an interactive object is created. When an object is created, its visual appearance is similar to its class.

The characteristics of an object are expressed through its appearance and behaviour. The appearance includes the object position (its location relatively to another object), its colour and its rotation angle. These characteristics are the object attributes. The behaviour of an object includes the ability to be assembled with another object to build a more complex structure, the ability to change its colour and/or the ability to rotate for a given duration. These characteristics are object methods.

The learner can change an object appearance by modifying the values of its attributes or making method calls. This is what defines an object state.

The learner experiences these concepts both with the 3D scene and the code editor (Fig 5). Once the learner has finished his construction, he is invited to create a new class with his realisation in a second phase.

Creating a new 3D construction

During the second didactic step, the learner moves to the concept of class, comprising: 1) the class role, 2) the class encapsulation, and 3) the class constructor (Table 1).

With the Progo interface, the learner can name and save each new 3D construction as a new class which can be instantiated and visualised in the 3D scene. This new graphical model gathers all the properties and behaviours of the objects chosen beforehand by the learner during the previous didactic step. Therefore, the player experiences the class role.

Once a new class is created, the learner can visualise new tabs displaying two codes in C++ programming language, the declaration of the new class ("*.hpp" file), and the definition of this class ("*.cpp" file) in the code editor. The learner can therefore experience the concept of encapsulation by observing the codes and by trying to manipulate new instances of this new class in a new "main()" function. The learner may notice that some of the attributes and methods of the new class are "private" (preceded by the keyword "private") and others are "public" (preceded by the keyword "public"). The learner also has the opportunity to make calls to the public methods in the "main()" function as well as in the 3D scene, but not in the private ones.

The new class also has a constructor which allows an object to be initialised as soon it is created. When observing the constructor code, the learner may notice that the constructor is preceded by the keyword "public", has the same name as its class, and does not have a return type (Fig. 6).

3D constructions as object-oriented systems

During the third didactic step, the learner is introduced to the design principles of the object-oriented paradigm. In the academic curricula, this mainly comprises the principles of association, aggregation, composition and inheritance (Table 1). In the Progo environment, the building of each 3D construction uses classes of objects which are connected to each others. Therefore, relationships between classes of objects manipulated by students when playing, are consistent with the object-oriented design principles. In this didactic step, the instructor can ask students to analyse the design principles that are illustrated in the 3D constructions.

Regarding the object-oriented paradigm, each 3D construction is an objectoriented system, that can be modelled using the Unified Modeling Language (UML) [START_REF] Muller | Modélisation objet avec uml[END_REF], which is a very widespread formalism used in the french academic curricula to introduce object-oriented design principles. UML allows to describe in a formal way the object-oriented relationships between the different classes used to build a 3D construction in Progo (Fig 7).

The classes of objects in the Progo construction game are modelled as follows:

1. The "3DConstruction" class: This class is a model of the final realisation of a student. It is a composition (part-of relationship) of all the classes used by the students during the game. It defines two main methods: the method "animate()" that gathers all the animation operations programmed by the student, and the method "reinitialise()", that allows to set a 3D construction to its initial state. 2. Abstract classes that are not visible at the interface, but allow to model the visible ones as graphical components having some characteristics. They are modelled as follows:

• The "3DComponent" class: models all the graphical components, having the attribute "color", and the methods "connect()", and "colorForaDuration()", allowing respectively to connect an object to another, and to colour an object during a period of time (animation effect). • The class "ActiveComponent": This class models all the graphical components, having additional characteristics comparatively with the precedent class. They are called active components since they are able to perform a movement as a result of a rotation during a period of time. This leads to animation effect. This class is inherited from the "3DComponent" class, and defines the new attribute "rotationAngle", and the method "turnForaDuration()".

3. Visible classes at the interface are classes that the students can directly manipulate when playing (Fig 8). They are inherited from the abstract classes, either from the class "3DComponent" such as "Base", "Cube", "YBifurcation" and "Spring", or from the class "ActiveComponent", such as "Wheel" and "Gear". The class "Base" has a unique instance as a construction basis. It is visible in the 3D scene when launching the Progo environment, inviting students to start playing.

Finally, in addition to these different classes, the Progo construction game enables the introduction of three distinct design principles from the academic curricula (see Table 1) : 1. Inheritance: relationships between each of the classes,

• "Base", "Cube", "YBifurcation", "Spring" and "ActiveComponent" with the class "3DComponent". • "Wheel" and "Gear", with the class "ActiveComponent".

2. Aggregation: the ensemble/element relationship between all the instances of the class "3DComponents", since each component is connected to each other, but removing some components doesn't impact others. 3. Composition: relationship between the "3DConstruction" class with the "3DComponent" class from one hand, and the "Base" class from another hand. The composed 3D construction cannot exist without the composing entities.

Fig. 8 3D graphical components representing classes of objects.

Discussion

The concept of ludicisation, as a form of didactic transposition [START_REF] Balacheff | La transposition informatique. note sur un nouveau problème pour la didactique[END_REF][START_REF] Bonnat | Didactic transposition and learning game design. proposal of a model integrating ludicization, and test in a school visit context in a museum. Didactics in a Changing World[END_REF], allows to distinguish between a target situation (in the sense of a learning target), which integrates the knowledge to be taught, and a source situation (in the sense of a learning source), that refers to the learning situation in which this knowledge is contextualised in the form of playful problems to be solved, tasks to be carried out or even objects to be manipulated.

In our work, knowledge is integrated into a learning situation through a metaphor of a construction game dedicated to the creation and animation of 3D objects. This metaphor transforms the characteristics of object-oriented programming concepts (target situation), into graphical 3D objects to be manipulated in a construction game (source situation).

The process of didactic transposition has captured the essence of the target situation similarly to a literary metaphor. Indeed, the metaphor is a refined form of the target situation, aiming to allow learners focusing their attention on the core concepts of this situation. In our case, the core situation comprises key concepts of object-oriented programming (e.g. the concepts of objects, class and relationship between the object and class are represented by visible and interactive 3D graphics, which are instances of 3D graphical models, setting attribute values and making method calls are illustrated by colouring, rotating or connecting graphics).

The construction metaphor embedded in the game is a well known and intuitive conceptual domain (the source situation), which is projected on the conceptual domain to be learned (the target situation). This allows the learner to move from concrete and visible concepts (3D graphics and their characteristics) to more abstract and opaque concepts (objects, classes, methods, etc.) [START_REF] Botet | Petit traité de la métaphore, un panorama des théories modernes de la métaphore[END_REF]. In other words, the learner moves from the experience of the construction game to the computing concepts to be learned.

There is an analogical relationship between the situation implied by the Progo environment (source situation) and the object-oriented concepts (target situation). Indeed, the construction metaphor embedded in the Progo game allows the description of object-oriented basics in a reliable and accurate way (objects, classes and design principles). This is in line with [START_REF] Hofstadter | Surfaces and essences: Analogy as the fuel and fire of thinking[END_REF], who assumes that learning does not result from a purely interpretative logic, but rather from a process that leads the learner to identify analogical relationships between different situations.

Therefore, the analysis we have carried out allow us to answer the research questions (RQ 1 and RQ 2). Contextualisation of computing knowledge in the game Progo is a result of a transformation process, that maintained an analogical relationship between the knowledge concerned and the game metaphor.

Limitations

This work highlights how didactic transposition operates on the design of the Progo environment through metaphorisation and ludicisation. However, our analysis doesn't take into consideration the reverse process, which consists of de-metaphorisation. In practice, this takes the form of a debriefing conducted by the teacher, also referred to as knowledge institutionalisation [START_REF] Brousseau | Théorie des situations didactiques: Didactique des mathématiques 1970-1990[END_REF]. A student who plays with Progo develops knowledge which needs to become communicable and transferable to other situations. Indeed, the French language recognises a difference between "situational knowledge" (connaissance) and "institutional knowledge" (savoir ) (Plumettaz-Sieber, [START_REF] Plumettaz-Sieber | Debriefing and knowledge processing an empirical study about game-based learning for computer education[END_REF]. A student who plays Progo develops knowledge which is implicit, subjective and situated. For example, the concept of object is not explicit within the Progo environment. This concept is only reflected through the tasks performed by the player. It means that, although the player learns how to use an object by playing Progo, he is not able to explain what an object is, in computing terms. [START_REF] Warfield | Invitation to didactique[END_REF] uses the expression "to be familiar with" to describe the knowledge gained by students involved in an autonomous activity such as Progo. This situational knowledge is not formalised and tied to a specific context (i.e, the learning context). The transfer of this knowledge implies a transformation called institutionalisation [START_REF] Brousseau | Theory of didactical situations in mathematics[END_REF], and this occurs during debriefing [START_REF] Plumettaz-Sieber | Debriefing and knowledge processing an empirical study about game-based learning for computer education[END_REF]. Institutionalisation, relates to the change of the status of knowledge. The implicit, subjective and situated knowledge becomes explicit, objective and context-free (institutional knowledge). [START_REF] Warfield | Invitation to didactique[END_REF] uses the expression "to know a fact" to stress that institutionalisation consists of a metacognitive process. This transformation of knowledge is under the responsibility of the teacher. During debriefing the game is over, the players become learners, and, through questions and discussions, the concepts experienced when playing the game are named, explained and validated. In addition, future usages of the knowledge are considered. Thus, institutionalisation of knowledge and debriefing are the counter parts of metaphorisation and ludicisation. While metaphorisation and ludicisation occur on the design of the game, institutionalisation occurs during the debriefing which follows the time dedicated to play the game. However, both processes are essential.

Conclusions and implications

In this paper we performed an a priori analysis of the game Progo, a new environment dedicated to learning object-oriented programming basics to beginners. Our analysis relies on the didactic transposition framework, which allows, on the one hand, to highlight how computing knowledge is transformed and reshaped to be "played" as more intuitive and graspable objects, and from another hand, to verify whether analogies between the computing knowledge and the manipulated objects are maintained during this transformation process. The didactic transposition framework allows to distinguish between a target situation (target knowledge, abstract and opaque concepts, i.e. the object-oriented programming basics) and a source situation (concrete and visible objects, i.e. the game play induced by Progo), and highlights a transformation process between these two situations as a result of metaphorisation and ludicisation process (i.e. the Progo construction and animation game metaphor).

Moreover, in order to be able to describe the target situation in a comprehensible way, we based our analysis on the objects-first approach. This approach embeds object-oriented concepts in three didactic steps that help beginners to progressively master the targeted concepts. This approach is part of the Progo game design and provides a means for the description of the programming concepts as defined in computer science curricula. An a priori analysis of the game, allowed to describe in an effective way, how each programming concept is transformed in the game, through a construction and animation metaphor, in terms of 3D objects and learner's interactions fostered by this transformation (e.g. a visible and interactive 3D component is a metaphor of a computing object, colouring or rotating a 3D component is a metaphor of a method call, ...). The choices made through this metaphor, aim to trigger a play situation when learners interact with the construction game (i.e. the source situation). This analysis showed clear analogies between the source and target situations, and the meaning of the considered concepts is maintained.

This work is a contribution to computer science didactic and game design. Indeed, didactic transposition approached from the perspective of metaphorisation and ludicisation, revealed a powerful tool for game design analysis in the case of object-oriented programming learning. In addition, debriefing was identified as an essential element in the didactic transposition process. Indeed, debriefing is the reverse process of metaphorisation. It provides students with a means to take a step backward after the game session and to identify the knowledge embedded in the metaphor, and, by doing so, to be able to transfer the gained knowledge to other situations. Indeed, if this paper describes the process of contextualising knowledge in a metaphorical and playful learning situation, this process needs to be reversed by another process that allows the conversion of subjective and implicit knowledge into explicit knowledge. Both processes consist of important and needed transformations of knowledge that educators should take into consideration. This work open new perspectives for understanding how game-based learning occurs. In particular, it motivate future work about the role of debriefing to helping students to understand the analogical relationships between the source and the target situation. For example, it could be relevant to study whether students establish links between the object-oriented programming concepts and the properties of the graphical objects they see and manipulate with the Progo interface, and how this can be enhanced by debriefing. It would be also interesting to analyse to what extent students are able to transfer what they learn to other similar situations. Indeed, we consider that game-based learning does not only results from gaming. Game-based learning results from a metacognitive process on the gaming experience which allows for the transfer of knowledge.

Fig. 1

 1 Fig. 1 Didactic engineering defining the objects-first approach.

Fig. 2

 2 Fig.2Didactic transposition framework(Bonnat et al., n.d.).

Fig. 3

 3 Fig. 3 Didactic transposition model applied to the Progo game.

Fig. 4

 4 Fig. 4 3D constructions realised by students when playing with Progo.

Fig. 5

 5 Fig.5Modifying attribute values and making method calls, both in the 3D scene and in the code editor.

Fig. 6

 6 Fig. 6 Generated declaration code of a new class called Robot.

Fig. 7

 7 Fig. 7 UML Class diagram modelling a Progo 3D construction.

Table 1

 1 Object-oriented fundamentals embedded within three didactic steps.

	Didactic step	Programming concept
	1) Using objects	1.1. Relationship between an object and a class: an object results
		from a class instantiation.
		1.2. Object characteristics: an object is characterised by
		attributes and methods.
		1.3. Object state: attribute values and method calls.
	2) Creating classes	2.1. Class role: a class allows for the description of object
		properties. It is a new data type.
		2.2. Class encapsulation: hiding internal data and methods from
		the outside of a class.
		2.3. Class constructor: function of a class that allows creating and
		initialising new objects of that class.
	3) Design principles	3.1. Association: relationship between classes of objects. Each
		Object is connected to another, knowing its reference.
		3.2. Aggregation: symmetric association between classes repre-
		senting a "ensemble/element" relationship. Both the entities can
		exist individually.
		3.3. Composition: form of aggregation in which two entities are
		highly dependent on each other, representing a "part-of" rela-
		tionship. The composed object can not exist without the other
		entity.
		3.4.

Inheritance: represent a relationship between classes, where an inherited class is a subclass of its parent class or super class. An object created through inheritance acquires all the properties of the super class.