summaries: This paper studies the derivatives of regularized M-estimators and distribution of the residual.  These results give rises to a new novel adaptive criterion for tuning loss and penalty function. Numerical experiments are conducted on various models to validate the theoretical result.

summaries: The paper is dedicated to the analysis of robust linear regression, where the proposed estimation is based on sparse M-estimation. The statistical criterion corresponds to a penalised M-estimation problem, where both the non-penalised loss function and penalty function are assumed convex. The contributions of the paper can be summarised as follows: - the authors provide a criterion for the optimal selection of the non-penalised loss and penalty function so that some out-of-sample distance, say D, is minimal.  - the authors quantify the behaviour of the penalised estimator \hat\beta using quantities depending on the observations only (idest no unknown quantities such as true sparse support) in a regime where p/n has finite limit. - some explicit derivative formulas of the penalised estimator are provided.  - the distribution of the estimated residuals is provided, which allows for a selection of the tuning parameter for regularization. - the authors derive an approximation formula of the distance D.

summaries: The authors study M-estimators with convex penalties. They give algebraic forms for derivatives of the estimator with respect to response $y$ and the design matrix $X$. They describe the distribution of residuals or certain functions of residuals. Given a loss function and penalty (with tuning parameters) they propose a criterion that can effectively approximate the out-of-sample error. This criterion can be computed without the knowledge of the covariance matrix $\Sigma$ (rows of $X \sim N(0,\Sigma)$). They give finite sample bounds that show how fast the criterion converges to the out-of-sample error.

summaries: Finding the right parameter when doing robust estimation is a recurring problem in the robust community. This article propose to choose the parameters in a robust regularized linear regression model by minimizing a completely data-driven criterion. This criterion is shown to be a good approximation to the out of sample error, this is also illustrated on practical experiments.

summaries: This paper studies M-estimators in linear models, with convex and gradient-Lipschitz loss function and a convex penalty.   Main contributions:  1. The authors provide a criterion to select tuning parameters (the loss function and the penalty function) of M-estimators, such that minimizing the criterion provides a proxy for minimizing the out-of-sample error, since the criterion is an approximation of the out-of-sample error up to a constant shift. One advantage of this criterion is that it does not require the prior knowledge of the covariance matrix of the design and the noise distribution.  2. The authors provide simulation results that confirm theoretical findings.

abstractText: This paper studies M-estimators with gradient-Lipschitz loss function regularized 1 with convex penalty in linear models with Gaussian design matrix and arbitrary 2 noise distribution. A practical example is the robust M-estimator constructed with 3 the Huber loss and the Elastic-Net penalty and the noise distribution has heavy-tails. 4 Our main contributions are three-fold. (i) We provide general formulae for the 5 derivatives of regularized M-estimators β̂(y,X) where differentiation is taken with 6 respect to both y andX; this reveals a simple differentiability structure shared by 7 all convex regularized M-estimators. (ii) Using these derivatives, we characterize 8 the distribution of the residual ri = yi−xi β̂ in the intermediate high-dimensional 9 regime where dimension and sample size are of the same order. (iii) Motivated 10 by the distribution of the residuals, we propose a novel adaptive criterion to select 11 tuning parameters of regularized M-estimators. The criterion approximates the 12 out-of-sample error up to an additive constant independent of the estimator, so 13 that minimizing the criterion provides a proxy for minimizing the out-of-sample 14 error. The proposed adaptive criterion does not require the knowledge of the 15 noise distribution or of the covariance of the design. Simulated data confirms the 16 theoretical findings, regarding both the distribution of the residuals and the success 17 of the criterion as a proxy of the out-of-sample error. Finally our results reveal 18 new relationships between the derivatives of β̂(y,X) and the effective degrees of 19 freedom of the M-estimator, which are of independent interest. 20

authors:
Mohsen Bayati
Murat A Erdogdu
Andrea Montanari

title: Estimating lasso risk and noise level

authors:
Mohsen Bayati
Andrea Montanari

title: The lasso risk for gaussian matrices

venue: IEEE Transactions 274 on Information Theory,

authors:
Pierre C Bellec
Cun-Hui Zhang

title: Second order poincare inequalities and de-biasing arbitrary 278 convex regularizers when p/n→

authors:
Stéphane Boucheron
Gábor Lugosi
Pascal Massart

title: Concentration inequalities: A 280 nonasymptotic theory of independence

authors:
Michael Celentano
Andrea Montanari

title: Fundamental barriers to high-dimensional regression 282 with convex penalties

venue: arXiv preprint arXiv:1903.10603,

authors:
Michael Celentano
Andrea Montanari
Yuting Wei

title: The lasso with general gaussian designs 284 with applications to hypothesis testing

venue: arXiv preprint arXiv:2007.13716,

venue: Proba- 286 bility Theory and Related Fields,

authors:
David Donoho
Andrea Montanari

title: High dimensional robust m-estimation: Asymptotic 288 variance via approximate message passing

venue: Probability Theory and Related Fields,

authors:
Noureddine El Karoui
Derek Bean
Peter J Bickel
Chinghway Lim
Bin Yu

title: On robust 291 regression with high-dimensional predictors

authors:
Vladimir A Marčenko
Leonid Andreevich Pastur

title: Distribution of eigenvalues for some sets 294 of random matrices

venue: Mathematics of the USSR-Sbornik,

authors:
Léo Miolane
Andrea Montanari

title: The distribution of the lasso: Uniform control over sparse 296 balls and adaptive parameter tuning

venue: arXiv preprint arXiv:1811.01212,

authors:
Fabian Pedregosa
Gaël Varoquaux
Alexandre Gramfort
Vincent Michel
Bertrand Thirion
298 Olivier Grisel
Mathieu Blondel
Peter Prettenhofer
Ron Weiss
Vincent Dubourg

title: Scikit- 299 learn: Machine learning in python

venue: The annals of 302 Statistics,

venue: arXiv preprint 304

text:
This paper studies M-estimators with gradient-Lipschitz loss function regularized1 with convex penalty in linear models with Gaussian design matrix and arbitrary2 noise distribution. A practical example is the robust M-estimator constructed with3 the Huber loss and the Elastic-Net penalty and the noise distribution has heavy-tails.4 Our main contributions are three-fold. (i) We provide general formulae for the5 derivatives of regularized M-estimators β̂(y,X) where differentiation is taken with6 respect to both y andX; this reveals a simple differentiability structure shared by7 all convex regularized M-estimators. (ii) Using these derivatives, we characterize8 the distribution of the residual ri = yi−x>i β̂ in the intermediate high-dimensional9 regime where dimension and sample size are of the same order. (iii) Motivated10 by the distribution of the residuals, we propose a novel adaptive criterion to select11 tuning parameters of regularized M-estimators. The criterion approximates the12 out-of-sample error up to an additive constant independent of the estimator, so13 that minimizing the criterion provides a proxy for minimizing the out-of-sample14 error. The proposed adaptive criterion does not require the knowledge of the15 noise distribution or of the covariance of the design. Simulated data confirms the16 theoretical findings, regarding both the distribution of the residuals and the success17 of the criterion as a proxy of the out-of-sample error. Finally our results reveal18 new relationships between the derivatives of β̂(y,X) and the effective degrees of19 freedom of the M-estimator, which are of independent interest.20
1 Introduction21
This paper studies properties of robust estimators in linear models y = Xβ∗ + ε with response22 y ∈ Rn, unknown regression vector β∗ whereX is a design matrix with n rows x1, ...,xn, each row23 xi being a high-dimensional feature vector in Rp with covariance Σ. Throughout, let β̂ = β̂(y,X)24 be a regularized M -estimator given as a solution of the convex minimization problem25
β̂(y,X) = argminb∈Rp 1 n ∑n i=1 ρ(yi − x>i b) + g(b) (1)
where ρ : R → R is a convex data-fitting loss function and g : Rp → R a convex penalty. We26 may write β̂ρ,g(y,X) for (1) to emphasize the dependence on the loss-penalty pair (ρ, g); if the27 argument (y,X) is dropped then β̂ is implicitly understood at the observed that (y,X). Typical28 examples of losses include the square loss ρ(u) = u2/2, the Huber loss H(u) = ∫ |u| 0 min(1, t)dt29 or its scaled version ρ = Λ2H(u/Λ) for some tuning parameter Λ > 0, while typical examples of30 penalty functions include the Elastic-Net g(b) = λ‖b‖1 + µ‖b‖2/2 for tuning parameters λ, µ ≥ 0.31 The paper introduces the following criterion to select a loss-penalty pair (ρ, g) with small out-of-32 sample error ‖Σ1/2(β̂ − β∗)‖2: for a given set of candidate loss-penalty pairs {(ρ, g)} and the33
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
corresponding M -estimator β̂ρ,g in (1), select the pair (ρ, g) that minimizes the criterion34
Crit(ρ, g) = ∥∥∥r+ d̂f tr[V ] ψ ( r )∥∥∥ 2 with    r = y −Xβ̂ρ,g ∈ Rn, d̂f = tr[X(∂/∂y)β̂ρ,g] ∈ R, V = diag{ψ′(r)}(In −X(∂/∂y)β̂ρ,g) ∈ Rn×n (2)
where tr[·] is the trace, ψ : R → R is the derivative of ρ, ψ′ the derivative of ψ and we extend ψ35 and ψ′ to functions Rn → Rn by componentwise application of the univariate function of the same36 symbol. Above, (∂/∂y)β̂ρ,g ∈ Rp×n denotes the Jacobian of (1) with respect to y for X fixed,37 at the observed data (y,X). As we will see while studying particular examples, for pairs (ρ, g)38 commonly used in robust high-dimensional statistics such as the square loss, Huber loss with the39 `1-penalty or Elastic-Net penalty, the ratio d̂f/ tr[V ] in (2) admits simple, closed-form expressions40 and can be computed at a negligible computational cost once β̂ρ,g(y,X) itself has been computed.41 The criterion (2) has an appealing adaptivity property: it does not require any knowledge of the noise42 ε or its distribution, nor any knowledge of the covariance Σ of the design.43
1.1 Contributions44
1. The end goal of paper is to provide theoretical justification and theoretical guarantees for the45 criterion (2) in the high-dimensional regime where the ratio p/n has a finite limit and X has46 anisotropic Gaussian distribution. The theoretical results will justify the approximation47
∥∥r + ( d̂f/ tr[V ] ) ψ ( r )∥∥2/n ≈ ‖ε‖2/n+ ‖Σ1/2(β̂ − β∗)‖2. (3)
Figure 1 illustrates the accuracy of (3) on simulated data. To study the criterion (2) and derive the48 approximation (3), we develop novel results of independent interest regarding M -estimators in (1):49
2. The paper derives general formula for the derivatives (∂/∂yi)β̂ and (∂/∂xij)β̂. This sheds light50 on the differentiability structure ofM -estimators for general loss-penalty pairs: for any ρ, g with g51 strongly convex, there exists Â ∈ Rp×p depending on (y,X) such that for almost every (y,X),52
(∂/∂yi)β̂(y,X) = ÂX >eiψ ′(ri), (∂/∂xij)β̂(y,X) = Âejψ(ri)− ÂX>eiψ′(ri)β̂j ,
for ri = yi − x>i β̂, ∀i ∈ [n],j ∈ [p] where ej ∈ Rp and ei ∈ Rn are canonical basis vectors.53
3. The paper obtains a stochastic representation for the residual yi−x>i β̂ for some fixed i = 1, ..., n,54 extending some results of [10] on unregularized M -estimators to penalized ones as in (1). In55 short, for each i = 1, ..., n the i-th residual satisfies ri = yi − x>i β̂56
ri + (d̂f/ trV )ψ(ri) ≈ εi + Zi‖Σ1/2(β̂ − β∗)‖ (4) where Zi ∼ N(0, 1) is independent of εi. This stochastic representation is the motivation for57 the criterion (2) as the amplitude of the normal part in the right-hand side is proportional to the58 out-of-sample error ‖Σ1/2(β̂ − β∗)‖ that we wish to minimize, while the variance of the noise59 εi does not depend on the choice of (ρ, g).60
Simulated data in Figure 2 confirms that the stochastic representation for the i-th residual ri =61 yi − x>i β̂ is accurate. Our working assumption throughout the paper is the following.62 Assumption 1.1. For constants γ, µ > 0 independent of n, p we have p/n ≤ γ, the loss ρ : R→ R63 is convex with a unique minimizer at 0, continuously differentiable and its derivative ψ = ρ′ is64 1-Lipschitz. The design matrix X has iid N(0,Σ) rows for some invertible covariance Σ and the65 noise ε is independent of X with continuous distribution. The penalty g : Rp → R is µ-strongly66 convex w.r.t. Σ in the sense that b 7→ g(b)− (µ/2)b>Σb is convex in b ∈ Rp.67
Throughout the paper, we consider a sequence (say, indexed by n) of regression problems with p,68 β∗, Σ and the loss-penalty pair (ρ, g) depending implicitly on n. For some deterministic sequence69 (an), the stochastically bounded notation OP (an) in this context may hide constants depending on70 γ, µ only, that is, OP (an) denotes a sequence of random variables Wn such that for any ε > 0 there71 exists K depending on (ε, γ, µ) satisfying P(|Wn| ≥ Kan) ≤ ε.72 Since Assumption 1.1 requires p/n ≤ γ, the Bolzano-Weierstrass theorem lets us extract a subse-73 quence of regression problems such that p/n→ γ′ along this subsequence, for some constant γ. This74 is the asymptotic regime we have in mind throughout the paper, although our results do not require a75 specific limit for the ratio p/n. For some results, we will require the following additional assumption76 which is satisfied by robust loss functions and penalty that shrink towards 0.77
Assumption 1.2. The penalty is minimized at 0, that is, g(0) = minb∈Rp g(b); the loss is Lipschitz as78 in |ψ| ≤M for some constant M independent of n, p; the signal is bounded as in ‖Σ1/2β∗‖2 ≤M .79
1.2 Related works80
The context of the present work is the study of M -estimators in the regime pn has a finite limit. This81 literature pioneered in [2, 10, 9, 15] typically describes the subtle behavior of β̂ in this regime by82 solving a system of nonlinear equations. This system typically depends on a prior distribution for the83 components of β∗, and either depends on the covariance Σ [7] or assume Σ = Ip [2, 16, 6, among84 many others]. Solutions to the nonlinear system are a powerful tool to understand β̂ in theory, e.g.,85 to characterize the deterministic limit of ‖Σ1/2(β̂ − β∗)‖, see e.g., the general results in [6] for the86 square loss and [16] for general loss-penalty pairs. However, since the system and its solution depend87 on unobservable quantity (Σ and prior on β∗), the system solution is not directly usable for practical88 purposes such as parameter tuning.89
The present work distinguishes itself from most of this literature as the goal is to describe the behavior90 of β̂ using observable quantities that only depend on the data (y,X) (and not unobservable ones such91 as Σ or a prior distribution on β∗ that appear in the aforementioned nonlinear system of equations).92 As we will see this view lets us perform adaptive tuning of parameters in a fully adaptive manner93 using the criterion (2). The criterion (2) appeared in previous works for the square loss only: [1, 12]94 studied (2) for the Lasso with Σ = Ip and [3, Section 3] for the square loss and general penalty95 (note that for the square loss ρ(u) = u2/2, (2) reduces to n2‖r‖2/(n− d̂f)2 due to ψ(u) = u and96 tr[V ] = n − d̂f. The property ψ(u) = u of the square loss hides the subtle interplay between97 r, ψ(r), d̂f and tr[V ] in (2) for ρ different than the square loss). A criterion different from (2) is98 studied in [12, 3] to estimate the out-of-sample error. That criterion has the drawback to require the99 knowledge of Σ, unlike (2) which is fully adaptive.100
This work leverages probabilistic results on functions of standard normal random variables [4][3,101 §6, §7] which are consequences of Stein’s formula [14]. Consequently, the main limitation of our102 work is that it currently requires Gaussian design for the probabilistic results (on the other hand, the103 differentiability result (5) is deterministic and does not rely on any probabilistic assumption).104
2 Differentiability of regularized M-estimators105
The first step towards the study of the criterion (2) is to justify the almost sure existence of the106 derivatives of β̂ that appear in (2) through the scalar scalar d̂f and the matrix V in (2). Although the107 criterion (2) only involves the derivatives of β̂(y,X) with respect to y for a fixedX , the proof of108
our results rely on the interplay between the derivatives with respect to y and with respect toX: this109 differentiability structure of M -estimators is the content of the following result.110
Theorem 2.1. Let Assumption 1.1 be fulfilled. For almost every (y,X) the map (y,X) 7→ β̂(y,X)111 is differentiable at (y,X) and there exists a matrix Â ∈ Rp×p with ‖Σ1/2ÂΣ1/2‖op ≤ (nµ)−1 s.t.112
(∂/∂yi)β̂(y,X) = ÂX >eiψ ′(ri),
(∂/∂xij)β̂(y,X) = Âejψ(ri)− ÂX>eiψ′(ri)β̂j , where ri = yi − x>i β̂, (5)
ei ∈ Rn, ej ∈ Rp are canonical basis vectors , ψ := ρ′ and ψ′ denote the derivatives. Furthermore,113
d̂f = tr[X(∂/∂y)β̂] = tr[XÂX diag{ψ′(r)}], (6)
V = diag{ψ′(r)}(In −X(∂/∂y)β̂) = diag{ψ′(r)} − diag{ψ′(r)}XÂX diag{ψ′(r)}. (7)
satisfy 0 ≤ d̂f ≤ n and 0 ≤ tr[V ] ≤ n.114
Since the same matrix Â appears in both the derivatives with respect to yi and to xij , (5) provides115 relationship between (∂/∂yi)β̂ and (∂/∂xij)β̂, for instance (∂/∂xij)β̂ = Âejψ(ri)− β̂j(∂/∂yi)β̂.116 Although the matrix Â is not explicit for arbitrary loss-penalty pair, closed-form expressions are117 available for particular examples such as the Elastic-Net penalty as discussed in Section 6.118 Remark 2.1. For the square loss ρ(u) = u2/2, the differentiability formulae (5) reduce to119
(∂/∂yl)β̂(y,X) = ÂX >el, (∂/∂xij)β̂(y,X) = Âej(yi − x>i β̂)− ÂX >eiβ̂j
for most every (y,X) and some matrix Â ∈ Rp×p depending on (y,X), since in this case ψ′ = 1.120
In the simple case where g is twice continuously differentiable, (5) follows [4] with121
Â = ( X> diag{ψ′(r)}X + n∇2g(β̂) )−1 (8)
by differentiating the KKT conditions X>ψ(y −Xβ̂) = n∇g(β̂). To illustrate why this is true, provided that β̂(y,X) is differentiable, if (y(t),X(t)) are smooth perturbations of (y,X) with (y(0),X(0)) = (y,X) and ddt (y(t),X(t))|t=0 = (ẏ, Ẋ), differentiation of X(t)
>ψ(y(t) − X(t)β̂(y(t),X(t))) = n∇g(β̂(y(t),X(t))) at t = 0 and the chain rule yields
Ẋ>ψ(r)−X> diag{ψ′(r)}(ẏ − Ẋβ̂(y,X)) = Â−1 ddt β̂(y(t),X(t)) ∣∣ t=0
with Â in (8). This gives (5) if the penalty g is twice-differentiable. Theorem 2.1 reveals that for122 arbitrary convex penalty functions including non-differentiable ones, the differentiability structure123 (5) always holds, as in the case of twice differentiable penalty g, even for penalty functions such as124 g(b) = µ‖b‖2/2 + λ‖mat(b)‖nuc where mat : Rp → Rd1×d2 is a linear isomorphism to the space of125 d1 × d2 matrices and ‖ · ‖nuc is the nuclear norm: in this case by Theorem 2.1 there exists a matrix126 Â ∈ Rp×p such that (5) holds although no closed-form expression for Â is known.127 The representation (5) is a powerful tool as it provides explicit derivatives of quantities of interest128 such as r = y −Xβ̂, ‖ψ(r)‖2 or ‖Σ1/2(β̂ − β∗)‖2. These explicit derivatives can then be used in129 probabilistic identities and inequalities that involve derivatives, for instance Stein’s formulae [14],130 the Gaussian Poincaré inequalty [5, Theorem 3.20], or normal approximations [8, 4].131 Remark 2.2. Similar derivative formulae hold if an intercept is included in the minimization, as in132
( β̂0(y,X), β̂(y,X) ) = argmin b0∈R,b∈Rp 1 n n∑
i=1
ρ(yi − b0 − x>i b) + g(b) (9)
Let Assumption 1.1 be fulfilled, and assume further ‖ψ′(r)‖2 > 0 with r := y− 1nβ̂0−x>i β̂ where133 1n = (1, ..., 1)
> ∈ Rn. For almost every (y,X) the map (y,X) 7→ β̂(y,X) is differentiable at134 (y,X), and there exists Â ∈ Rp×p depending on (y,X) with ‖Σ1/2ÂΣ1/2‖op ≤ (nµ)−1 such that135
136
(∂/∂yi)β̂(y,X) = ÂX >Ψ′ei, (∂/∂xij)β̂(y,X) = Âejψ(ri)− ÂX>Ψ′eiβ̂j , (10)
where ei ∈ Rn, ej ∈ Rp are canonical basis vectors, ψ = ρ′ and Ψ′ := diag{ψ′(r)} −137 ψ′(r)ψ′(r)>/ ∑ i∈[n] ψ ′(ri).138
3 Distribution of individual residuals139
We now turn to the distribution of a single residual ri = yi − x>i β̂ for some fixed observation140 i ∈ {1, ..., n} (for instance, fix i = 1). By leveraging the differentiability structure (5) and the normal141 approximation from [4], the following result provides a clear picture of the distribution of ri.142 Theorem 3.1. Let Assumption 1.1 be fulfilled and let Â ∈ Rp×p be given by Theorem 2.1. Then for143 every i = 1, ..., n there exists Zi ∼ N(0, 1) such that144 ∣∣∣ ( ri+tr[ΣÂ]ψ(ri) ) − ( εi+‖Σ1/2(β̂−β∗)‖Zi
)∣∣∣ ≤ OP (n−1/4)(|ψ(εi)|+‖Σ1/2(β̂−β∗)‖) (11) Furthermore, if εi has a fixed distribution F , there exists a bivariate variable (ε̃ni , Z̃ n i ) converging in145 distribution to the product measure F ⊗N(0, 1) such that146 ri + tr[ΣÂ]ψ(ri) = ε̃ n i + ‖Σ
1/2(β̂ − β∗)‖Z̃ni . (12) If εi has a fixed distribution F and Assumption 1.2 holds then |ψ(εi)|+ ‖Σ1/2(β̂ − β∗)‖ = OP (1).147
Theorem 3.1 is a formal statement regarding the informal normal approximation148
ζi := ri + tr[ΣÂ]ψ(ri)− εi ‖Σ1/2(β̂ − β∗)‖ ≈ N(0, 1). (13)
Simulations in Figure 2 confirm the normality of ζi for the Huber loss with Elastic-Net penalty149 and four combinations of tuning parameters. For the square loss ρ(u) = u2/2, because ψ(u) = u,150 asymptotic normality of the residuals hold in the following form.151 Theorem 3.2. Let Assumption 1.1 hold with ρ(u) = u2/2 and ε ∼ N(0, σ2In). Then for i = 1,152
(σ2 + ‖Σ1/2(β̂ − β∗)‖2)−1/2(1 + tr[ΣÂ])(yi − x>i β̂)→d N(0, 1) as n→ +∞. (14)
It is informative to provide a sketch of the proof of Theorem 3.1 explain the appearance of ψ(ri) and153 tr[ΣÂ] in the normal approximation results (11) and (13). A variant of the normal approximation154 of [4] proved in the supplement states that for a differentiable function f : Rq → Rq \ {0} and155 z ∼ N(0, Iq), there exists Z ∼ N(0, 1) such hat156
E [∣∣∣ f(z) >z − ∑q k=1(∂/∂zk)fk(z)
‖f(z)‖ − Z
∣∣∣ 2] ≤ C1E [∑q k=1 ‖(∂/∂zk)f(z)‖2 ‖f(z)‖2 ] . (15)
Some technical hurdles aside, the proof sketch is the following: Apply the previous display to q = p,157 z = Σ−1/2xi conditionally on (ε, (xl)l∈[n]\{i}) and to f(z) = Σ
1/2(β̂ − β∗) in the simple case158 where β∗ = 0 (this amounts to performing a change of variable by translation of β̂ to β̂ − β∗). Then159 the right-hand side of the previous display is negligible in probability compared to Z, and in the160 left-hand side f(z)>z = x>i (β̂ − β ∗) and ∑q k=1(∂/∂zk)fk(z) ≈ tr[ΣÂ]ψ(ri) as the second term161 in (5) is negligible. This completes the sketch of the proof of (13).162
Proximal operator representation. From the above asymptotic normality results, a stochastic representation for the i-th residual ri = yi − x>i β̂ can be obtained as follows: With prox[tρ](u) the proximal operator of x 7→ tρ(x) defined as the unique solution z ∈ R of equation z + tψ(z) = u,
ri = yi − x>i β̂ = prox[t̂ρ] ( ε̃ni + ‖Σ 1/2(β̂ − β∗)‖Z̃ni )
with t̂ = tr[ΣÂ]
where (ε̃ni , Z̃ n i ) converges in distribution to product measure F ⊗N(0, 1) where F is the law of εi.163
4 A proxy of the out-of-sample error if Σ is known164
The approximations of the previous sections for ri + tr[ΣÂ]ψ(ri) and the fact that εi is independent165 of Zi ∼ N(0, 1) in (11) suggest that (ri + tr[ΣÂ]ψ(ri))2 ≈ ε2i + ‖Σ
1/2(β̂ − β∗)‖2Z2i ; and166 averaging over {1, ..., n} one can hope for the approximation ‖r + tr[ΣÂ]ψ(r)‖2/n ≈ ‖ε‖2/n+167 ‖Σ1/2(β̂ − β∗)‖2. The following result makes this heuristic precise.168
Theorem 4.1. Let Assumption 1.1 be fulfilled and Â be given by Theorem 2.1. Then169
‖Σ1/2(β̂ − β∗)‖2 + ‖ε‖2/n = ∥∥r + tr[ΣÂ]ψ(r) ∥∥2/n+OP (n−1/2) Rem,
where Rem := ‖Σ1/2(β̂−β∗)‖2 + 1n‖ψ(r)‖ 2 + (‖Σ1/2(β̂−β∗)‖2 + 1n‖ψ(r)‖ 2)1/2‖ 1√ n ε‖. Thus
‖Σ1/2(β̂ − β∗)‖2 + ‖ε‖2/n = (1 +OP (n−1/2)) ∥∥r + tr[ΣÂ]ψ(r) ∥∥2/n.
Theorem 4.1 provides a first candidate, ∥∥r + tr[ΣÂ]ψ(r) ∥∥2/n to estimate170
‖Σ1/2(β̂ − β∗)‖2 + ‖ε‖2/n. (16)
Estimation of (16) is useful as ‖ε‖2/n is independent of the choice of the estimator β̂ and in particular171 independent of the chosen loss-penalty pair in (1). Given two or more estimators (1), choosing the172 one with smallest ∥∥r + tr[ΣÂ]ψ(r) ∥∥2 is thus a good proxy for minimizing the out-of-sample error.173
Corollary 4.2. Let β̂, β̃ be two M -estimators (1) Assumption 1.1 with loss-penalty pair (ρ, g) and174 (ρ̃, g̃) respectively. Assume that both satisfy Assumption 1.1 and let ψ = ρ′ and ψ̃ = ρ̃′. Let175 r = y −Xβ̂, r̃ = y −Xβ̃ be the residuals, Â, Ã be the corresponding matrices of size p × p176 given by Theorem 2.1. Further assume that both estimators satisfy Assumption 1.2 and that ε has iid177 coordinates independent with E[|εi|1+q] ≤M for constants q ∈ (0, 1),M > 0 independent of n, p.178 Let Ω = {‖XΣ−1/2‖op ≤ 2 √ n+ √ p} ∩ {‖ε‖2 ≤ n2/(1+q)}. Then for any η > 0 independent of179 n, p there exists C(γ, µ, η, q,M) > 0 depending only on {γ, µ, η, q,M} such that180
P ( ‖Σ1/2(β̂ − β∗)‖2 − ‖Σ1/2(β̃ − β∗)‖2 > η, ‖r + tr[ΣÂ]ψ(r)‖2 ≤ ‖r̃ + tr[ΣÃ]ψ̃(r̃)‖2 )
≤ C(γ, µ, η, q,M)n−q/(1+q) + P(Ωc)→ 0.
Provided that the noise random variables εi have at least 1 + q moments, Corollary 4.2 implies181 that with probability approaching one given two M -estimators β̂ and β̃, choosing the estimator182 corresponding to the smallest criteria among ‖r + tr[ΣÂ]r‖2 and ‖r̃ + tr[ΣÃ]r̃‖2 leads to the183 smallest out-of-sample error, up to any small constant η > 0. This allows noise random variables εi184 with infinite variance. A similar result can be obtained to select among K different M -estimators (1).185
Corollary 4.3. As in Corollary 4.2, assume E[|εi|1+q] ≤M and let β̂1, ..., β̂K be M -estimators of186 the form (1) with loss-penalty pair (ρk, gk) satisfying Assumptions 1.1 and 1.2. For each k = 1, ...,K,187 let rk = y−Xβ̂k be the residuals and Âk be the corresponding matrix of size p×p from Theorem 2.1.188 Let k̂ ∈ argmink=1,...,K ‖rk + tr[ΣÂk]ψk(rk)‖ where ψk = ρ′k. Then if (γ, µ, η, q,M) are189 constants independent of n, p190
P ( ‖Σ1/2(β̂k̂ − β ∗)‖2 > mink=1,...,K ‖Σ1/2(β̂k − β ∗)‖2 + η ) → 0 if K = o(nq/(1+q)).
Given K different loss-penalty pairs and the corresponding M -estimators in (1), minimizing the191 criterion ‖r + tr[ΣÂ]r‖ thus provably selects a loss-penalty pair that leads to an optimal out-192 of-sample error, up to an arbitrary small constant η > 0 independent of n, p. The requirement193 K = o(nq/(1+q)) means that the cardinality of the collection of M -estimators to select from should194 grow more slowly than a power of n. This is typically satisfied for default tuning parameter grids in195 popular libraries (e.g., sklearn.linear_model.Lasso [13]) with tuning parameters evenly spaced196 in a log-scale that consequently have cardinality logarithmic in the parameter range. The major197 drawback of the criterion ‖r + tr[ΣÂ]r‖ is the dependence through tr[ΣÂ] on the covariance Σ198 of the design, which is typically unknown. The next section introduces an estimator of tr[ΣÂ] that199 does not require the knowledge of Σ.200

heading: 5 Degrees of freedom and estimating tr[ΣÂ] without the knowledge of Σ201

text:
This section focuses on estimating tr[ΣÂ]. The matrix Â from Theorem 2.1 can estimated from the data (y,X) in the sense that Â is a measurable function of (y,X) (thanks to the observation that derivatives are limits, and limits of measurable functions are again measurable). The difficulty is thus to estimate tr[ΣÂ] without the knowledge of Σ. To illustrate this difficulty, consider Ridge regression with square loss ρ(u) = u2/2 and penalty g(b) = τ‖b‖2/2. Then β̂(y,X) = (X>X + τnIp) −1X>y and Â in Theorem 2.1 is given explicitly by Â = (X>X + τnIp)−1 and
tr[ΣÂ] = tr[(G>G+ nτΣ−1)−1], whereG = XΣ−1/2.
Above,G is a random matrix with iid N(0, 1) entries the value of tr[ΣÂ] is highly dependent on the202 spectrum of Σ−1. In this particular case, the limit of tr[(G>G+ nτΣ−1)−1] can be obtained using203 random matrix theory [11] as the limiting behavior of the Stieltjes transform of G>G/n + τΣ−1204 and its spectral distribution is known; however the limit of the spetral distribution depends on the205 spectrum of τΣ−1. This is not desirable here as we wish to construct estimators that require no206 knowledge on Σ. For more involved loss-penalty pairs such as the Elastic-Net in Example 6.1, such207 random matrix theory results do not apply as tr[ΣÂ] depends on the random support of β̂.208
Instead, we do not rely on known random matrix theory results. With the matrix Â ∈ Rp×p given by209 Theorem 2.1, our proposal to estimate tr[ΣÂ] is the ratio d̂f/ tr[V ] with d̂f and V in (6)-(7). Both210 the scalar d̂f and the matrix V ∈ Rn×n are observable; in particular they do not depend on Σ.211 Theorem 5.1. Let Assumption 1.1 be fulfilled and Â be given by Theorem 2.1. Then212
E[| tr[ΣÂ] tr[V ]/n− d̂f/n|] ≤ C2(γ, µ)n−1/2. (17)
Simulations in Figure 3 and Table 1 confirm that the approximation tr[ΣÂ] ≈ d̂f/ tr[V ] is accurate213 for the Huber loss with Elastic-Net penalty. For the square loss, ψ′ = 1 and tr[V ] = n− d̂f so that214 (17) becomes E|(1− d̂f/n)(1 + tr[ΣÂ])− 1| ≤ C3(γ, µ)n−1/2 and the following result holds.215 Corollary 5.2. Let Assumption 1.1 be fulfilled with ρ(u) = u2/2 and ε ∼ N(0, σ2In). Then216 (1−d̂f/n)(1+tr[ΣÂ])→P 1 and the normality (14) holds with 1+tr[ΣÂ] replaced by (1−d̂f/n)−1.217
For general loss ρ, the criterion (2) replaces tr[ΣÂ] by d̂f/ tr[V ] in the proxy of the out-of-sample218 error ‖r+ tr[ΣÂ]ψ(r)‖2 studied in the previous section. Thanks to (17), this replacement preserves219 the good properties of ‖r + tr[ΣÂ]ψ(r)‖2 proved in Corollaries 4.2 and 4.3.220 Theorem 5.3. For k = 1, ...,K, let (ρk, gk) be a loss-penalty pair satisfying Assumptions 1.1 and 1.2 with ψk = ρ′k, let β̂k, rk, Âk be the corresponding M -estimator residual vector and matrix of size p × p given by Theorem 2.1 as in Corollary 4.3 and let d̂fk = tr[XAkX> diag{ψ′k(rk)}] and V k = diag{ψ′k(rk)}(In −XAkX
> diag{ψ′k(rk)}). For a small constant η > 0 independent of n, p, say η = 0.05, define
k̂ ∈ argmin k=1,...,K
∥∥∥rk + d̂fk
tr[V k] ψk(rk)
∥∥∥ 2
subject to 1
n
n∑
i=1
ψ′k(rki) ≥ η.
0 .0
0 3
2
0 .0
0 4
7
0 .0
0 7
1
0 .0
1 1
0 .0
1 6
0 .0
2 4
0 .0
3 6
0 .0
5 4
0 .0
8 1
0 .1
2
0 .1
8
0 .2
7
0 .4
1
λ
1e-10
1e-07
1e-05
0.001
0.01
0.032
0.063
0.1
τ
n̂/n
0.0
0.2
0.4
0.6
0.8
1.0
0 .0
0 3
2
0 .0
0 4
7
0 .0
0 7
1
0 .0
1 1
0 .0
1 6
0 .0
2 4
0 .0
3 6
0 .0
5 4
0 .0
8 1
0 .1
2
0 .1
8
0 .2
7
0 .4
1
λ
1e-10
1e-07
1e-05
0.001
0.01
0.032
0.063
0.1
τ
d̂f/n
0.0
0.2
0.4
0.6
0.8
1.0
0 .0
0 3
2
0 .0
0 4
7
0 .0
0 7
1
0 .0
1 1
0 .0
1 6
0 .0
2 4
0 .0
3 6
0 .0
5 4
0 .0
8 1
0 .1
2
0 .1
8
0 .2
7
0 .4
1
λ
1e-10
1e-07
1e-05
0.001
0.01
0.032
0.063 0.1 τ
tr[V ]/n
0.0
0.2
0.4
0.6
0.8
1.0
If εi has 1 + q moments in the sense that E[|εi|1+q] ≤ M for constants q ∈ (0, 1),M > 0. If221 (M, q, η, µ, γ) and η̃ > 0 are independent of n, p then222
P ( ‖Σ1/2(β̂k̂−β
∗)‖ > min k=1,...,K: 1n ∑n i=1 ψ ′ k(rki)≥η ‖Σ1/2(β̂k−β ∗)‖+η̃
) → 0 if K = o(nq/(1+q)).
Figure 1 illustrates on simulations the success of the criterion (2) over a grid of tuning parameters223 for M -estimators with the Huber loss and Elastic-Net penalty. The criterion (2) is thus successful224 at selecting a M -estimator with smallest out-of-sample error up to an additive constant η̃, among225 those M -estimators indexed in {1, ...,K} that are such that 1n ∑n i=1 ψ ′ k(rki) ≥ η. On the one hand226
it is unclear to us whether the restriction 1n ∑n i=1 ψ ′ k(rki) ≥ η; on the other hand there is a practical227
meaning in excluding M -estimators with small 1n ∑n i=1 ψ ′ k(rki): For the Huber loss H(u) := u 2/2228
for |u| ≤ 1 and |u| − 1/2 for |u| ≥ 1 the quantity 1n ∑n i=1 ψ ′ k(rki) is the number of of data points229 in {1, ..., n} such that the residual yi − x>i β̂k fall within the quadratic regime of the loss function.230 Observations i ∈ {1, ..., n} that fall in the linear regime of the loss are excluded from the fit, in the231 sense that for some iwith rki = yi−x>i β̂k > 1, replacing yi by ỹi = yi+1000 (or any positive value)232 does not change the M -estimator solution β̂k (this can be seen from the KKT conditions directly,233 or by integration the derivative with respect to yi in (5)). Thus the constraint 1n ∑n i=1 ψ ′ k(rki) ≥ η234 requires that at most a constant fraction of the observations are excluded from the fit (or equivalently,235 at least a constant fraction of the n observations participate in the fit). For scaled versions of the236 Huber loss, ρk(u) = a2H(a−1u) for some a > 0, the value n̂ = 1n ∑n i=1 ψ ′ k(rki) again counts237 the number of residuals falling in the quadratic regime of the loss, i.e., the number of observations238 participating in the fit. The heatmaps of Figure 3 illustrate n̂ in a simulation for a wide range of239 parameters. Similarly, for smooth robust loss functions such as ρk(u) = √ 1 + u2, the constraint240
1 n ∑n i=1 ψ ′ k(rki) ≥ η requires that at most a constant fraction of the n observations are such that241
ψ′k(rki) < η/2, i.e., such that the second derivative ψ ′ k is too small (and the loss ρk too flat).242
Theorems 2.1, 3.2, 4.1 and 5.1 provide our general results applicable to a single regularized M -243 estimator (1) while corollaries such as Theorem 5.3 are obtained using the union bound. The next244
section specializes our results and notation to the Huber loss with Elastic-Net penalty and details the245 simulation setup used in the figures.246
6 Example and simulation setting: Huber loss with Elastic-Net penalty247
In simulations and in the example below, we focus on the loss-penalty pair248 ρ(u; Λ) = Λ2H(Λ−1u), g(b;λ, τ) = λ‖b‖1 + (τ/2)‖b‖22 (18) for tuning parameters Λ, λ, τ ≥ 0 where H(u) := u2/2 for |u| ≤ 1 and |u| − 1/2 for |u| ≥ 1.249 Example 6.1. With (ρ, g) in (18), matrix Â in (5) matrix V in (7) and d̂f in (6) we have250
ÂŜ,Ŝ = (X > Ŝ diag{ψ′(r)}X Ŝ + nτI p̂) −1, Ai,j = 0 if i 6∈ Ŝ or j 6∈ Ŝ, V = diag{ψ′(r)} − diag{ψ′(r)}X Ŝ(X > Ŝ diag{ψ′(r)}X Ŝ + nτI p̂) −1X> Ŝ diag{ψ′(r)}, d̂f = tr[X Ŝ(X > Ŝ diag{ψ′(r)}X Ŝ + nτI p̂) −1X> Ŝ diag{ψ′(r)}], (19)
where Ŝ is the active set {j ∈ [p] : β̂j 6= 0} and p̂ is the size of Ŝ; X Ŝ is the submatrix of X251 selecting columns with index in Ŝ and ÂŜ,Ŝ is the submatrix of Â with entries indexed in Ŝ × Ŝ.252
The identities (19) are proved in [3, §2.6]. Simulations in Figures 1 to 3 and Table 1 illustrate typical253 values for d̂f, tr[V ], tr[ΣÂ], the out-of-sample error and the criterion (2), n̂ = ∑n i=1 ψ
′(ri) and254 p̂ = |Ŝ| under anisotropic Gaussian design and heavy-tailed εi. The simulation setup is as follows.255 Data Generation Process. Simulation data are generated from a linear model y = Xβ∗ + ε with256 anisotropic Gaussian design Σ and heavy-tail noise vector ε. The design matrix X has n = 1001257 rows and p = 1000 columns. Each row of X is i.i.d. N(0,Σ), with the same Σ across all258 repetitions, generated once by Σ = R>R/(2p) withR ∈ R2p×p being a Rademacher matrix with259 i.i.d. entries P(Rij = ±1) = 12 . The true signal vector β
∗ ∈ Rp has its first 100 coordinates set to260 p1/2/100 = √ 10/10 and the rest 900 coordinates set to 0. The noise vector ε ∈ Rn has i.i.d. entries261 from the t-distribution with 2 degrees of freedom (so that Var[εi] =∞, i.e., εi is heavy-tailed).262 Estimation Process. Each dataset (y,X) is fitted by a Huber Elastic-Net estimator with263 loss-penalty pair in (18). We focus on 2d heatmaps with respect to the two penalty parame-264 ters (λ, τ) of the penalty; to this end the Huber loss parameter Λ is set to Λ = 0.054n1/2265 and a grid for (λ, τ) in then set so that d̂f/n varies on the grid from 0 to 1 (cf. the mid-266 dle heatmap in Figure 3). The Elastic-Net penalty g(b;λ, τ) = λ‖b‖1 + (τ/2)‖b‖22 is used267 with (λ, τ) ∈ {(0.036, 10−10), (0.054, 0.01), (0.036, 0.01), (0.024, 0.1)} in Figure 2 and Table 1,268 (λ, τ) ∈ [0.0032, 0.41]×{10−10} in Figure 3, and (λ, τ) ∈ [0.0032, 0.041]×[10−10, 0.1] in Figure 1.269 More simulation results are provided in the supplementary materials.270
References271 [1] Mohsen Bayati, Murat A Erdogdu, and Andrea Montanari. Estimating lasso risk and noise level.272 In Advances in Neural Information Processing Systems, pages 944–952, 2013.273
[2] Mohsen Bayati and Andrea Montanari. The lasso risk for gaussian matrices. IEEE Transactions274 on Information Theory, 58(4):1997–2017, 2012.275
[3] Pierre C Bellec. Out-of-sample error estimate for robust m-estimators with convex penalty.276 arXiv:2008.11840, 2020.277
[4] Pierre C Bellec and Cun-Hui Zhang. Second order poincare inequalities and de-biasing arbitrary278 convex regularizers when p/n→ γ. arXiv:1912.11943, 2019.279
[5] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A280 nonasymptotic theory of independence. Oxford University Press, 2013.281
[6] Michael Celentano and Andrea Montanari. Fundamental barriers to high-dimensional regression282 with convex penalties. arXiv preprint arXiv:1903.10603, 2019.283
[7] Michael Celentano, Andrea Montanari, and Yuting Wei. The lasso with general gaussian designs284 with applications to hypothesis testing. arXiv preprint arXiv:2007.13716, 2020.285
[8] Sourav Chatterjee. Fluctuations of eigenvalues and second order poincaré inequalities. Proba-286 bility Theory and Related Fields, 143(1):1–40, 2009.287
[9] David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic288 variance via approximate message passing. Probability Theory and Related Fields, 166(3-289 4):935–969, 2016.290
[10] Noureddine El Karoui, Derek Bean, Peter J Bickel, Chinghway Lim, and Bin Yu. On robust291 regression with high-dimensional predictors. Proceedings of the National Academy of Sciences,292 110(36):14557–14562, 2013.293
[11] Vladimir A Marčenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets294 of random matrices. Mathematics of the USSR-Sbornik, 1(4):457, 1967.295
[12] Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse296 balls and adaptive parameter tuning. arXiv preprint arXiv:1811.01212, 2018.297
[13] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion,298 Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-299 learn: Machine learning in python. the Journal of machine Learning research, 12:2825–2830,300 2011.301
[14] Charles M Stein. Estimation of the mean of a multivariate normal distribution. The annals of302 Statistics, pages 1135–1151, 1981.303
[15] Mihailo Stojnic. A framework to characterize performance of lasso algorithms. arXiv preprint304 arXiv:1303.7291, 2013.305
[16] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized306 m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592–5628,307 2018.308
Checklist309
1. For all authors...310 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s311 contributions and scope? [Yes]312 (b) Did you describe the limitations of your work? [Yes] See Assumptions 1.1 and 1.2 and313 the limitations mentioned in Section 1.2314 (c) Did you discuss any potential negative societal impacts of your work? [N/A]315 (d) Have you read the ethics review guidelines and ensured that your paper conforms to316 them? [Yes]317 2. If you are including theoretical results...318
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump-319 tions 1.1 and 1.2.320
(b) Did you include complete proofs of all theoretical results? [Yes] See supplementary321 material.322
3. If you ran experiments...323 (a) Did you include the code, data, and instructions needed to reproduce the main exper-324 imental results (either in the supplemental material or as a URL)? [Yes] See code in325 supplementary material.326
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they327 were chosen)? [Yes] The code is also provided.328
(c) Did you report error bars (e.g., with respect to the random seed after running experi-329 ments multiple times)? [Yes]330
(d) Did you include the total amount of compute and the type of resources used (e.g., type331 of GPUs, internal cluster, or cloud provider)? [Yes] It takes an Amazon EC2 server332 approximately 40 hours to generate all our simulation results. This is also mentioned333 in supplementary.334
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...335 (a) If your work uses existing assets, did you cite the creators? [N/A] Simulations are336 implemented using Python.337 (b) Did you mention the license of the assets? [N/A]338 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]339
340
(d) Did you discuss whether and how consent was obtained from people whose data you’re341 using/curating? [N/A]342
(e) Did you discuss whether the data you are using/curating contains personally identifiable343 information or offensive content? [N/A] Simulated data only.344
5. If you used crowdsourcing or conducted research with human subjects...345 (a) Did you include the full text of instructions given to participants and screenshots, if346 applicable? [N/A]347 (b) Did you describe any potential participant risks, with links to Institutional Review348 Board (IRB) approvals, if applicable? [N/A]349 (c) Did you include the estimated hourly wage paid to participants and the total amount350 spent on participant compensation? [N/A]351

title: Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning


summaries: This paper proposes a generalization of the attention coverage penalty in seq2seq models (Wu et al 2016), where instead of encouraging a uniform coverage of the source, this work first predicts the expected coverage of each source word. During beam search, beam hypotheses that violate the expected attention coverage constraints receive a penalty. Experiments on 9 summarization benchmarks show that the proposed coverage loss outperforms using existing attention coverage losses during beam search.

summaries: This paper thinks that cross attention distribution in transformer’s encoder-decoder framework can help the performance of beam search. At the same time, this paper also proposes an algorithm to predict distribution to help beam search. This paper conduct experiments on 9 datasets to prove its effectiveness.

summaries: This work proposes to add a global attention feature component to the beam search scoring procedure for conditional generation, which typically just considers the fitness of successor tokens conditioned on the predicted history of tokens in the beam. This augmentation basically keeps track of cumulative local autoregressive attention on the source tokens during beam search and penalizes major deviation from the predicted desired "global" attention over the source tokens. Specifically, this approach proposes a finetuning step of neural language generators, which is responsible for predicting cumulative global attention on each token and the training is done via regression. During training, the "reference" global attention is computed by using the full reference in the decoder transformer instead of just the left prefix of the reference to compute attention.  A relatively simple scheme is proposed to measure deviation of cumulative local attention from the global attention in a decomposable iterative manner. This scheme also involves a form of length reward that encourages the generation to match the length predicted by the global attention.  Experiments are performed on the task fo summarization with pretrained summarization system on 9 datasets. The results show that the proposed beam search augmentation outperforms standard beam search in general. Most strikingly, the ablation experiment with the "Oracle" global attention (instead of prediction, if we had access to the actual global attention and hence the actual reference length) significantly outperforms beam search and the proposed approach demonstrating the potential of global attention.

summaries: This paper tackles the problem of suboptimality of beam search as it is not able to have a global perspective of the probability of the generated beams due to truncated beam size (less than vocabulary size) for space and time complexity purposes. This paper proposes a global-aware beam search which is calibrated using the global attention distribution to guide the local decisions at every time step during beam search. The global attention distribution prediction is formulated as a regression task, which is then fed into a global scoring function to guide the beam search-based generation. This approach solves the mismatch between the local optimality of beam search with the global optimal generation. This modified search strategy has been shown to boost the summarization of two SOTA models BART and PEGASUS.

summaries: This paper presents a method to improve beam search by learning and predicting the global attention. A global scoring function is developed to regulate beam search to generate summaries. In Phase I, the global attention distribution is predicted in order to be included as a protocol to calibrate beam search. In Phase II, a step-wise global scoring function is used to guide beam search based on the predicted global attention distribution.  Experiments on 9 datasets show that the global-aware inference improves state-of-the-art summarization models.

abstractText: This study develops a calibrated beam-based algorithm with awareness of the global attention distribution for neural abstractive summarization, aiming to improve the local optimality problem of the original beam search in a rigorous way. Specifically, a novel global protocol is proposed based on the attention distribution to stipulate how a global optimal hypothesis should attend to the source. A global scoring mechanism is then developed to regulate beam search to generate summaries in a near-global optimal fashion. This novel design enjoys a distinctive property, i.e., the global attention distribution could be predicted before inference, enabling step-wise improvements on the beam search through the global scoring mechanism. Extensive experiments on nine datasets show that the global (attention)-aware inference significantly improves state-of-the-art summarization models even using empirical hyper-parameters. The algorithm is also proven robust as it remains to generate meaningful texts with corrupted attention distributions. The codes and a comprehensive set of examples are available.2

authors:
Shuyang Cao
Lu Wang

title: Attention head masking for inference time content selection in abstractive summarization

venue: In Proceedings of the 2021 Conference of the North American 10 Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Arman Cohan
Franck Dernoncourt
Doo Soon Kim
Trung Bui
Seokhwan Kim
Walter Chang
Nazli Goharian

title: A discourse-aware attention model for abstractive summarization of long documents. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)

authors:
Eldan Cohen
Christopher Beck

title: Empirical analysis of beam search performance degradation in neural sequence models

venue: In International Conference on Machine Learning,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

authors:
Li Dong
Nan Yang
Wenhui Wang
Furu Wei
Xiaodong Liu
Yu Wang
Jianfeng Gao
Ming Zhou
Hsiao-Wuen Hon

title: Unified language model pre-training for natural language understanding and generation

venue: Advances in Neural Information Processing Systems,

authors:
Alexander Fabbri
Irene Li
Tianwei She
Suyi Li
Dragomir Radev

title: Multi-news: A largescale multi-document summarization dataset and abstractive hierarchical model

venue: In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,

authors:
Sebastian Gehrmann
Yuntian Deng
Alexander Rush

title: Bottom-up abstractive summarization

venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,

title: Sequence transduction with recurrent neural networks

venue: arXiv preprint arXiv:1211.3711,

authors:
Max Grusky
Mor Naaman
Yoav Artzi

title: Newsroom: A dataset of 1.3 million summaries with diverse extractive strategies. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)

authors:
Karl Moritz Hermann
Tomas Kocisky
Edward Grefenstette
Lasse Espeholt
Will Kay
Mustafa Suleyman
Phil Blunsom

title: Teaching machines to read and comprehend

venue: Advances in neural information processing systems,

authors:
Ari Holtzman
Jan Buys
Li Du
Maxwell Forbes
Yejin Choi

title: The curious case of neural text degeneration

venue: In International Conference on Learning Representations,

authors:
Zhiheng Huang
Wei Xu
Kai Yu

title: Bidirectional lstm-crf models for sequence tagging

venue: arXiv preprint arXiv:1508.01991,

authors:
Nitish Shirish Keskar
Bryan McCann
Lav R Varshney
Caiming Xiong
Richard Socher

title: Ctrl: A conditional transformer language model for controllable generation

authors:
Rik Koncel-Kedziorski
Dhanush Bekal
Yi Luan
Mirella Lapata
Hannaneh Hajishirzi

title: Text generation from knowledge graphs with graph transformers

authors:
Anastassia Kornilova
Vladimir Eidelman

title: BillSum: A corpus for automatic summarization of US legislation

venue: In Proceedings of the 2nd Workshop on New Frontiers in Summarization,

authors:
Mahnaz Koupaee
William Yang Wang

title: Wikihow: A large scale text summarization dataset

venue: arXiv preprint arXiv:1810.09305,

authors:
Mike Lewis
Yinhan Liu
Naman Goyal
Marjan Ghazvininejad
Abdelrahman Mohamed
Omer Levy
Veselin Stoyanov
Luke Zettlemoyer

title: BART: Denoising sequence-to-sequence pretraining for natural language generation, translation, and comprehension

venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,

authors:
Jiwei Li
Will Monroe
Dan Jurafsky

title: Learning to decode for future success

venue: arXiv preprint arXiv:1701.06549,

authors:
Mingzhe Li
Xiuying Chen
Shen Gao
Zhangming Chan
Dongyan Zhao
Rui Yan

title: Vmsmo: Learning to generate multimodal summary for video-based news articles

venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP),

authors:
Wei Li
Xinyan Xiao
Yajuan Lyu
Yuanzhuo Wang

title: Improving neural abstractive document summarization with structural regularization

authors:
Yanyang Li
Tong Xiao
Yinqiao Li
Qiang Wang
Changming Xu
Jingbo Zhu

title: A simple and effective approach to coverage-aware neural machine translation

venue: In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics

title: ROUGE: A package for automatic evaluation of summaries

venue: In Text Summarization Branches Out,

authors:
Yinhan Liu
Jiatao Gu
Naman Goyal
Xian Li
Sergey Edunov
Marjan Ghazvininejad
Mike Lewis
Luke Zettlemoyer

title: Multilingual denoising pre-training for neural machine translation

authors:
Clara Meister
Ryan Cotterell
Tim Vieira

title: If beam search is the answer, what was the question

authors:
Myle Ott
Michael Auli
David Grangier
Marc’Aurelio Ranzato

title: Analyzing uncertainty in neural machine translation

authors:
Ratish Puduppully
Li Dong
Mirella Lapata

title: Data-to-text generation with content selection and planning

venue: In Proceedings of the AAAI conference on artificial intelligence,

authors:
Alec Radford
Jeffrey Wu
Rewon Child
David Luan
Dario Amodei
Ilya Sutskever

title: Language models are unsupervised multitask learners

venue: OpenAI Blog,

authors:
Marc’Aurelio Ranzato
Sumit Chopra
Michael Auli
Wojciech Zaremba

title: Sequence level training with recurrent neural networks

venue: arXiv preprint arXiv:1511.06732,

authors:
Abigail See
Peter J Liu
Christopher D Manning

title: Get to the point: Summarization with pointer-generator networks

venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks

venue: In Advances in neural information processing systems,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Ashwin K Vijayakumar
Michael Cogswell
Ramprasaath R Selvaraju
Qing Sun
Stefan Lee
David Crandall
Dhruv Batra

title: Diverse beam search for improved description of complex scenes

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Oriol Vinyals
Alexander Toshev
Samy Bengio
Dumitru Erhan

title: Show and tell: A neural image caption generator

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Michael Völske
Martin Potthast
Shahbaz Syed
Benno Stein

title: TL;DR: Mining Reddit to learn automatic summarization

venue: In Proceedings of the Workshop on New Frontiers in Summarization,

authors:
Sam Wiseman
Alexander M. Rush

title: Sequence-to-sequence learning as beam-search optimization

venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,

authors:
Thomas Wolf
Lysandre Debut
Victor Sanh
Julien Chaumond
Clement Delangue
Anthony Moi
Pierric Cistac
Tim Rault
Rémi Louf
Morgan Funtowicz
Joe Davison
Sam Shleifer
Patrick von Platen
Clara Ma
Yacine Jernite
Julien Plu
Canwen Xu
Teven Le Scao
Sylvain Gugger
Mariama Drame
Quentin Lhoest
Alexander M. Rush

title: Transformers: State-of-theart natural language processing

venue: In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations,

authors:
Yonghui Wu
Mike Schuster
Zhifeng Chen
Quoc V Le
Mohammad Norouzi
Wolfgang Macherey
Maxim Krikun
Yuan Cao
Qin Gao
Klaus Macherey

title: Google’s neural machine translation system: Bridging the gap between human and machine translation

venue: arXiv preprint arXiv:1609.08144,

authors:
Yilin Yang
Liang Huang
Mingbo Ma

title: Breaking the beam search curse: A study of (re-)scoring methods and stopping criteria for neural machine translation

authors:
Jingqing Zhang
Yao Zhao
Mohammad Saleh
Peter Liu

title: Pegasus: Pre-training with extracted gap-sentences for abstractive summarization

authors:
Wen Zhang
Yang Feng
Fandong Meng
Di You
Qun Liu

title: Bridging the gap between training and inference for neural machine translation

authors:
Juntang Zhuang
Tommy Tang
Yifan Ding
Sekhar C Tatikonda
Nicha Dvornek
Xenophon Papademetris
James Duncan

title: Adabelief optimizer: Adapting stepsizes by the belief in observed gradients

heading: 1 Introduction

text:
As the barriers exist from the auto-regressive design of neural probabilistic text generators to predicting the global optimum directly [30], the heuristic algorithm beam search that factorizes global optimization to multiple local optimizations, has been popularly used for text decoding [24]. In the original beam search setting, the global optimum is a hypothesis g of the highest probability among all possible sentences, and consists of words in vocabulary V . Given the global optimum at step t denoted as g≤t, the local optimums l≤t refer to K candidate sequences with the highest probabilities at each step. While it is necessary to compromise on the beam size K V to ensure text quality [3, 25, 24] and search efficiency, beam search suffers from a major limitation due to its local property. Concretely, assuming that the global optimal hypothesis is within the K local optimal hypotheses of the highest probabilities, i.e. p(g≤t) ≥ p(l≤t), for all t until the termination T , it operates solely with the local information available at each step. In practice, such assumption may however fail in the case that the probability of the global optimum at step τ < T is less than those of the local optimums, i.e. p(g≤τ ) < p(l≤τ ), but is adjusted to a higher level in the later steps, p(g>τ |g≤τ ) > p(l>τ |l≤τ ) and p(g≤τ )p(g>τ |g≤τ ) > p(l≤τ )p(l>τ |l≤τ ). This often leads beam search to get stuck in the local optimum from step τ onward in generating texts.
∗corresponding author 2https://github.com/yema2018/global_aware
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
To cope with this limitation, this study proposes a calibrated beam-based algorithm with global awareness at all searching steps. Generally, our novel algorithm is implemented in two phases. Before the beam search (Phase I), the global attention distribution is predicted in order to be included as a protocol to calibrate beam search at each step, encouraging the generated hypotheses to attend to the source in a more near-global optimal way. Specifically, the global attention distribution describes how all reference tokens should assign the attention to each source token (illustrated in Figure 1.a), which could be predicted from the source by training an attention-prediction model. The training is fairly straightforward and resembles a sequence tagging task [12], except that the predicted attention distribution from the source is a regression result. There are several advantages of using the attention distribution as the global protocol. 1) Attention distributions are sensitive to the decoder input, suggesting that any input to the decoder leads to a unique attention distribution with fixed model parameters; 2) attention distributions are accessible for almost all text generation tasks thanks to the recent advances in attention models [27, 4, 31]; 3) relying on the source only, the global attention distribution can be predicted before beam search, thus offering a rigorous mechanism to calibrate a global-aware beam search.
During beam search (Phase II), we develop a novel global scoring mechanism composed of attention scores and length rewards to guide beam search based on the predicted global attention distribution. As one main theoretical result, we show that the attention score can be considered as the probability that generated texts attend to sources in line with the predicted global attention distribution. Specifically, the generated tokens in each step update the local attention distribution to source tokens dynamically, where the attention values grow monotonically as the generation proceeds (see Figure 1.b). Since the desired situation is that the local distribution reaches exactly the global distribution at the terminal step, we regulate the inference by discouraging local attention from exceeding their corresponding predicted global attention at all steps.
With regards to the core target to investigate the possible paradigm that improves beam search with global awareness during decoding, contributions of this study are summarized as follows:
• We argue that the limitation of beam search roots from its defect in finding the global optimal hypothesis. We improve the algorithm by proposing a global protocol to regulate beam search step-by-step. This paper is the first to predict and deploy the global attention distribution to calibrate the inference in a rigorous way, thus returning a hypothesis that attends to source tokens in a more near-global optimal manner. In contrast, previous works [37, 7, 20, 29, 21] try to use attention distributions to improve beam search, but ignore that the global attention distribution is predictable.
• A novel global scoring mechanism is designed to evaluate the generated sequences at each step based on the desired situation described in Figure 1.c. As theoretically justified, its major component can be elegantly integrated into beam search in the form of a probability so that merely O(K) of the time complexity is increased in each step (see Section § 3.1 for more details).
• The proposed algorithm with global awareness manifests a robust and plug-and-play property in enhancing beam search for neural abstractive summarization. Without requiring any model or parameter modification, the global-aware inference shows excellent performance in generating meaningful texts, even if the attention distribution is corrupted or not of its own. Further, it is identified that summaries generated by global-aware inference are both higher-quality and different from beam search hypotheses (see Global-aware in Table 1). More interestingly, we find that the generation style of a dataset could be transferred by the designated global attention distribution. For instance, summaries of higher abstractness for CNN/DM could be generated by only replacing its global attention distribution with a highly abstractive distribution during inference, as presented in Global-aware† of Table 1.
• On the empirical side, we show that the proposed global-aware inference can stably and significantly boost two state-of-the-art summarization models BART [17] and PEGASUS [39] to produce higher quality summaries on nine datasets, even if only the empirical hyper-parameters are used.

heading: 2 Preliminary

text: The proposed decoding strategy is applied in BART [17] and PEGASUS [39] to perform summarization. BART is a pre-trained seq-to-seq model whose structure essentially follows a vanilla Transformer encoder-decoder [31]. PEGASUS has a similar structure but is pre-trained on a larger dataset differently. Notably, the fine-tuned parameters of both models are downloaded from HuggingFace Models3 and are fixed in all subsequent operations, where “fine-tuned" means the pre-trained model has been fine-tuned on a specific dataset.

heading: 2.1 Beam Search

text:
Since the decoder of the seq-to-seq model is an auto-regressive model, the probability of a target sequence y = (y0, · · · , yt, · · · , yT ) can be factorized to the probabilities conditional on the source x = (x1, · · · , xi, · · · , xn) and y<t = (y0, · · · , yt−1), i.e.,
p(y|x) = T∏ t=1 p(yt|x,y<t), T ≥ 1 (1)
When T = 0, y = (y0) and p(y0|x) = 1 because y0 is a fixed start token. Beam search [8] is a decoding strategy to predict a target sequence by maximizing this factorization. Given a vocabulary set V , at each inference step t, beam search selects a candidate beam set BKt = {bkt }Kk=1 (where each beam bkt = (b k 0 , · · · , bkt ) is a candidate sequence) from an all-possible beam set Bt of size K × |V|, namely, Bt = { bkt−1 ◦ v | bkt−1 ∈ BKt−1, v ∈ V } (2)
3https://huggingface.co/models
BKt = { bkt | bkt = argtopk (log p(bt|x)) , bt ∈ Bt } , t ≥ 1 (3)
where argtopk(·) outputs K beams with the highest conditional probability, and ◦ is the concatenation operation. Besides, BK0 = {bk0}Kk=1 where bk0 is the start token. By Eq. 1, log p(bt|x) is an accumulated value. Its calculation can be simplified as:
log p(bt|x) = { log p(bkt−1|x) + log p(v|x, bkt−1), t ≥ 2 log p(v|x, bk0), t = 1
(4)
where the value of log p(bkt−1|x) is computed from the previous step. Therefore, at each step, we only need calculate the condition probability of each token in the vocabulary set.
A beam is terminated after it generates an ending token, and the beam set of K terminated beams is defined as Y . The final hypothesis y∗ is chosen from Y based on the beam probability normalized by lengtha where a is a hyper-parameter of length [37]:
y∗ = argmax yk∈Y log p(yk | x) (|yk| − 1)a
(5)
where yk = (yk0 , · · · , ykT ). |yk| − 1 is used since the start token is not considered in calculating the length.

heading: 2.2 Attention Distribution

text:
Attention distribution is a continuous vector whose element indicates the degree of attention paid to a source token. The element is formed by the accumulation of cross attention, i.e., ∑ t αt,i, where αt,i refers to the cross attention that the tth token in the target sequence gives to the ith source token.4 Specially, cross attention is a scaled dot-product [31] of hidden states of the source x and the target sequence y. Notably, since Transformer-decoder is an auto-regressive model, the cross attention assigned by tth target token is actually calculated by y<t = (y0, · · · , yt−1). Global Attention Distribution. The global attention distribution g = [g1, · · · , gi, · · · , gn] ∈ Rn is the attention distribution given by the reference, where global attention gi refers to the total attention that the reference attends to the ith source token, and n is the source length.
Optimal Length. The summation of g, namely ∑n i=1 gi, is equal to ∑n i=1 ∑T t=1 αt,i = T due to∑n
i=1 αt,i = 1 in softmax operation, where T is the reference length, or equivalently the optimal length Z.
Local Attention Distribution. The local attention distribution lkt = [lkt,1, · · · , lkt,i, · · · , lkt,n] ∈ Rn is the attention distribution of the kth generated sequence and updated at each decoding step t. Thereinto, the local attention lkt,i denotes the total attention paid to the ith source token by the kth beam sequence (bk1 , · · · , bkt ) and is dependent on the sequence generated before t, i.e., bkt−1 = (bk0 , · · · , bkt−1).

heading: 3 Proposed Global-aware Inference

heading: 3.1 Global Scoring Mechanism

text:
The global scoring mechanism consists of an attention scoring function and a length reward function. Given the global attention distribution g, the attention scoring function A(·) at the step t depends on bkt−1,
A(bkt−1) = ∑n i=1 min(l k t,i, gi)
ζkt , ζkt = n∑ i=1 lkt,i, t ≥ 1 (6)
where ζkt indicates the total attention that the generated sequence (b k 1 , · · · , bkt ) gives to the source, and ζkt = |bkt−1| = t because the assignable attention for each generated token is 1. Notably, Eq. 6 attains the maximum score provided that each lt,i ≤ gi. As mentioned in Section § 1, the reason for
4Mean pooling is used for multi-layers and multi-heads
this design is that we desire the local attention lT,i at the termination is exactly gi, since the final hypothesis is expected to attend to source tokens in the global-optimal manner. Meanwhile, we have lT,i > lt,i for t < T because lt,i monotonically increases on t with αlm,i > 0. Therefore, at any step, the local attention lt,i should not surpass gi. Otherwise, the attention score will decline, and the penalty depends on the total amount by which these lt,i exceed gi (see Theorem 1). Further, the attention score could be considered as the proportion of correctly assigned attention to the total attention given by the generated sequence, where correct assignment indicates that all parts of lt,i do not exceed gi. Also, it could be interpreted as the correct allocation probability of local attention against the global attention distribution (see Corollary 1.1). In this case, the total attention score can be expressed as the same multiplicative form as Eq. 1 to be elegantly integrated into beam search. Theorem 1. Let M = { s : lkt,s > gs } and ∆kt = { δ | ∀s ∈M, δ = lkt,s − gs } . Given ∆ =∑
δ∈∆kt δ where ∆ ≥ 0, then A(bkt−1) decreases as ∆ increases.
Corollary 1.1. The bound of A(bkt−1) is between 0 and 1.
Proof. See App. A.
In addition to the constraint for lt,i, we still desire lT,i = gi for each token. An ideal hypothesis should have two characteristics simultaneously. Namely, its attention score at the termination is the maximum 1, and its length equals the optimal length. Therefore, we introduce a length reward function to cooperate with the attention score to penalize the situation lT,i 6= gi, which will be discussed at the end of this subsection.
As mentioned before, the total attention score at the decoding step t is defined as:
A(bkt−1) = t∏ m=1 A(bkm−1) (7)
Thus, the joint scoring function J(·) is modified from Eq. 4: J(bt,x) = log p(b k t−1|x) + β logA(bkt−1) + log p(v|x, bkt−1)
= t−1∑ m=1 ( log p(bm|x, (bkt−1)<m) + β logA(bkm−1) ) + log p(v|x, bkt−1) + β logA(bkt−1)
= J(bkt−1,x) + log p(v|x, bkt−1) + β logA(bkt−1), t ≥ 2 (8)
and J(b1,x) = log p(v|x, bk0) + β logA(bk0), where β is a hyper-parameter to trade-off between the probability and attention score. Similar to log p(bt|x) in Eq. 4, J(bt,x) is also an accumulative score. Consequently, at each step t, we only need compute p(v|x, bkt−1) and A(bkt−1). Compared with Eq. 4, the time complexity of each step is only increased by O(K) as there are K attention scores. Replacing log p(bt|x) in Eq. 3 by J(bt,x), we can select the top K beams of each decoding step according to not only the probability distribution conditional on local information bkt−1 but also the score conditional on global information g.
Considering the length reward function, the final hypothesis is thus defined as:
y∗ = argmax yk∈Y
( J(yk,x)
|yk| − 1 + βγR(ζkT , Z)
) (9)
where R(·) is the length reward function dependent on the optimal length Z and the candidate hypothesis length ζkT . Exactly, ζ k T is the total attention that a candidate hypothesis (y k 1 , · · · , ykT ) pays to the source and equals |yk| − 1. Besides, the attention score and length reward are weighted by a hyper-parameter γ, and the role of β is to ensure that the two are at the same level relative to the probability. We remove a in Eq. 5 as it only adjusts the length preference without really controlling the length.
The design of R(·) could be straightforward – one only need ensure that it increases as ζkT approaches Z, and reaches the maximum only at ζkT = Z. In this paper, we design a step-wise length reward functionR(ζkt , Z) to better balance the relationship between the attention score and the length reward and make the whole searching process as succinct as beam search. We put the design details of the step-wise length reward in App. B, and we regard Eq. 9 as the general scoring formulation of global-aware inference.

heading: 3.2 Predict the Global Attention Distribution

text:
Since the reference is unknown practically, the global attention distribution could only be predicted from the source. We construct an attention-prediction model to learn the relationship between the source tokens and the global attention distribution.
The input of the attention-prediction model is the fixed encoder output E ∈ Rn×d of BART or PEGASUS plus learnable positional encodings P ∈ Rn×d, where d is the dimension of hidden states. The input is fed to a learnable Transformer-encoder to obtain Ẽ ∈ Rn×d that is encoded with additional context information, followed by a linear transformation with an exponential function:
ĝ = exp ( ẼWg + bg ) (10)
where ĝ ∈ Rn refers to the prediction of g, Wg ∈ Rd×1 and bg ∈ Rn are the learnable weights and biases. The exponential function is imposed to ensure ĝ > 0. We choose the exponential function for this operation because it is shown stable in the training and testing stage. Given the objective of minimizing the distance between ĝ and g, the loss is defined as their Euclidean distance:
L = ‖ĝ − g‖2 (11)
The predicted optimal length Ẑ is the sum of elements in ĝ. Note that the length reward function is not affected no matter whether Ẑ is an integer or not.

heading: 4 Experiment

heading: 4.1 Setup

text:
Datasets. We evaluate the performance on totally 9 summarization datasets, where 2 datasets (CNN/DM [10], XSUM [5]) with BART [17] and 8 datasets (XSUM [5], BillSum [15], Multi-News [6], NewsRoom [9], WikiHow [16], Reddit TIFU [34], arXiv and PubMed [2]) with PEGASUS [39]. Thereinto, XSUM [5] is a highly abstractive dataset whose summaries are all expressed in a short sentence.
Implementation Details. We adopt a randomly initialized 2-layer transformer-encoder in the attention-prediction model wherethe structure of each layer is the same as the BART-encoder layer. The optimizer is the Adabelief-optimizer [41] with eps 1e − 16, betas (0.9, 0.999), weight decay 1e − 4 and learning rate 2e − 5. The attention-prediction model is trained on the training set for about 50, 000 steps, and checkpoints are saved per 10, 000 steps to select the best checkpoints on the development set. Since the attention prediction is slightly different from common sequence tagging tasks, we have summarized two notable points after several attempts – the dropout rate should be 0, and a small learning rate is preferred. All experiments are conducted on 3 RTX 6000. We include the global-aware inference in the generation code of HuggingFace transformers [36]. At the time of evaluation, ROUGE-1, ROUGE-2 & ROUGE-L (R-1, R-2 & R-L) scores [22] are computed from the ROUGE code5 used by BART [17].
Hyper-parameter Selection. Although the global-aware inference requires two new hyperparameters γ and β, some original hyper-parameters of beam search, namely length penalty, minimum and maximum length, are omitted. The searching scopes of β and γ are in {2, 4, 6, 10, 12, 15, 18, 20} and {0, 0.5, 1, 1.5, 2}, respectively. According to the numerical tests on the development set, we finally choose β = 12, γ = 1.5 for CNN/DM and β = 4, γ = 0 for XSUM. As limited improvement could be observed from larger γ’s, we recommend γ = 1 for normal or longer targets. When testing the global-aware inference with PEGASUS [39], we directly use empirical hyper-parameters for each dataset, namely β = 4, γ = 0 for XSUM and β = 12, γ = 1 for other 7 datasets. The beam size K follows the setups in BART [17] and PEGASUS [39].

heading: 4.2 Results

text:
Comparison with Beam Search. Beam search is a hard-to-beat baseline which has stood the test of time and proven its superiority in practice for long [24]. In Table 2, we compare our global-aware
5https://github.com/pltrdy/files2rouge
inference to beam search with length regularizations (i.e., α in Eq. 5, accompanied with two hard constraints, namely minimum length and maximum length). We strictly follow the hyper-parameter setups of PEGASUS [39] in terms of beam search, while we only adopt empirical hyper-parameters for our method. Even so, significant improvements can be observed on all the data sets, especially when the summary is of normal or longer length.
Table 3: Comparison with other methods.
CNN/DM K = 4 R-1 R-2 R-L
Beam search [17] 44.12 21.21 40.89 + Our coverage 44.74 21.69 41.48 + Repetition penalty [13] 44.11 21.14 40.87 + Attention masking [1] 45.54 22.24 42.44
Global-aware 45.13 21.77 42.04
XSUM K = 6 R-1 R-2 R-L
Beam search [17] 45.38 22.32 37.15 + Our coverage 44.54 21.82 36.97 + Repetition penalty [13] 45.40 22.31 37.13 + Attention masking [1] 45.35 22.31 37.15
Global-aware 45.57 22.60 37.61
Table 4: ORACLE and ablation results.
CNN/DM R-1 R-2 R-L
ORACLE global-aware 51.85 28.13 48.68 -w/o length reward 50.46 27.53 47.43
Global-aware 45.13 21.77 42.04 -w/o length reward 44.39 21.58 41.41 -w/o attention score 44.12 21.29 40.91
XSUM R-1 R-2 R-L
ORACLE global-aware 49.50 26.24 41.13 -w/o length reward 48.92 26.48 41.45
Global-aware (γ = 1) 45.44 22.15 37.11 -w/o length reward 45.57 22.60 37.61 -w/o attention score 45.23 21.88 36.73
Comparison with Other Attention Approaches. In this part, we focus on comparing other approaches which also exploit certain attention distributions to improve beam search. The first is the coverage penalty [37, 21]. To enhance its performance in summarization, we replace its preset attention distribution with our predicted global attention distribution. Note that the coverage function can only evaluate the generated sentences at the terminal step. Instead of comparing the global-aware inference to the methods [29, 20, 7] that aim to reduce repetition using the dynamic attention distribution, we compare our algorithm with the CTRL repetition penalty [13] which has similar motivation but is more systematical and independent of training. Table 3 lists the comparison results against different algorithms. It can be observed that our global-aware approach can improve the performance of beam search stably and fundamentally. We also observe that the attention head masking [1] appears to outperform the global-aware approach on CNN/DM, but it fails to gain any improvement on XSUM. To further show the advantage of the proposed approach, we will take a closer examination on the attention head masking [1] and our proposed approach in the next part.
Further Comparison with Attention Head Masking. First, one should bear in mind that the attention head masking [1] acts on the model instead of beam search, which is opposite to us. Specifically, it selects contents during decoding by disabling partial attention heads for unimportant
Table 7: Generate summaries with corrupted attention distributions.
R-1 R-2 R-L
Beam search 27.00 12.21 23.88 Global-aware (10K) 28.78 12.82 25.51 Global-aware (100K) 29.59 13.72 26.30
Figure 2: Sensitive analysis in the test set.
2 4 6 10 12 15 18 20 40.5
41
41.5
42
R -L
f1 s
co re
s
CNN/DM, =1
global-aware beam search
0 0.5 1 1.5 2 40.5
41
41.5
42
R -L
f1 s
co re
s
CNN/DM, =12
2 4 6 10 12 15 18 20 37
37.2
37.4
37.6
R -L
f1 s
co re
s
XSUM, =0
0 0.5 1 1.5 2 37
37.2
37.4
37.6
R -L
f1 s
co re
s
XSUM, =4
tokens to decrease the attention to these tokens. According to the reported results presented in Table 3, we can see that although attention masking achieves amazing results on CNN/DM, it does fail completely on XSUM. Since hiding unimportant tokens from some heads results in the loss of context information of salient tokens, this would lead to its instability. Thus, it could be ineffective for tasks that require contextual information of the whole source such as XSUM. Taking a further comparison, we deploy the attention head combinations selected for CNN/DM and XSUM to examine its effect on PEGASUS [39]. These comparison results are shown in Table 5. Evidently, our method enjoys a robust feature that is able to boost summary inference on various datasets and models even with the same set of hyper-parameters. In contrast, attention masking [1] behaves much sensitive to the changes of models and datasets. Besides, attention masking has to construct its training saliency labels based on the longest common subsequences between a reference summary and the source. This may be hardly achieved in some text generation tasks (e.g. translation) where no common subsequence exists at all. Such drawback presents one main limitation for attention masking.
ORACLE Results and Ablation Study. ORACLE refers to the global-aware inference combined with (true) global attention distribution instead of predicted global attention distribution. The related results have been presented in Table 4, and the significant boosting certifies that the proposed method could improve beam search with the global attention distribution. On the other hand, we conduct ablation experiments on ORACLE and global-aware. Both results indicate that length reward plays an important role in generating normal-length text but causes adverse effect on generating text of very short length. Besides, the performance declines significantly when only length reward is applied, due to the fact that sole length reward cannot calibrate beam search step-wise.
Robustness. We intend to examine the robustness of our proposed global-aware algorithm in this and next part. To do so, we substitute the parameters in CNN/DM’s attention prediction model to XSUM’s to create more abstractive summaries for CNN/DM. For comparison, we set the minimum length of beam search as 0 to allow it to generate shorter summaries. Table 6 shows the F1 score, recall and precision of the shorter beam search and global-aware†. It is surprising that even by using the attention distribution from a different dataset with distinct properties, the proposed global-aware mechanism still manages to generate meaningful summaries with competitive F1 scores, proving the robustness of this algorithm. Moreover, the higher Precision and lower Recall of the global-aware suggest that although information is partially lost, the algorithm still summarizes core information in a concise format, compared to the standard beam search. On the other hand, we exploit a BART model fine-tuned on CNN/DM to generate summaries of NewsRoom directly, and the ROUGE scores of beam search are shown in Table 7. Next, we randomly select 10K and 100K samples from the training set and use them to fine-tune the attention-prediction model, where the global-aware improves beam search substantially. The experiment once again validates the robustness of the proposed inference algorithm, as it maintains a reasonably good performance even from learning a corrupted attention distribution from a BART without fine-tuning.
Sensitive Analysis. We further examine the performance robustness with respect to the hyperparameters. From Figure 2, we could see the global-aware inference is always better than beam search in CNN/DM, no matter how its hyper-parameters change. Besides, the performance is less sensitive to the hyper-parameters when β ≥ 10 or γ ≥ 1. While in XSUM, the global-aware could improve beam search stably with γ = 0, but there is a significant decline when applying length
reward. In fact, the attention score favors shorter hypotheses, and the length reward could alleviate the bias. However, if the references of a dataset are already very short such as XSUM, the length reward may lead to a counterproductive effect. Since the setup of CNN/DM is applicable to most datasets, we argue that the global-aware inference is robust to both hyper-parameters in most cases.

heading: 5 Analysis on Global Attention Distribution

heading: 5.1 Distribution Law

text: The distribution law of global attention in BART [17] is shown in Figure 3. It is observed that most attention is assigned to the start token and full stops which are not semantically salient, and most of the remaining attention is unevenly allocated to (semantically) overlapped tokens between the source and the reference (i.e., important words). It is worth mentioning that the importance here is no longer a simple binary classification like in [7, 1], but a continuous numerical value decided by the model knowledge learned from data. In general, one should not simply equate the global attention with the word importance, but should be clear that it essentially reflects knowledge learned by the attention model such as the syntactic and semantic structure of sentences. Meanwhile, the distribution law indicates that attention distributions in pre-trained models may not be relevant with the uniform distribution at all. That is to say, it is not reasonable to still use an uniform attention threshold (like the threshold 1 preset in [37, 7]) to regulate the decoding of pre-trained models. Last but not least, our general motivation is to alleviate locality bias by aligning the attention distribution of reference and hypothesis, which does not really care how the global attention is distributed only if it is predictable. However, the proposed penalty mechanism is indeed insensitive to some distributions, and we will provide more thinking about this in App. G by applying the global-aware inference to translation.

heading: 5.2 Why It can be Predicted from Source?

text:
Since the ORACLE experiments indicated that the global attention is helpful for decoding, the concern remains if it is predictable using only source. In App. E.1 we will show the predictability empirically, while here we just provide an interesting explanation. In our opinion, the global attention distribution is an interpretable representation of reference which not only has the characteristics of hidden representation but also can be explained by the source tokens. First of all, given the source, the global attention is calculated by the input reference and trained neural network parameters;
this is similar to achieving hidden representation. Moreover, like hidden representation, the global attention distribution could also capture the semantic similarity, e.g., replacing a reference word with a semantically similar word leads to slighter attention changes than that with a random word (see Figure 4.a). Besides, it is observed from Figure 4.b and Figure 4.c that global attention is able to represent the sentence order and factual knowledge. On the other hand, the global attention distribution enjoys a distinct characteristic that each of its features can be explained as the degree of attention paid to a source token, which means changes of such representation are regular to some extent. For example, in Figure 4.c, we distort a numerical number in the reference to violate the fact stated in the source, and then find that the attention assigned to the actual number originally is most transferred to the special tokens and punctuation. Overall, similar sources should have similar global attention distributions, since similar sources often have similar references and global attention distribution is a representation of reference. Moreover, the global attention and source tokens are in an one-to-one correspondence. Thereby, we argue that it is convenient to use the source to predict the global attention distribution.

heading: 6 Related Work

text:
In the field of text generation, efforts have been made to boost beam search with regards to the attention distribution. For instance, some studies engage the attention distribution to penalize the situation where sources fail to be fully covered in translation tasks [37, 21], while others [7, 29, 20] incorporate dynamic attention distributions to evade tokens that have been highly regarded to reduce repetition. However, none of the aforementioned studies attempts to apply the global attention distribution to acquire the knowledge that the level of attention should be allocated to each token from the reference. Further, the existing score functions used by those studies are rather different from the proposed global scoring mechanism. More details can be seen in App. D.
In addition to the attention distribution, other techniques are developed to improve beam search in terms of length bias [38], diversity-less [32], vapidity [11] and degradation [25, 3]. These methods are not included for comparison because they are not suitable for summarization [38, 11], or do not aim to enhance beam search as the main purpose [32, 25, 3]. Besides, we argue that these patches to beam search are supposed to be hard for improving the performance stably and fundamentally (as shown in Table 3 given by our global-aware method) because they fail to specify what a final hypothesis should look like and are easy to trap into local optimums.

heading: 7 Conclusion

text:
Beam search tends to fall into local optimums due to the lack of global information during inference. To calibrate beam search on the premise of global awareness, this study proposes a predictable protocol to stipulate how a global optimal hypothesis should attend to source tokens. By training a simple prediction model of the global attention distribution, a novel global scoring mechanism is then developed to regulate the inference on a step-wise basis. Our experiment shows that the proposed global-aware beam search generates higher-quality summaries, relative to beam search and other counterparts of the similar nature. Besides, the proposed algorithm is proven robust in generating meaningful texts even with corrupted attention distributions, implying its potential to cooperate with user-defined global attention distributions. We plan to focus our future study on generalizing the global-aware inference to a broader range of text generation tasks, including not only text2text but also image caption [33], multimodal summarization [19], graph2text [14] and data2text [26].
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: XJTLU Key Programme Special Fund KSF-A-14 and KSFP-02, National Natural Science Foundation of China under No. 61876155 and Jiangsu Science and Technology Programme under No. BE2020006-4.

title: Global-aware Beam Search for Neural Abstractive Summarization