Unweighted Layered Graph Traversal
Xingjian Bai Christian Coester Romain Cosson


[
    [
    25 April 2024
=================




Introduced by Papadimitriou and Yannakakis in 1989, layered graph traversal is an important problem in online algorithms and mobile computing that has been studied for several decades, and which now is essentially resolved in its original formulation. In this paper, we demonstrate that what appears to be an innocuous modification of the problem actually leads to a drastic (exponential) reduction of the competitive ratio. Specifically, we present an algorithm that is (log^2 w)-competitive for traversing unweighted layered graphs of width w. Our technique is based on a simple entropic regularizer, which evolves as the agent progresses in the layered graph. Our algorithm is randomized and simply maintains that at all layers, the probability distribution of the position of the mobile agent maximizes the entropic regularizer. 



empty
arabic



§ INTRODUCTION

Exploring an unknown environment with a mobile agent is a fundamental task in robotics and artificial intelligence <cit.>. Despite its importance, very few models allow for rigorous worst-case analysis, especially when the environment is a general graph (or metric space). One successful model introduced in the field of online algorithms is called `layered graph traversal', and it has been studied extensively since the 1990s <cit.>. In this paper, we show that a simple and natural assumption on the problem – specifically, that the unknown graph is unweighted – drastically reduces its competitive ratio. 



  
Problem setting. In layered graph traversal, a mobile agent starts from an arbitrary node – called the source – of an unknown weighted graph G=(V, E), and is tasked to reach another arbitrary node – called the target. The graph is divided into “layers”, where the t-th layer refers to the set of nodes at combinatorial depth t (i.e. t hops away from the source).  The agent is short-sighted in the sense that it only gets to see layer t+1 once it is located at layer t. Luckily, the agent is broad-sighted, in the sense that it sees all nodes and edges going from layer t to layer t + 1 when it reaches layer t. The problem is parameterized by the width w of the graph, defined as the maximum number of nodes in a layer. 
The cost of the agent is defined as the total distance travelled until reaching the target. A deterministic (resp. randomized) algorithm for layered graph traversal is said to be c(w)-competitive if its cost (resp. expected cost) is at most c(w) times the length of the shortest path from source to target. The deterministic competitive ratio of layered graph traversal is known to lie between Ω(2^w) <cit.> and (w 2^w) <cit.> and its randomized counterpart was settled to Θ(w^2) in <cit.>. It is known <cit.> that layered graph traversal is equivalent to the special case where the graph is a tree and all edge lengths are either 0 or 1.

Despite receiving broad interest, the unweighted variant (where all edge lengths are exactly 1) was not studied until <cit.> recently proposed a (√(w))-competitive randomized algorithm, improving over the simple Θ(w) competitive ratio of the depth-first search algorithm.






  
Our results. In this paper, we show that the assumption that the graph is unweighted allows for an even more drastic improvement in the competitive ratio, reducing it to (log^2 w). Our algorithm leverages the mirror descent framework <cit.>, though it is extremely simple: when the t-th layer is revealed, the agent moves in a way that its probability distribution over the t-th layer maximizes an entropy defined on the layered tree. The majority of this paper is dedicated to proving this randomized upper bound. A few simple motivating results, such as tightness of 2w-1 for deterministic algorithms (achieved by depth-first search), a randomized lower bound of Ω(log w), and some natural randomized algorithms that fail to provide competitive guarantees, are surveyed in Appendix <ref>.




 §.§ Overview of techniques and relation to prior mirror descent based online algorithms
 Mirror descent has led to significant advances in the field of online algorithms recently <cit.>. These results are based on a regularization function Φ that is typically a perturbed negative entropy, such as Φ(x)=∑ (x_i+δ)log(x_i+δ) in its simplest forms, where x describes the configuration of the algorithm. Here, δ>0 is a perturbation term needed to ensure that the Lipschitz constant of Φ is bounded. In the continuous-time mirror descent framework <cit.>, an algorithm is described by a differential inclusion

    ∇^2 Φ()-γ∈ -N_K,

where  is the time derivative of , γ is the “desired direction of movement”, and N_K is the normal cone of the polytope K of configurations. Although our algorithm also satisfies such an inclusion, it can be formulated even more simply as

    x(t) = _x∈ KΦ_t(x),

where Φ_t is a time-varying regularizer. This formulation, in fact, yields a memoryless algorithm since the selected Φ_t only depends on the tree distances between the nodes of the current layer.

Specifically, we choose

    Φ_t(x)=∑_u x_ulog x_u = ∑_u h_p(u)x_ulogx_u/x_p(u),

where the sum is over vertices u of the Steiner tree of the current layer,
x_u is the algorithm's probability of moving to the subtree rooted at u, p(u) is the parent of u, and h_u denotes the height of u in the tree at time t. Note that this quantity is well-defined only because the tree is unweighted, and all nodes at the last layer are at the same combinatorial depth. 
See Appendix <ref> for the identity between the two sums. Remarkably, this simple formulation does not involve any perturbation terms δ.

The analysis of the proposed algorithm is split into dead-end phases and growth phases, which at a high level resemble similar phases previously considered in the “evolving tree game” of <cit.>. However, the actual analysis of these phases has little in common with <cit.> and requires several novel ideas.

The right-hand side of equation (<ref>) resembles the “conditional entropy” regularizer used in <cit.> to obtain an (log n)-competitive algorithm for metrical task systems on hierarchically separated trees.[The regularizer used in <cit.> is of the form ∑_uw_u/η_u(x_u+δ_u x_p(u))log(x_u/x_p(u)+δ_u), where w_u has a similar meaning to h_p(u) in our case, and η_u and δ_u are suitable parameters.] However, the analysis in <cit.> requires that the depth of the tree is at most logarithmic in the number of leaves and that edge lengths decrease geometrically along every root-to-leaf path. Since the depth of the tree (even if merging edges where possible) could be as large as w-1 in our case, a naïve adaptation of the analysis from <cit.> would fail to achieve a sublinear competitive ratio in our setting. The high depth of the tree is also an obstacle leading to the competitive ratio Θ(w^2) in the algorithm from <cit.> for weighted layered graph traversal. To handle this difficulty and achieve a competitive ratio of (log^2w), a key idea of our proof is to separate the analysis of movement cost when handling “dead-ends”, where the probability mass x_ℓ of a leaf ℓ decreases to 0, into two substeps that are analyzed differently depending on whether x_ℓ is smaller or greater than 1/poly(w). Another interesting aspect – which echoes the technique used in <cit.> – is that the value of the regularizer appears in the potential function, in place of the Bregman divergence to an optimal configuration. This is necessitated by the fact that the Lipschitz constant of Φ_t, even when evaluating it only at the online algorithm's actual configuration, can be Ω(w). Finally, we note that unlike most prior work relying on entropic regularization, our algorithm can alternatively be expressed with elementary operations from the layered tree structure (see Lemma <ref>).   

The analysis of growth steps requires bounding the movement cost when the algorithm redistributes its probability to adapt to the distances between nodes in the new layer (note that the distance between two nodes is 2h_u, where u is their least common ancestor). Bounding this movement is based on deriving relationships between the algorithm's probability mass in sibling subtrees and the number of leaves in these subtrees.



 §.§ Related works
 The setting of layered graph traversal was introduced in a paper titled `Shortest path without a map' by Papadimitriou and Yannakakis, motivated by applications in navigation robotics <cit.>. For the case of w=2, they showed that the deterministic variant of the problem is essentially equivalent to linear search, a problem which dates back to <cit.> for which the competitive ratio is equal to 9 <cit.>. The first competitive analysis for arbitrary values of w∈ was obtained by <cit.>, which coined the term `layered graph traversal' to emphasize how the agent collects information (i.e., the feedback). The problem was also studied in the same period by <cit.>, which preferred the denomination `metrical service systems' to highlight its connection to the emerging setting of metrical task systems <cit.>. 
The denomination `small set chasing' was also recently suggested by <cit.> to point out its connection with more recent works on set chasing (see, e.g. <cit.>). Following a series of improvements <cit.>, the competitive ratio of the deterministic variant of the problem was proved to lie between (w2^w) <cit.> and Ω(2^w) <cit.>. More recently, the competitive ratio of the randomized variant of the problem was resolved up to a constant factor, establishing it at Θ(w^2) <cit.>. The study of the unweighted setting was recently introduced by <cit.>, who provided a (√(w))-competitive algorithm, leaving a substantial gap compared to the classical Ω(log w) lower-bound. This paper significantly narrows this gap by presenting a (log^2 w)-competitive algorithm. 
Additionally, layered graph traversal has also found applications in the context of learning-augmented algorithms, where it is used to combine several algorithms or predictions into a hybrid algorithm <cit.>.


Exploration of an unknown environment by a mobile agent. In layered graph traversal, the agent's objective can be restated as follows: the agent must build a complete map of the underlying graph using the fewest moves possible. 
Graph exploration with a mobile agent has attracted attention since the 19th century <cit.>, marked by the formal introduction of the depth-first search (DFS) as a maze-solving algorithm. 
DFS is particularly suited for exploring general unknown graphs when the agent is short-sighted and narrow-sighted: the agent traverses all m edges in exactly 2m moves, which is optimal in the sense of the competitive ratio. A natural extension of this problem is when the agent can also see its immediate neighborhood (a little less short-sighted) <cit.>. This setting is known as `online graph exploration' <cit.>, and the goal is for the agent to visit all nodes while incurring a limited cost with respect to the optimal tour (i.e., the solution of the traveling salesman problem). The competitive ratio for that problem is still unsettled (it lies between Ω(1) and (log n), where n is the number of nodes in the graph) but many restricted classes of graphs admit (1)-competitive algorithms, such as planar graphs or some minor-excluded graphs (see <cit.> and its references). In contrast, layered graph traversal proposes a different model of feedback where the agent gets to see all nodes and edges simultaneously at some given hop distance from its initial position. This setting is particularly well-motivated when the graph evolves with time (e.g., a phylogenetic tree). Many other graph exploration settings have been introduced, varying the capabilities of the agents, e.g., with limited memory <cit.>, limited storage capabilities <cit.>, or if it can coordinate with a series of teammates <cit.>. For a recent review of graph exploration problems, we refer to the introduction of <cit.>. Contrarily to the aforementioned examples, this paper studies the case of a single, fully-competent agent. 





 §.§ Notations and preliminaries
 

Consider a graph G=(V, E) defined by a set of nodes V⊂ and edges E over V, where  is an arbitrary countable set. 
The edges are undirected and unweighted, and the graph is connected. One node is called the root and is denoted by r∈ V. For some t∈, we denote by (t) the set of nodes at combinatorial depth t, i.e., t hops away from the root. We will refer to (t) as the t-th layer of the graph.
The width w of the graph is defined as the maximum cardinality of its layers, i.e., w = max_t |(t)|. As standard in layered graph traversal, the goal to reach a certain target can be equivalently simplified to reaching the last layer of the graph. 

Reduction to trees. For any node u ∈ V, we denote by t_u the combinatorial depth of u, i.e. satisfying u∈(t_u). At any step t≥ t_u, we call h_u(t) = t-t_u the height of u. For any node u∈ V∖{r}, we can arbitrarily pick a node of the preceding layer p(u) ∈(t_u-1), such that (p(u),u)∈ E.[Observe that the choice of p(u) can be made online by the agent. The reduction from graphs to tres is standard in the literature on layered graph traversal. Here, we use the assumption that any non-root node is connected to a node in the preceding layer because a layer refers to the set of nodes at the same combinatorial depth. We note that this assumption is not required in the weighted variant of the problem; see <cit.>. For more motivation on the setting of this paper, we refer to <cit.>.] It is clear that traversing the tree formed by T={(p(u),u)| u∈ V∖{r}}⊆ E in an online manner is no less difficult than traversing the original graph. For this reason, we will focus the rest of the paper on the specific case where the layered graph is a tree. For any node u∈ V, we denote by c(u)⊂ V the set of its children of u, and by _u(t) the subset of nodes of (t) that are descendants of u, for some t∈. We also denote by u→ r ⊂ V the set of all nodes in the path from u to r, excluding r. 



Layered graph traversal algorithm. Formally, a randomized unweighted layered graph traversal algorithm is defined by a function  : ×→() mapping a tree T ∈ and a node u∈ in the penultimate layer of T to a distribution ∈() over the set of nodes in the ultimate layer of T.
The algorithm is deterministic if the distribution is always supported on a unique node. The cost of the algorithm is defined as the total number of edges traversed by an agent that picks its next position using  at each layer and uses the shortest paths to move between positions elected in consecutive layers. The total cost of an agent until reaching layer t is denoted by (t) and depends on the random choices taken by the agent. The algorithm is c(w)-competitive if, for any graph of width w and any step t, it satisfies ((t))≤ c(w)t. If the algorithm is deterministic, the expectation can be dropped. 

Fractional perspective on unweighted layered graph traversal. A classical equivalent perspective on layered graph traversal – which is referred to as the fractional view – is that the algorithm :→() maintains a distribution on the ultimate layer of the tree given as input. The movement cost charged to the algorithm is then the optimal transport cost between the two consecutive distributions. Given a fractional algorithm for layered graph traversal, one gets a randomized algorithm with the same cost by considering at each step an optimal coupling between the two consecutive distributions and sampling the next position of the agent according to the conditional distribution associated with its current position. We refer to <cit.> for more details on the reduction. 

The active tree and the active polytope. At any layer t, we will essentially focus on the subtree of that is the Steiner tree of (t)∪{r} and denote its set of vertices by V(t),
i.e., containing only r and the nodes on the paths ℓ→ r for ℓ∈(t). We will refer to this subtree as the `active subtree' and edges contained in this subtree as `active edges.' We will denote by (t) ∈((t)) the probability distribution associated with the position of the agent on the t-th layer. Instead of viewing  as a probability distribution, it will be useful to consider it more generally as a point of the active polytope, K(t) that we define as,

    K(t) = {∈^V(t)∖{r}|∀ u ∈ V(t) ∖(t) x_u = ∑_v∈ c(u)x_v }.

We emphasize that x_r is defined once and for all to be 1. For that reason, it does not appear as a variable in the definition of the active polytope above (but x_r does appear in one constraint, which effectively enforces ∑_ℓ∈(t)x_ℓ(t) =1). We note that a probability distribution must also satisfy non-negativity constraints, which are not explicit in K(t). It will be obvious that the configuration (t)∈ K(t) defined by our algorithm satisfies the positivity constraints (with strict inequality) and can indeed be interpreted as (t) ∈((t)).
We note that K(t) can be viewed as an affine subspace, supported by the tangent vector space K̅(t) = Vect({_u-∑_v∈ c(u)_v: u∈ V(t) ∖(t) })^⊥ of flows. We also define the normal cone N_K(t) associated with K(t), which is in this simple case always the space orthogonal to K̅(t), i.e.,

    N_K(t) = {ξ∈^V(t) ∖{r} : ξ_u = λ_p(u)-λ_u   with λ∈^V(t) and λ_ℓ = 0  for ℓ∈(t)}.


Optimal transport in a tree. For two given configurations, (t) ∈ K(t) and (t + 1)∈ K(t + 1), we denote the optimal transport cost (also known as the earth-mover distance) between (t) and (t + 1) by ((t),(t + 1)). 
Extending the definition of a configuration to take value zero outside of the active polytope, the optimal transport cost on a tree is classically expressed as

    (,') = ∑_u∈ V|x_u'-x_u|.

We note that this definition matches the usual definition of optimal transport on the metric space associated with the underlying tree. 

Derivatives and instantaneous movement costs. The derivative of a differentiable real function f(·) with respect to a single variable s∈ will be denoted by ∂_s f(s). The gradient of a twice-differentiable multivariate function Φ() will be denoted by ∇Φ(), and its Hessian will be denoted by ∇^2 Φ(). For convenience, when the function that is differentiated is a configuration (s) ∈ K(t), we will adopt the physicist's notation and denote its derivative ∂_s (s) by . Thus, at an arbitrary node u∈ V(t), we will also denote ∂_s x_u(s) by ẋ_u. In general, we will often drop dependence on time when it is clear from the context. We observe that if ∀ s: (s)∈ K(t), it must be the case that (s) is in the previously defined tangent space of flows, i.e. (s) ∈K̅(t). In this case, we will define the instantaneous movement cost at instant s as 

    ∂_s (s) = ∑_u∈ V(t)|ẋ_u|.

By the triangle inequality, it is clear that for any two configurations ∈ K(t) and '∈ K(t), if (s) is a differentiable function with respect to s, interpolating between (a)= and (b)=' for a<b, we have (,') ≤∫_a^b ∂_s (s)ds.

Convexity. For some twice differentiable convex function Φ defined on an open domain U, we denote the Bregman divergence associated to Φ by D(·,·). It is defined for any , ' ∈ U^2 as, D(',) = Φ(')-Φ() -∇Φ() ('-), and it is always non-negative. 






§ ALGORITHM AND ANALYSIS

In this section, we present and analyze our algorithm for layered graph traversal, which is stated here in its fractional formulation (see Section <ref> for definition). When reaching layer t∈, the algorithm chooses the configuration (t) that is the minimizer of the following expression, 

    (t) ∈_∈ K(t)∑_u∈ V x_u log x_u,

which 
we denote by Φ_t.[We note that Φ_t is defined on the open domain U = _++^V(t) and that the minimizer is effectively taken on  K(t) ∩ U. Such minimizer exists due to the property that ∂_x_uϕ() → -∞ when x_u→ 0. It is also unique, by strong convexity of Φ_t.] 
We observe that Φ_t can equivalently be rewritten as

    Φ_t()  = ∑_u∈ V(t) x_u log x_u = ∑_u∈ V(t)∖{r}h_p(u)(t)x_ulogx_u/x_p(u),

where h_p(u)(t) denotes the height of p(u) at time t. See Appendix <ref> for details. The rest of this section is devoted to proving the following theorem, which is the main result of the paper. 
 The fractional algorithm defined by (<ref>) is (log^2 w)-competitive for unweighted layered graph traversal. In other words, the associated randomized algorithm satisfies for any unweighted graph of width w that its cost up to layer t is bounded by 

    ((t)) ≤(log^2 w)· t.



Proof sketch.
For any layer t∈, we define the potential,

    P(t) = 4L(t)/w + 4log w ·Φ_t((t)) + 6(1+log w)^2t,

where L(t) denotes the number of edges that have been deactivated before layer t (see Section <ref>). We will prove that the cost of the fractional algorithm up to time t – which we denote by (t) – is always bounded by the potential, 

    (t) ≤  P(t).

Since L(t) ≤ wt and Φ_t((t))≤ 0, this implies that at any layer t∈, (t) ≤(log^2 w)· t.

The proof is by induction on t. When moving from layer t to layer t+1, the goal is to show that the variation of the cost, which equals ((t),(t+1)), is at most the variation of the potential, which is equal to P(t+1)-P(t). Instead of considering the optimal transport from (t)∈ K(t) to (t+1)∈ K(t+1), we consider a series of (possibly sub-optimal) phases that together form a transport between (t) and (t+1). There are two main phases.


    
  * For each node ℓ∈(t) that does not have a descendant in (t+1), we displace the fractional mass present at ℓ to obtain x_ℓ = 0. We call this phase the deactivation phase, as it corresponds to situations where the agent is trapped in a dead-end and cannot continue downwards. The deactivation of leaf ℓ is performed continuously by setting (s) = _x∈ K(t)Φ_t()+sx_ℓ and letting s→∞. After the deactivation of ℓ, in slight abuse of notation, we remove ℓ from the set V(t) and write K(t) for the new corresponding polytope. 
    After consecutively removing all dead-ends, we obtain a new configuration, ', and re-interpret it as a point in K(t+1) by setting x_ℓ=x_p(ℓ)/|c(p(ℓ))| for each ℓ∈(t+1).
    At this point, we have ' ∈_∈ K(t+1)Φ_t(). 
    
    
  * Then, we consider the configurations (s) = _∈ K(t+1)Φ_t()+s∑_ℓ∈(t+1)x_ℓlog x_ℓ for values of s that increase continuously from 0 to 1, which interpolate between ' and (t+1). We call this the growth phase.
    Here, although (s)∈ K(t+1), we still only update the configuration on (t) while s changes from 0 to 1 by considering the projection of (s) onto K(t), i.e., we don't advance to the new layer in the growth phase. 
    After the growth, we add a cost of 1 to account for the ultimate movement from (t) to (t+1).


To complete the proof, we shall show that the main inequality (<ref>) is preserved by both deactivation and growth phases. These phases are respectively treated in Section <ref> and Section <ref>. 



 §.§ Explicit algorithm and basic lemmas


In this section, we establish some fundamental properties of the algorithm. The proofs of these lemmas are deferred to Appendix <ref>.

The following lemma (specialized with γ=0) explicitly describes the configuration of the algorithm at any given layer by specifying the probabilities x_u/x_p(u) of being in the subtree of u conditioned on being in the subtree of p(u). 


    Let γ∈^ and
    
    =_∈ K∑_u∈ V∖{r}h_p(u)x_ulogx_u/x_p(u) + ∑_ℓ∈γ_ℓ x_ℓ.

    Then for each u∈ V∖{r},
    
    x_u/x_p(u) = y_u/∑_v∈ c(p(u))y_v,

    where y_u is defined recursively via
    
    y_u=
                e^-γ_u/h_p(u)   if u∈
    (∑_v∈ c(u) y_v)^h_u/h_p(u)     if u∉.

    In particular, if γ=0, then 1≤ y_u≤ |_u|.


As we will consider continuously evolving configurations, it will be useful to understand their dynamics. These are expressed most naturally by differential equations describing the evolution of the conditional probabilities x_u/x_p(u). The premise (<ref>) of the following lemma will be satisfied for different functions γ in deactivation and growth steps.


    Let γ [0,∞)→^ and x[0,∞)→ K be continuously differentiable and satisfy x_u(s)>0 for all u∈ V, s∈[0,∞) and

    ∇^2 Φ((s))(s) +∑_ℓ∈γ_ℓ(s)_ℓ∈ -N_K

for all s∈[0,∞). Then for each node u∈ V∖{r},
    
    ∂_sx_u/x_p(u) = 1/h_p(u)x_p(u)( x_u/x_p(u)∑_ℓ∈_p(u)x_ℓγ_ℓ   -  ∑_ℓ∈_u x_ℓγ_ℓ).



The next lemma bounds the movement cost in terms of the change of the conditional probabilities.


    The instantaneous cost during continuous movement is at most
    
    2∑_u∈ V ∖{r} h_p(u)x_p(u)(∂_s x_u/x_p(u))_-,

    where we write (z)_-=max{-z,0}.



 §.§ Deactivating dead-ends

This section examines the deactivation/deletion of leaves in (t) at a given step t. For simplicity, we focus on the deactivation of a single leave, ℓ, and observe that multiple deactivations could take place consecutively without loss of generality. 
Note that ' represents the new configuration after all deactivations. In a slight abuse of notation, we denote by ' the configuration right after the deactivation of ℓ, which is defined by

    ' = _∈ K(t)  and  x_ℓ = 0Φ_t().

Then, we consider the resulting change of the potential, which can be expressed as:

    Δ P = 4d_ℓ/w + 4log w·(Φ_t(')-Φ_t((t))),

where d_ℓ denotes the total number of edges deactivated in this step, which also equals the number of nodes with ℓ as their only active descendant before its deactivation (d_ℓ≥ 1, because ℓ itself counts as one such node). Our goal is to bound the cost of this deactivation under the increase of the potential, i.e., to show that

    ((t),')≤Δ P.




For s∈[0,∞), we define

    (s) = _∈ K(t)Φ_t()+s x_ℓ.

We start by stating the following claims on (s): 

    The following statements are satisfied:
    
    
  * (s) satisfies the explicit form given in Lemma <ref> with γ(s)=s_ℓ. Therefore, it is differentiable, and (s) converges to '.
    
  * (s) satisfies the mirror descent equation ∇^2Φ_t((s)) (s) ∈ - _ℓ - N_K(t) and thus, the dynamics given by Lemma <ref>. Also, ∂_s D(',(s)) = - x_ℓ(s) and ẋ_ℓ(s) ≤ - 1/2d_ℓx_ℓ(s).    




We provide a short proof of the above claims.

<ref> Explicit form. (s) clearly satisfies the conditions of Lemma <ref>. Since the expression only involves differentiable operations, (s) is differentiable. Convergence to ' holds because the explicit form of (s) converges to the explicit form of ' (which is given by invoking Lemma <ref> with γ=0 and the polytope K where the leaf ℓ is removed).

<ref> Mirror descent. For any s≥ 0, the optimality of (s) implies ∇Φ_t((s))+s_ℓ∈ -N_K(t). Taking the derivative with respect to s, we obtain, ∇^2 Φ_t((s))(s) ∈ -_ℓ-N_K(t). By definition of the Bregman divergence, ∂_s D(',(s)) = (s)^T∇^2Φ_t((s))((s)-') = -x_ℓ(s), where we used that x_ℓ' = 0 and that (s)-' is orthogonal to N_K(t). Then, applying Lemma <ref> to the lowest node u on the path ℓ→ r that has an active sibling, and observing that (x_ℓ(s),ẋ_ℓ(s)) = (x_u(s),ẋ_u(s)) and that h_p(u)=d_ℓ, we have d_ℓ(ẋ_ℓ/x_ℓ - ẋ_p(u)/x_p(u)) = x_ℓ/x_p(u)-1. Then, by Lemma <ref>, we have x_ℓ/x_p(u)≤ 1/2  and ẋ_p(u)≤ 0, since all conditional probabilities on ℓ→ r are non-increasing. Therefore, d_ℓẋ_ℓ/x_ℓ≤ -1/2.


Using claim <ref> above, we note that

    ∫_s=0^∞ x_ℓ(s)ds =  -∫_s=0^∞∂_s D(',(s))ds = D(',(t)) =Φ_t(')-Φ_t((t))

where the last equation uses that ∇Φ_t((t)) ∈ -N_K(t) (by optimality of (t)) is orthogonal to '-(t).

For the deactivation step, in light of (<ref>) and (<ref>), it therefore suffices to prove that 

    ((t),')  ≤4d_ℓ/w +4 log w∫_s=0^∞ x_ℓ(s) ds.

Since x_ℓ(s) is decreasing during the deletion of ℓ, if x_ℓ(t)>1/w^2, there exists an instant s̅> 0 such that x_ℓ(s) ≥ 1/w^2 for s≤s̅ and  x_ℓ(s) ≤  1/w^2 for s≥s̅. If x_ℓ(t)≤ 1/w^2, we simply set s̅ = 0. By the triangle inequality, ((t),')≤∫_s=0^∞∂_s (s)ds.
To achieve the above goal (<ref>), it will thus suffice to prove the two following equations:

    ∫_s=0^s̅∂_s (s)ds    ≤ 4 log w ∫_s=0^s̅ x_ℓ(s)ds,
    ∫_s̅^∞∂_s (s)ds    ≤ 4d_ℓ /w




Applying Lemma <ref> and Lemma <ref> with γ = _ℓ, the instantaneous cost during deactivation of leaf ℓ satisfies

    ∂_s (s)    ≤ 2x_ℓ∑_u∈ℓ→ r(1-x_u/x_p(u)).

In particular, this shows that ∂_s (s) ≤ 2w x_ℓ, because w bounds the number of non-zero terms in the above sum. Together with the claim <ref> that x_ℓ≤ -2d_ℓẋ_ℓ, we get that

    ∫_s̅^∞∂_s (s)ds ≤ -4d_ℓ w∫_s = s̅^∞ẋ_ℓ(s) ds = 4d_ℓ w x_ℓ(s̅) ≤ 4d_ℓ /w,

which proves equation (<ref>).

To conclude, we now need to prove (<ref>). 
Since z≤ e^z-1 for all z∈,

    x_ℓ = ∏_u∈ℓ→ r(x_u/x_p(u)) ≤exp(-∑_u∈ℓ→ r(1- x_u/x_p(u)) ).

For s< s̅, since x_ℓ(s) ≥ 1/w^2 we have that ∑_u∈ℓ→ r(1- x_u/x_p(u)) ≤ 2log w. In turn, using (<ref>), we get that

    ∂_s (s) ≤ 4log w · x_ℓ,

which completes the proof of our first goal (<ref>).





 §.§ Growing the tree

In this section, we will account for the growth of the tree by interpolating continuously between the configuration defined after all deactivations, ', and the configuration defined at the next layer (t+1). We consider the following trajectory, where we now have for s∈ (0,1],

    (s) = _∈ K(t+1)Φ_s()   where  Φ_s() = Φ_t()+s∑_ℓ∈(t+1)x_ℓlog x_ℓ.

Though the configuration is now defined as in K(t+1), we will not pay for movements between layer t and layer t+1. This is because, as explained in the proof sketch, we only effectively move the probability mass from ((t)) to ((t+1)) at the very end, leading to a movement cost of 1 that will be accounted for in the variation of the potential. 

The change of the potential in a growth step is given by Δ P = 4log w ·(Φ_t+1((t+1))-Φ_t('))+6(1+log w)^2. 
Taking the derivative with respect to s in Φ_s((s)) yields, by the optimality of (s), 
∂_s Φ_s((s)) = ∑_ℓ∈ℒ(t+1) x_ℓ(s) log x_ℓ(s) ≥ -log w.
Rewriting Φ_t+1((t+1))-Φ_t(') = ∫_s=0^1 ∂_s Φ_s((s))ds, we obtain that the variation of the potential satisfies

    Δ P ≥ 2(1+log w)^2+1.

We use the “+1” term to pay for the movement from (t) to (t+1) at the end.
Thus, to preserve (<ref>), it suffices to show that the instantaneous movement cost, for s∈ [0,1], is bounded as

    ∂_s (s)≤ 2(1+log w)^2.

We now note that (s) satisfies ∇^2 Φ_s() +∑_ℓ∈(t+1) (1+log x_ℓ)_ℓ∈  - N_K(t+1). Since ∑_ℓ∈(t+1)_ℓ∈ N_K(t+1), we can rewrite this expression as

    ∇^2 Φ_s() + ∑_ℓ∈(t+1)log x_ℓ·_ℓ∈ - N_K(t+1).

In light of Lemma <ref> we have for all u∈ V(t), 

    ∂_s x_u/x_p(u) = 1/h_p(u)x_p(u)( x_u/x_p(u)∑_ℓ∈_p(u)(t+1)x_ℓlog x_ℓ -∑_ℓ∈_u(t+1) x_ℓlog x_ℓ),

where we define h_p(u) = h_p(u)(t)+s. By Lemma <ref>, we recall that the continuous movement is bounded by

    ∂_s (s)    ≤ 2∑_u∈ V(t)∖{r}h_p(u)x_p(u)(∂_s x_u/x_p(u))_- 
       = 2∑_u∈ V(t)∖{r}(x_u/x_p(u)∑_ℓ∈_p(u)(t+1)x_ℓlog x_ℓ -∑_ℓ∈_u(t+1) x_ℓlog x_ℓ)_-.


For a node p∈ V(t)∖(t), let c^-(p)⊂ c(p) denote the set of children u of p that have a non-zero contribution to this sum, i.e., satisfying x_u/x_p∑_ℓ∈_px_ℓlog x_ℓ -∑_ℓ∈_u x_ℓlog x_ℓ<0, and let c^+(p)=c(p)∖ c^-(p). Let _p^+ = ⋃_u∈ c^+(p)_u(t+1), w_p^+=|_p^+| and x_p^+ = ∑_u∈ c^+(p)x_u = ∑_ℓ∈_p^+x_ℓ, and define _p^-, w_p^- and x_p^- similarly, so that x_p^++x_p^-=x_p and _p^+∪_p^-=_p(t+1). Then

    ∑_u∈ c(p)(x_u/x_p∑_ℓ∈_p(t+1)x_ℓlog x_ℓ -∑_ℓ∈_u(t+1) x_ℓlog x_ℓ)_-   = ∑_ℓ∈_p^- x_ℓlog x_ℓ - x_p^-/x_p∑_ℓ∈_p(t+1)x_ℓlog x_ℓ
       = x_p^+/x_p∑_ℓ∈_p^-x_ℓlog x_ℓ - x_p^-/x_p∑_ℓ∈_p^+ x_ℓlog x_ℓ
       ≤x_p^+x_p^-/x_plog x_p^- - x_p^-x_p^+/x_plogx_p^+/w_p^+
       ≤x_p^+x_p^-/x_plog(w_p^+w_p^-).

where the first inequality uses that ∑ x_ℓlog x_ℓ subject to the constraints x≥ 0 and ∑ x_ℓ=x_p^- (resp. ∑ x_ℓ=x_p^+) is maximized (resp. minimized) when all mass is concentrated on a single leaf (resp. spread equally across the w_p^+ leaves), and the last inequality follows from the (yet unproven) relation

    x_p^-≤ x_p^+w_p^-.


To see that (<ref>) is true, note that by Lemma <ref>, there exist 1≤ y_u≤ |_u| such that

    x_p^+/x_p = ∑_u∈ c^+(p)y_u/∑_u∈ c(p)y_u≥1/1+∑_u∈ c^-(p)|_u| = 1/1+w_p^-.

Applying this twice, we get

    x_p^+w_p^-/x_p≥w_p^-/1+w_p^- = 1 - 1/1+w_p^-≥ 1 - x_p^+/x_p = x_p^-/x_p,

and multiplying by x_p yields (<ref>).

Combining (<ref>) and (<ref>) yields

    ∂_s(s) ≤ 2∑_p∈ V(t)∖(t)x_p^+x_p^-/x_plog(w_p^+w_p^-).




Finally, our objective (<ref>) is implied by invoking the following lemma with u=r.


    For each u∈ V(t), writing V_u⊆ V(t) for the nodes in the subtree rooted at u and w_u=|_u(t+1)|, it holds that
    
    ∑_p∈ V_u∖(t)x_p^+x_p^-/x_plog(w_p^+ w_p^-)≤ x_u (1+log w_u)^2.




    We proceed by induction on the level of u. If u∈(t), the inequality follows trivially since the left-hand side is an empty sum.

    For the induction step, consider some u∈ V(t)∖(t). Then 
    
    ∑_p∈ V_u∖(t)x_p^+x_p^-/x_plog(w_p^+ w_p^-)    = x_u^+x_u^-/x_ulog(w_u^+ w_u^-) + ∑_v∈ c(u)∑_p∈ V_v∖(t)x_p^+x_p^-/x_plog(w_p^+ w_p^-) 
       ≤x_u^+x_u^-/x_ulog(w_u^+ w_u^-) + ∑_v∈ c(u)x_v(1+log w_v)^2
       ≤x_u^+x_u^-/x_ulog(w_u^+ w_u^-) + x_u^+(1+log w_u^+)^2 + x_u^-(1+log w_u^-)^2

    where the first inequality follows from the induction hypothesis. We may assume w_u^-≥ 1 and w_u^+≥ 1, since otherwise x_u^+ or x_u^- is 0 and the lemma follows directly from the induction hypothesis applied to the children of u.
    Dividing by x_u and writing q:=x_u^+/x_u, so that 1-q=x_u^-/x_u, it remains to show that
    
    q(1-q)log(w_u^+w_u^-) + q(1+log w_u^+)^2 + (1-q)(1+log w_u^-)^2    ≤ (1+log w_u)^2

    for all q∈[0,1].

    By concavity of w↦(1+log w)^2 for w≥ 1, we have
    
    q(1+log w_u^+)^2 + (1-q)(1+log w_u^-)^2 ≤ (1+log(qw_u^++(1-q)w_u^-))^2.

    By symmetry, assume w_u^+≥ w_u^-, so we can write w_u^+=(1+a)w_u^- for some a≥ 0. Using w_u=w_u^++w_u^-, and writing d:=ew_u^- (where e is the base of log), inequality (<ref>) follows if we show that
    
    q(1-q)log((1+a)d^2) + log^2((1+aq)d)    ≤log^2 ((2+a)d).

    for all q∈[0,1], a≥ 0 and d≥ e. Indeed,
    
    = q(1-q)log((1+a)d^2) + log^2((1+aq)d) - log^2 ((2+a)d)
       = q(1-q)(2log d + log(1+a)) + 2log d·log1+aq/2+a + log^2(1+aq) - log^2(2+a)
       ≤log(2+a)log1+a/2+a + log(1+aq)log1+aq/1+a
       ≤ 0,

    where inequality (<ref>) uses
    
    q(1-q)≤min{log 2,log1/q}≤log2+a/1+aq.








  
*Acknowledgements. RC would like to thank Laurent Massoulié for many insightful discussions.   


alpha





