Optimal Activation Functions for the Random Features Regression Model
Authors: Jianxin Wang
José Bento
Venue: ICLR 2023 poster (2023)
Keywords: Random Features Regression Model
Learning theory for neural networks
Functional analysis and variational calculus

Abstract: The asymptotic mean squared test error and sensitivity of the Random Features Regression model (RFR) have been recently studied. We build on this work and identify in closed-form the family of Activation Functions (AFs) that minimize a combination of the test error and sensitivity of the RFR under different notions of functional parsimony. We find scenarios under which the optimal AFs are linear, saturated linear functions, or expressible in terms of Hermite polynomials. Finally, we show how using optimal AFs impacts well established properties of the RFR model, such as its double descent curve, and the dependency of its optimal regularization parameter on the observation noise level.

Published as a conference paper at ICLR 2023
OPTIMAL ACTIVATION FUNCTIONS FOR THE RANDOM FEATURES REGRESSION MODEL
Jianxin Wang"
José Bento
Department of Electrical and Computer Engineering
Department of Computer Science
Rice University
Boston College
5wl 620 r edu
bent.ayrrbcc.em edu
ABSTRACT
The asymptotic mean squared test error and sensitivity of the Random Features Regression model (RFR) have been recently studied. We build on this work and identify closed-form the family of Activation Functions (AFs) that minimize combination of the test eπror and sensitivity of the RFR under different notions functional parsimony. We find scenarios under which the optimal AFs are linear, saturated linear functions, Finally, we show how using optimal AFs impacts well established properties of the RFR model, such as its double descent curve, and the dependency of its optimal regularization parameter on the observation noise level.
expressible in terms of Hermite polynomials.
INTRODUCTION
For many neural network (NN) architectures, the test error does not monotonically increase as a model's complexity increases but can go down with the training error both at low and high complexity levels. This phenomenon, the double descent curve, defies intuition and has motivated new frameworks to explain Explanations have been advanced involving linear regression with random covariates (Belkin et al. 22000; Hastie et al. 2022), kernel regression (Belkin et al.) 2019b Liang & Rakhlin 2020), the neural tangent kernel model (Jacot et al. 2018), and the Random Features Regression (RFR) model (Mei & Montanari] 2022). These frameworks allow queries beyond
the generalization power of NNs. For example, they have been used to study networks' robustness properties (Hassani & Javanmard 2022 Tripuraneni et al. 2021).
One aspect within reach and unstudied to this day is finding optimal Activation Functions (AFs) for these models. It is known that AFs affect network's approximation accuracy and efforts to optimize AFs have been undertaken. Previous work has justified the choice of AF's empirically, e.g.. Ramachandran et al. (2017), provided numerical procedures learn AF parameters, sometimes jointly with models" parameters, e.g. Unser 2011).. See Rasamoelina et al. (2020) for commonly used AFs and Appendix C for how AFs have been previously derived.
We derive for the first time closed-form optimal AFs such that an explicit objective function involving the asymptotic test error and sensitivity of a model is minimized. Setting aside empirical and principled but numerical methods, all past principled and analytical approaches to design AFs focus on non accuracy related considerations, e.g. Milletari et al. (2019). We focus on AFs for the RFR model and expand its understanding. We preview few surprising conclusions extracted from our main results: 1. The optimal AF can be linear, in which case the RFR model is linear model. For example, if no regularization is used for training, and for low complexity models, a linear AF is often preferred want minimize test error. For high complexity models non-linear AF is often better;
2. A linear optimal AF can destroy the double descent curve behaviour and achieve small test error with much fewer samples than e.g. a ReLUU;
When, apart from the test error, the sensitivity of model becomes important, optimal AF's that without sensitivity considerations were linear can become non-lineat and vice-versa:
4. Using an optimal AF with an arbitrary regularization during training can lead to the same, or better, test error as using a non-optimal AF, e.g. ReLU, and optimal regularization.
* Work done during undergrad at Boston College.

---

Published as a conference paper at ICLR 2023
1.1 PROBLEM SET UP
We consider the effect of AFs on finding an approximation f to square-integrable function fa on the d-dimensional sphere gd-I(Vd), the function fa having been randomly generated. The approximation is to be learnt from training data D yr),1 where æ; sv-l(Vd), the variables {æ;) )/_1 are Li.d, uniformly sampled from sd-I(Vd), and y; = fa(æ,) + E₁, where the noise variables {E) are i.dd. with B(e,) = 0, B(c)) =²; and B(c,)= co.
The approximation f is defined according to the RFR model. The RFR model can be viewed as two-layer NN with random first-layer weights encoded by a matrix θ E R with ith row 0 e R satisfying ||0:1== Vd, with {0:} i.idd uniform on (Vd), and with to-be-learnt second-layer weights encoded by a vector a = [ui]] = =R Unless specified otherwise, the norm |I-Il denotes the Euclidean norm. The RFR model defines fa,e: (v-) - R such that
fa,o(z) = Σ (0, x)/Va)
i=1
where o--) is the AF that is the target of our study and (x, y) denotes the inner product between vectors x and When clear from the context, we write fa.e as f. omitting the model's parameters. The optimal weights at * are learnt using ridge regression with regularization parameter A z 0, namely,
n yイ
NA d
a= = =a (d, arg min
Σ j=1
(B:0
||a||
(2)
aCRN
We will tackle this question: What the simplest that leads to the best approximation of fa?
We quantify the simplicity of an AF a with its norm in different functional spaces. Namely, either ||r|||2 (Z(()
||r||| = (Z))),
or
(3)
(4)
where o' is the derivative of o and the expectations are with respected a normal random variable Z with zero mean and unit variance, i.e. Z ~ N(O. 1). For a comment on these choices please read Appendix A We quantify the quality with which f = far approximates fa via L, linear combination of the mean squared error and the sensitivity of f to perturbations in its input. For
[0, 1J. uniform on gd-I(Vd), define
L - (1 - (r) aS, (5) where & = B((f(x)- fa(x))
(6)
and S = |[Vvf(=)1
(7)
See Appendix B for comment our choice for sensitivity.
Like in Mei & Montanari (2022): D' A'mmuur al. 2020), we operate the asymptotic proportional regime where n, d, N oo, and have constant ratios between them, namely, N/d - 1/1 and n/d - 1/2 In this asymptotic setting, it does not matter in defining (6) and 77. in addition to taking the expectation with respect to the test data independently of D, we also take expectations over D and the random features in RFR. This is because when n, d, N - oo with the ratios defined
above, & and S will concentrate around their means (Mei & Montanari 2022 D'Amour et al. 2020).
Mathematically, denoting by ||ا||| either or J. our goal is to study the solutions of the problem
& min|lo*1|| subject to o* E arg min L(rr).
(8)
Notice that the outer optimization only affects the selection of optimal AF in so far as the inner optimization does not uniquely define o*, which, as we will later see, it does not.
To the best of our knowledge, no prior theoretical work exists on how optimal AFs affect performance guarantees. We review literature review on non- non-theoretical works on the design of AFs, and work studying the RFR model for purposes other than the design of AFs in Appendix C
BACKGROUND ON THE ASYMPTOTIC PROPERTIES OF THE RFR MODEL
Here will review recently derived closed-form expressions for the asymptotic mean squared error and sensitivity of the RFR model, which are the starting point of our work. First, however, we explain
the use-inspired reasons for our setup. Our assumptions are the same as, or very similar to, those of
published theoretical papers, e.g. Jacot et al. (2018): Yang et al. (202T): Ghorbani et al. (202 Mcl Pennington (0022).
2

---

Published as a conference paper at ICLR 2023
1. Data a sphere: Normalization of input data is a best practice when learning with NNs (Huang
et al. 2020). Assuming that input data lives on a sphere is one type of normalization.
Random features: The seminal work Rahimi & Recht (007a) showed the success of using
random features real datasets. For recent review on their use see see Cao et al. (2018).
3. Asymptotic setting: Mei & Montanari (2022) empirically showed that the convergence to the asymptotic regime is relatively fast, even with just few hundreds of dimensions. Most real world applications involve larger dimensions d, lots of data and lots of neurons N.
4. Shallow architecture: For a finite imput dimension d. the RFR model can learn arbitrary functions as the number of features N grows large (Bach) 2017 Rahimi & Recht 2007b Ghorbani et al. 202T). Existing proof techniques make it very hard yet to extend our type of analysis to more than two layers or complex architectures. A few papers consider models with depth 2 but do not tackle our problem and have other heavy restrictions
the model, e.g. |Pennington al. (2018) 8)). 5. Regularization: Using regularization during training to control the weights' magnitude is com- mon. can help convergence speed and generalization error (Goodfellow al.) 2016). For review on different types of regularization for learning with NNs see Kukačka et al. (2017
We make the following assumptions, which we assume hold in the theorems in this section. Assumption 1. We assume that the AF is weakly differentiable with weak derivative o', it satisfies (or villlv E R. for some constants O < Co. C1 < oo, and that it also satisfies
Ho = (Z))))),
((Zo(ZZ),,
= B(((())) 14 =2 16 pî. {= (9)
for some μ4: Ml, H2 E R. where the expectations are with respect to Z. N(O,1)
Assumption 2. We assume that N Ndd) and n n(d) such that the following limits exist in (0, oo): lim N(d) = 1/ and lim n(d)/d 1/2-
Assumption 3. We assume that yi fa(a;) + where {Edlisn -iid, Fe are independent of (milism
with B(61) = 0, B(e r2, B(eT) < 00, expectations with respect to (Ei) Furthermore,
fa(œ) = Ba,0 + (Ba, x) + +fa (x),
(10)
where Pa.o E R. 3d,1 E Rdd are deterministic with lima B2,0 = Fg. lima 1l==1 non-linear far is a centered Gaussian process indexed by x E sd-1 sd-I(V with covariance
0. The
B (oi) (2z)) = Ea((xr,
(11)
where Ea(:) satisfies B 1e-Uningdd1( (Ea(x//Vd) = O, B - (Ea(x) 0, where X1 is the 1st component of x. We define the Signal to Noise Ratio (SNR) p by
p= F= +3), r²), where F lim Ea(I).
(12)
Informally, ua quantifies how non-linear the AF is (cf. Lemia 3.1). di quantifies the complexity of the RFR model relative of the dimension d, 4/2 quantifies the amount data used for training relative to d, x2 is the variance of the observation noise, F1 is the magnitude of the linear component of our target function fa, which is controlled by Ba,1, F+ is the magnitude of the non-linear component fa in the target function, and p is the ratio between the magnitude of the linear component and the magnitude of all of the sources of randomness in the noisy function fa + e. Recall that all of our results will be derived in the asymptotic regime when d 00.
Our contributions are divided into two parts, Section 3.1 and Section 3.2 The theorems' statements in Section 3.2 quickly get prohibitively complex as they are stated more generally, with lots of special cases having to be discussed. Hence, in Section 3.2 we display our analysis on the following three different important regimes: R₁: Ridgeless limit regime, when - 0"; R2: Highly overparameterized limit, when 1/1 - oo; R3: Large sample limit, when 1/2 + co. Section 3. results are general and not restricted to these regimes. In the context of the RFR model, these regimes were introduced and discussed in Mei & Montanari (2022). For what follows we define ī 2/12² Any "lima-co X y should be interpreted as X converging to Y in probability with respect to the training data D, the random features O and the random target fa as d + co.
2.1 ASYMPTOTIC MEAN SQUARED TEST ERROR OF THE RFR MODEL
The following theorems are a specialization of a more general theorem, Theorem 12 Mei & Montanari (022). which we include in the Appendix G for completeness.
3

---

Published as a conference paper at ICLR 2023
Theorem 1 (Theorem 3 Mei & Montanari (002)). ). The asymptotic test error for regime R₁ equals Exi = lim lim & Fi Beal , v1, 222 + (r² + P.) Vnsa(S.W.../ + F2. 1-00 d=
(13)
where BnolL.VV..42
6 to. (. 1/, 222
62.ee160.0 and the functions
t. &1sten and h2nss are polynomials that are functions of 2², 11,41 and x. where x is a function of // m,nn 3/22 and 5². See Appendix Di details.
Remark 1. As function of w &R, has a discontinuity 11 = 422 called the interpolation threshold. For 1/2 high enough, and for 4/1 < 1//2. &R; decreases, reaches a minimum and then explodes approaching 2 However, past 1/2. &R, decreases again with 1 This double descent behavior has been observed/studied in many settings, including Mei & Montanari (2022) and references therein. Theorem 2 (Theorem 4 Mei & Montanari (2022)). The asymptotic test error (6) for regime R₂ equals lim lim 8= Fi Bmia (5. 2) (72 P3) 2/2 F2, (1-2 d-oo
OR=² where Buise and Vanse are defined in Appendix E
(14)
Theorem 3 (Theorem 5|Mei & Montanari (2022)). The asymptotic test error (6) for regime R3 equals
R
=
lim lim & = Fi B 1. 2/1))
(15)
$1-000 d'-co
where B Baamp (5. is defined Appendix
2.2 ASYMPTOTIC SENSITIVITY OF THE RFR MODEL
We derive a sensitivity formula for regimes Rj, R2, R3. Our theorems are a specialization (proofs in Appendix M of the more general Theorem 13 that we include in the Appendix G for completeness. Theorem 4. The sensitivity
7 for regime R1 equals
F.e. 11 1222
(F2 + 15. 11.8022
SRI= lim lim 5
(16)
d'400
6x6² 1) 11.42)
Do, (S. th 2/2)
where Do, (5, 1122))) Z S. 2/2), and 22 (, oi v22) are polynomials found in App. F7
Theorem 5. Let u2 equal (32). defined in Appendix A The sensitivity 7 for regime R2 equals
w22 + + w2) F] - 1/2 12(-1+++2))
SR. lim lim S
(17)
11 d
(-1 + 2 202222 + w22 (-1 v22))
Theorem 6. Let wn equal (35). defined in Appendix F The sensitivity (7) for regime R3 equals
Sk
lim lim S F1(1 (2/(-1 + ())) (1/ 20nth1 + 0n 2-1 + 100 d00
(18)
2.3 GAUSSIAN EQUIVALENT MODELS
string of recent work shows that the asymptotic statistics of different models, e.g. their test MSE, is equivalent that of a Gaussian model. This equivalence is known for the setup in (Mei & Montanari 2022), and also for other setups Hu & Lu (200);; Ba et al. (2022); Loureiro et al. (2021); Montanari & Saeed (2022). Setups differ the loss they consider, the type of regularization, the random feature matrices used, the training procedure, the asymptotic regime studied, or on the model architecture.
In the Gaussian model equivalent to our setup, the AF constants μoo /Ii and μ22 appear as parameters. For example, 1** appears as the magnitude of noise added to the regressor matrix entries, and the non-linear part of the target in the RFR model appears additive mismatch noise. As such, e.g., tuning μ* is related to an implicit ridge regularization. However, since in the Gaussian equivalent model μ** also appears an effective model mismatch noise, tuning AF's leads to a richer behaviour than just tuning A. Furthermore, tuning the AF requires tuning more than just one parameter, while tuning regularization only one, making our contribution in Sec. 3322 all the more valuable. In fact, one of our contributions (cf. contribution 4 in Sec. I is quantifying the limitation of this connection: tuning AFs can lead to strictly better performance than tuning regularization (cf. Section 3.3
Gaussian equivalent models derive good portion of their importance from their connection to the original models to which their equivalence is proved, and which are typically closer to real-world use of neural networks. By themselves, these Gaussian models are extremely simplistic and lack basic real-world components, such as the concept of AF that we study here. Hypothesizing an equivalence to Gaussian models greatly facilitates analytical advances and numerous unproven conjectures have been put forth regarding how generally these equivalences can be established Goldt et al. (2022); Loureiro al. (202T): Dhifallah & Lu (022).
4

---

Published as a conference paper at ICLR 2023
2.4 ADVANTAGES AND LIMITATIONS OF STUDYING THE RFR MODEL
It is known (Mei & Montanari 2022) that in the asymptotic proportional regime, the RFR cannot learn the non- component of certain families of non-linear functions, and in fact cannot do better than linear regression on the input for these functions. [Ba et al. (222) show that a single not-small gradient step to improve the initially random weights of RFR 's first layer allows surpassing linear regression's 's performance in the asymptotic proportional regime. However, for not-small steps, no explicit asymptotic MSE or sensitivity formulas are given that one could use to tune AFs parameters. Also, [a ct al. (2022). and others, e.g. Hu & Lu (222)) work with slightly different class of functions than Mei & Montanari (2022), e.g. their AFs are odd functions, making comparisons not apples- It known that the RFR can learn non-linear functions in other regimes, e.g. n poly(d), and asymptotic formulas for the RFR in this setting also exist Misiakiewicz (2022).
There is numerical evidence of the real-word usefulness of the RFR (Rahimi & Recht 20076).
Linear regression also exhibits a double descent curve in the asymptotic proportional regime (Hastie) al. 2019). However, under e.g. overparameterizztion this curve exhibits minimizer at a finite 1/2. while empirical evidence for real networks shows that the error decreases monotonically as 1/2 - co. Therefore, linear regression is not as good as the RFR to explain observed double-descent phenomena. Furthermore, linear regression does not deal with AFs, which is our object of study. Finally, even in setting where the RFR cannot learn certain non-lineat functions with zero MSE, remains an important question to study how much tuning AF can help improve the MSE and how this affects properties like the double descent curve.
3 MAIN RESULTS
We will find the simplest AFs that lead to the best trade-off between approximation accuracy and sensitivity for the RFR model. Mathematically, we will solve (8). From the theorems in Section 2 we know that & and S, and hence = (1 - a)E + as,, only depend on the AF via po, M11 442. Therelore, we will proceed in two steps. In Section 3..1 we will fix μ4. Ml. u2, and find o with associated values Mo. f1, 22 that has minimal norm, either 4 or (3) In Section 3.2, we will find values of μoo M1. H2 that minimize I. = (1 ar + oxS. Together, these specify optimal AFs for the RFR model.
It is the case that properties of the RFR model other than the test error and sensitivity also only depend on the AF via μoo 41 /22 One example is the robustness of the RFR model to disparities between the training and test data distribution (Tripuraneni et al. (021). Although we do not focus on these other properties, the results in Section (3.I) can be used to generate optimal AFs for them as well, as long as, similar to in Section 3.2
we can obtain No. M1 M2 that optimize these other properties.
We made the decision to, as often as possible, simplify expressions by manipulating them to expose == (T F.). Fi > 0, rather than using the variables F1, r, and F.. The
the signal to noise ratio p = only downside is that conclusions in the regime r = F, = O require a bit more of effort to be extracted, often been readable in the limit p
The complete proofs of our main results can be found in Appendix M and their main ideas below. The proofs of Section (.ooom3..... a.2 algebraically heavy and we provide a Mathematica file to symbolically check expressions of theorem statements and proofs in the supplementary material.
3.1 OPTIMAL ACTIVATION FUNCTIONS GIVEN FIXED μo. M1, AND μ2
Since one of our goals is knowing when an optimal AF is linear we start with the following lemma. Lemma 3.1. The AF o is linear (almost surely) if and only if 2 + μ μu n/ 0.
We now state results for the norms (4) and (3). The problem we will solve under both norms is similar.
Let Z ~ N/O, 1). We consider solving the following functional problem, where i = 1 or 2,
min||orll; subject to B(o(Z)) nvo B(Zo = nn, B(or())) = #2, with Z - N(0, 1).
(19)
If 2, we seek solutions over the weighted Lebesgue space of twice weak-differentiable functions that have ((((((Z))) and ((((o(())) defined and finite. if 1, we seek solutions over the moussian-weightte Lebesgue space of brek-differentialle functions that have B((rr()))² and B(Jor (Z)) defined and finite. The derivative o' is be understood in weak sense.
Since or is a dieeenniiiooal function, the requirement of existence of weak derivative implics that there exists function that is absolute continuous and that agrees with o almost everywhere (Rudin) cet al. 1976). Therefore, any specific solution we propose should be understood as an equivalent class of functions that agree with up set of measure zero with respect to the Gaussian measure.
5

---

Published as a conference paper at ICLR 2023
Theorem 7. The minimizers of f 2, i.e. ||=||²= (Z))" are
o(x) ax² + bx c, where = b μl, and :40 In Theorem 7 if μ4+ = there is only one minimizer, linear function. If μ. > O, there are exactly two minimizers, both quadratic functions. Note that both minimizers satisfy the growth constraints of Assumption |I and hence can be used within the analysis of the RFR model. We note that quadratic AFs have been empirically studied in the past, e.g. Wuraola & Patel (2018).
(20)
Theorem 8. One minimizer of 119 for = 1, i.e. ||] B((o'())), is
(xx) po h mmi s)) where b erfis/55) erf the Gauss error function, and E R is the unique solution to the equation 2² x//u² = g(5) if M* # O, and s +oo if μ = O, where g is specified in Appendix
(21)
When ||
we can characterize the complete solution family to (9). These are AFs of the form (xx)= = a b max mi)( where a, b, s, and f are chosen such that the constraints in (19) hold. is possible to explicitly write a and as function of μo, Ml, s, 7, and express 5,7 as the solution of E)s, = n//p2. where E has explicit form. In this case, for each μo, MI, H22 there are an infinite number of optimal AFs since E(s, = 22,/22, has infinite number of solutions. ReLU's are included in this family as f + co. The involved lengthy expressions do not bring any new insights, so we state and prove only Thr. [] which is a specialization of the general theorem s =-
Proofs' main ideas: We give the main ideas behind the proof of Theorem The proof of Theorem [8 follows similar techniques. The first-order optimality conditions imply that ~xxo'(x) (xx) + 2xr"(xx + A1 A22 1300(x)= O, where the Lagrange multipliers d1, A2, and da must be later chosen such that (Z)r = no. B(Zo(()) = μj. and B(o²(Z)) = =12-- Using the change of variable o(x) T(x/V2) - A1/43 - x12//133 - 1) we obtain -xxē'(x)+ +*x)) (3ō(x)= O which is the Hermite ODE, which well studied in physics, e-g. it appears in the study of the quantum harmonic oscillator. The cases A3 E 3) require special treatment. Using a finite energy/norm condition
we can prove that A3 is quantized. In particular d3 = 4k, k = 1, J..,. which implies that o(x) =
-d1/A3 - 12x/(d3 2) + (x2 V2), where H, is the ith Hermite polynomial and c a constant. The energy/norm is minimal when k 1, which implies quadratic AF.
3.2 OPTIMAL ACTIVATION FUNCTION PARAMETERS
We will find AF parameters that minimize linear combination of sensitivity and test error. We are interested in an asymptotic analytical treatment in the three regimes mentioned in Section To be specific, we will compute
UR 42, T, F1, Fx. = arg min (1 - (1- a Ri where == 1, or 3.
(22)
po.
We are not aware of previous work explicitly studying the trade-off between & and S for the RFR model. For the RFR model, the work of Mei & Montanari (2022) studies only the test error and D'Amour et al. (2020) studies a definition of sensitivity related but different from ours. Other papers have studied trade-offs between robustness and error measures related but different than ours and for other models, e.g. Tsipras et al. (2018): Zhang et al. (2019).
To simplify our exposition, we do not present results for the edge case a = 1, for which problem 22 reduces to minimizing the sensitivity. Below we focus on the case when [0, 1).
Special notation: In Theorem 9 we use the following special notation. Given two potential choices for AF parameters, say and y, we define y to mean that cxists and that y might exist or not, and that L = y if exists and it leads to a smaller value of (1 - at) + a than using x, and otherwise Note that y and y L make different statements about the existence of x and y. This notation is important to interpret the results of Table in Theorem 9
xUy=x.
Theorem 9. Let a E [0, 1), v = min( 3/2) and v = max 1/2). We have that
UR, (100.M1 M1, #2) x-p((-1xx +x1++++++ w) = 2 + x)} where x is as Table
(23)
In Table 7 X2, and x3 are the smallest, second smallest and third smallest roots of a 4th degree polynomial p(x), specified in Appendix ] in the range (x), a (-V, min(O, 1 //), these exists. The variables B, B2, Br. a ac, ag. the polynomial p(x), and the conditions E, and E, are defined in Appendix J.2 when th U2. and when 1/ > 2/2 these are defined in Appendix J.3
6

---

Published as a conference paper at ICLR 2023
B
B2 < < < B1
B3 v S B2
& B3
(a < (1) A E1
XR
XR LI
XR
XR
(a < (1) A E2 A (a > ac)
X1
X1 L333
x1
(ar <..)) E2 A (a (c))
x1 L33
x1
(a > OL..
(a > #c)
XL
XL
XL
(a (L)A
<ac)
XR
XR
XR
(a > A
XL
XL L
XL L X2
XL
Table 1: The optimal AFs (23) depends on x according to this table. Cells with "--" never happen. The values of 43. x3. B1, 11.B2.p., æt, -L.XR. and the events E and Eg specified below.
Remark Excluding the a scenario, follows directly from (3 that the optimal AF is linear if and only if x Xg. With this information and Table | we have all the information needed to find exactly when the optimal AF is, is not, linear. For regime Rj, changing a alone can change the optimal AF from linear to non-linear and vice-versa (see e.g. 3rd column of Table I which justifies the observation 3 Section
Remark 3. For the cases considered in Table ! is unique. When E (aRR az ac), or when (d/) > 42) A (#11 E (A, B)), (A&B are defined in Appendix [.3), we can lose the uniqueness of x. Yet, still explicitly characterize the sets of optimal and of optimal AFs parameters. For simplicity we omit these cases from Thr. [
Remark 4. Theorem 9 proof gives relationships among Table constants that imply that (1) no two rows/columns simultaneously hold and (2) in some cases some cells might not hold. See App.
We do not consider 1/1 = 2/2 in Theorem 9 because implies (1 e)ER, + +aSk, that 4/2 has been called the interpolation threshold in the context of studying the generalization properties of the RFR model under vanishing regularization (Mei & Montanari (2022). See Remark [
defined. Note
When XR)
compute the optimal value of the objective explicitly. For example, if 1/2 and
1 2/2 and Xz the optimal value of the objective (1-0)000FF++F
If d/
42-41
XR the optimal value of the objective is aFf (oMW F2 11422 a)+ath 1athaalh--33 -01" if w/ 1 and Fla(20 -00-----X00-)-)-0000
01-0/2
2 - (1000=--1110000-----0--00))))))) - if 11/ This follows by substitution.
01-122
Theorem 10. Let a E [0. 1). We have that,
UR= = (H U2) ff(-11 + 20 - x) =x) -2 1422((1 + +x)]
(24)
where x is the unique solution to p(x) = 0 in the range x (-1, min 1. - + 2d/2)), where p(x) Po PIx p2x² + p2x² p4x* with coefficients described in Appendix
Remark 5. The only way to get μ 0, and hence linear optimal AF is if simultancously satisfies m + 11-11+242-00 2
2 (1 + x) and p(x) = O. Since the first equation does not depend on a, but the zeros of p(x) = 0 change continuously with only very special choices of parameters lead to linear AFs. general regime R₂ does not have optimal linear AFs.
Theorem 11.
Let a E [0. 1). We have that
(H10- M1, (22 f, = A μ1 = 000)
=v 111=110=- a +
(Ho. M1, (2) μa A , -4a² 24302+
UR-
=
(25)
16a 80+1
(HO, #n, (42) : μ4 0 (- x)(=
0) i #1
where x is the unique solution to p(x) = in the range x x (-1, and with 1/2 replaced by v/.
2(/2),, where p(x) is
define like in Theorem 70 but with p
Remark 6. The optimal AF is always linear and independent of the noise variables F, and T. 1
Remark 7. When / = 1, a S 4 there is no optimal AF inside our AF search space since no AF can satisfy μN co. Rather, there exists a sequence of valid AFs with decreasing whose μl co.
Remark 8. We can compute the optimal objective in closed-form in some scenarios. When 0 the optimal objective is F.. When 1 1 A < a S 1. the optimal objective approaches az + - F? μI co. When v A $. the optimal objective is (f 1 -3x) F2(1 a).
Proofs' main ideas: We give the main ideas behind the proof of Theorem 10
The proof of Theorems
9 and 1T follows similar techniques but require more care. The objective I. only depends AF
7

---

Published as a conference paper at ICLR 2023
parameters via W2 (2((1/2 Mi p2). We use the Möbius transformation = (1 =1+))) 1) such that the infinite range w2 E [-00, 0] gets mapped to the finite range x E [-1. 1]. We then focus the rest of the proof on minimizing L = L(x) over the range of x. First we show that given that 1f 2 O. 1/1 > 0, the range of x can be reduced to x E [xI - -in (1, -
2//2]]. Then we compute dL/dx and L/dxx, which turn out to be rational functions of x. We then show that if x E [-1, min I, -1 2 then L/dx/² O, so is strictly convex. We also show that dL/dx < xy. and dL/dx > 0 at xR. thus xR and xy, cannot be minimizers. Finally, we show that the zeros of the numerator p(x) of the rational function dL/dx differ from the denominator's zeros. So the optimal x is the unique solution to p(x) in [xL.
3.3
IMPORTANT OBSERVATIONS
Together, Sections 3.1 and 3.2 explicitly and fully characterize the solutions of (8) in the ridgeless, overparametrized, and large sample regimes. A few important observations follow from our theory. In Appendix L we discuss more on this topie and include details the observations below.
Observation 1: In regime R and if a = 0, 11 < v22, the optimal AF is linear. This follows from Theorem 9 and Remark 2 Indeed, expressions simplify and we get that p(x) pv/2(th1 (x + ) if 11 # I or p(x) = -(2 + p)22 if 1 = 1, which implies that x does not exist (since it would be outside of (=)).xR)). Hence, the first row of Table alwaay gives x = Xg and the optimal AF is linear. Also, when a = O. 1 < 12, we can explicitly compute the optimal objective (see paragraph before Theorem 10p. If furthermore r F. = O, we can show that also when 1/ 1/2, X1 does not exist and x XR. therefore the optimal objective and AF when 1/ > 1/2 have the same formula as when 1 2/ Hence, if = r = F+ 0, 1 2/2, from the formula one can conclude that choosing an optimal linear AF destroys the double descent curve if 1/2 | the test error becoming exactly zero for 1/1 2 1. This contrasts with choosing a non-linear, sub-optimal, AF which will exhibit a double descent curve. This justifies observation 1 (low complexity 1/1 4/2) and observation 2 in Sec.
Fig. (A.B) illustrates this and details the high-complexity (W11 > 4/22 observation.
(A)
(B)
(C)
(D)
w/2
F+ 0
33
0
oa
22
10
08
10 F.
a=
0
0
1.5
Lo 1:
Pork
Lur
Lorgel 11
05
-2
-3
(
( //2
login
login
Figure 1: (A) Consider the regime R1. a noiseless setting, if 1/2 > 1, the evolution of versus ( when an optimal linear AF o* is used, can achieve 0 test error for 1 2 1. However, if a non-linear ReLL is used, we observe the typical double descent curve. (B) Consider the regime Rj. If there is observation noise > 0. the evolution of versus / with a linear AF Vinear only optimal for d/ 1/2. For 111 > 4/2. L is optimal for a lincar AF until 1/1 < C (C = for the parameters here). For 1 C a non-linear AF oT., here close to but different from a ReLU, achieves minimal L. (C) Consider the regime R2. When a RcLU is used (green curves), the evolution of L versus A for both low and high Signal to Noise Ratio (SNR), p is only optimal for a special choice of A. achieving the minimum Lonau (2*) ). However, also for the same low and high SNR settings, when an optimal (non-linear) AF is used (orange curves), we obtain the same, or slightly better, Lg regardless of any careful choice for 2. For low SNR (r2 = 10) we have Lg- Logau (d*)= 0.512 and for high SNR (r2 1 5) we get Lowau (2*)= 0.0220 > L 0.0217. (D) In a situation just like in (C) but with even higher SNR, the difference between the minimum L that be achieved with a particular choice of (blue line ordinate value Lowan )) and the value of L with any choice of but with an optimal (non-linear) AF (orange line ordinate value L becomes clearly visible. Both (C) and (D) show that optimally tuning AFs can be different from optimally tuning regularization. Tuning AFs is always better or equal to tuning A, showing the limits of the connection between AFs and implicit regularization when Gaussian equivalence holds (cf. Section 2.3). We include inside of each plot the parameters used. See Appendix [.] for how to reproduce this figure.
Observation 2: In regime R2, looking at Theorem 2 and Theorem 5 one sees that both & and S, and hence the objective L (cf. (5). only depend on the optimal AF parameters via w22 In particular, we can solve (22) by searching for the cu2 that achieves the smallest objective. Given the definition of we w2((2,5 (. ()) in (32), fixing A and changing & or ja, always allows one to span a larger range of values for c22 than fixing the AF's parameters Ç, H4 and changing A. In particular, tedious calculation
shows that in the first case the achievable range for W2 is mo -1 0J which contains the range
If #22 1 the optimal AF is still linear but the explosion the interpolation threshold #1 = 2/2 remains.
8

---

Published as a conference paper at ICLR 2023
This implics that while for a fixed AF one needs to tune 2 during learning for best performance, an optimal AF is used, regardless of A, we always achieve either equal or better performance. This justifies the observation 4 made in Section [ This is illustrated in Figure (CC.))
in the second case which is (c2 - (/22 (52 (/2 -
+1+ +
In Appendix N we have experiments involving real data that show consistency with these observations. The supplementary material has code to generate Fig. [ and the figures in Appendix N for real data.
4 CONCLUSION AND FUTURE WORK
We found optimal Activation Functions (AFs) for the Random Features Regression model (RFR) and characterized when these are linear, or non-linear. We connected the best AF to use with the regime in which RFR operates: e.g. using a linear AF can be optimal even beyond the interpolation threshold; in some regimes optimal AFs can replace, and outperform, regularization tuning.
We reduced the gap between the practice and theory of AFs' design, but parts remain to be closed. For example, we could only obtain explicit equations for optimal AFs under two functional norms in the optimization problem from which we extract them. One could explore other norms in the future. One could also explore adding higher order moment restrictions to the AF since some of these higher order constraints appear the theoretical analysis of neural models (Ghorbani et al. 2021).
One open problem is determining, both numerically and analytically, how generic our observations are. One could numerically compute optimal AFs for several models, target functions, and regimes beyond the ones we considered here, and determine how the conditions under which the optimal AF is, or not, linear compare with the conditions we presented. We suspect that the choice of target function affects our target function affects our conclusions. In particular, can affect the optimal AF being linear or not linear (this is visible in Theorem 9 in its dependency on p. ef. (12), via the polynomial p(x)).
conclusions. In fact, even for our current results, the amount of non- non-linearity in
Another future direction would be to study optimal AFs when the first layer in our model is also trained, even if with just one gradient step. For this model there are asymptotic expressions for the test error (Ba et al. 2022) to which one could apply a similar analysis as in this paper. One could also study the RFR model under different distributions for the random weights, including the Xavier distribution (Glorot & Bengio 2010) and the Kaiming distribution (He et al. (015). Some experimental results are included in Appendix O Regarding the use of different distributions, we note the following: The key technical contribution in Mei & Montanari (202)) is the use of random matrix theory to show that the spectral distribution of the Gramian matrix obtained from the Regressor matrix in the ridge regression is asymptotically unchanged if the Regressor matrix is recomputed by replacing the application of an AF element wise by the addition Gaussian i.i.d. noise. Because many universality results exist in random matrix theory, we expect that for other choices of random weights distributions, exactly the same asymptotic results would hold. The first thing to try to prove would be similar results for from well-known random matrix ensembles. We note that GGraac et al. (2020) provides very strong numerical evidence that this is true for other matrix ensembles, and stronger results are known in what concerns just spectral equivalence (Benigni & P ché (021))
One could study both the RFR and other models in regimes other than the asymptotic proportional regime. The work of Misiakewwizz (2022) is good lead since it provides asymptotic error formulas derived for our setup but when ~ poly(d), d د co. In this regime, the RFR can learn non- linear target functions with zero MSE (Misiakiewicz 2022 Ghorbani et al. 202T). These formulas are equivalent to the ones in Mei & Montanari (2022) after a renormalization of parameters, reparametrisation that depend on a problem's constants, noted in [L & Yau (2022). is unclear this reparametrisation would change the high-level observations from our work but we expect it to change their associated low-level details, like Table thresholds. It would be interesting to make these same investigations for more realistic neural architectures, such as Belkin et al. (2019a) and Nakkiran et al. (2019), for which phenomena such as the double descent curve is well documented.
Finally, it would be interesting design AFs for an RFR model that optimizes combination of test error and robustness to test/train distribution shifts and adversarial attacks. The starting point would be Tripprraneni al. (2021); Hassani & Javanmard (2022) (cf Appendix CC. The results Hassani & Javanmard (2022) would need to be generalized from a ReLU to general AFs before one could optimize the AFs' parameters.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Song Mei for valuable discussions regarding the asymptotic properties of the Random Feature Regression model. We thank Piotr Suwara for his help regarding Hlermite-type differential equations and their solutions.
REFERENCES
Forest Agostinelli, Matthew Hoffman, Peter Sadowski, and Pierre Baldi, Learning activation functions to improve deep neural networks, 2014.
Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation, 2022. httttttp://aaa.t.
abs 201.2225.2210
Francis Bach. On the equivalence between kernel quadrature rules and random feature expansions. The Journal of Machine Learning Research, (8(1):714-751) 2017.
Chaity Banerjee, Tathagata Mukherjee, and Eduardo Pasiliao Jr. An empirical study on generalizations of the relu activation function. Proceedings of the 2019 ACM Southeast Conference, pp. 164-167, 2019.
Derek Bean, Peter Bickel, Noureddine El Karoui, and Bin Yu. Optimal m-estimation in high- dimensional regression. Proceedings of the National Academy of Sciences, 110(36):14533-14555 2013.
Mikhail Belkin, Daniel Hsu. Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical ilss-vrriance trade-off. Proceedings of the National Academy of Sciences, 116632) 158811114449--8888-- 15854, 2019a. doi: 10. 10.1073/pnas. p000////....000700000 19030701 URL https:/ wwww pnas
brg/dol/abs/11
19030
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1611-1619. PMLR, 2019b.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-1180, 2020.
Lucas Benigni and Sandrine Pé ché. Eigenvalue distribution of some nonlinear models of random matrices. Electronic Journal of Probability, 26(none), jan 2021. doi: 10. 10.1214/21-ejp699, URL
/rrp://///oo..//1.... 1......14422222 jp6999 jj699
Sébastien Bubeck, Yuanzhi Li, and Dheeraj Nagaraj. A law of robustness for two-layers neural networks, 2020.
Weipeng Cao, Xizhao Wang. Zhong Ming, and Jinzhu Gao. A review neural networks with random weights. Neurocomputing, 275:278-287, 2018
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus), 2015.
Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew Hoffman, et al. Undenspecification presents challenges for credibility in modern machine learning, arXiv preprint arXiv:2011.03395. 2020.
Amit Daniely. Sgd learns the conjugate kernel class of the network. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gameet (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL URL/attps://prrcednnnn ctt.:eeeeedeeeeeeeeeeees.e.....e http:://c.cccceee............o.r
10

---

Published as a conference paper at ICLR 2023
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural net- works: The power of initialization and a dual view on expressivity. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gameet (eds.), Advances in Neural Information Processing Systems. volume 29. Curran Associates, Inc., 2016. URL htl_htttps://prcceedingg mee
neur ps. cc/
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018. URL https: http:///pppevvvivieeee
www/ d=H= -GGWC
Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6):141-1422 2012.
Oussama Dhifallah and Yue M. Lu. A precise performance analysis of learning with random features, 2020. / atw.v..ivvvv...///..//.......av.
11904
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional networks as shallow gaussian processes. In International Conference on Learning Representations, 2019. URL httpt:::: httt:::///ppezeview..c wttpreeeee.rraainaddddeeseeeeeee
Izrail Moiseevitch Gelfand, Richard A Silverman, et al. Calcudus of variations. Courier Corporation, 2000.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. Generali- sation error in learning with random features and the hidden manifold model. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3452-3465 3462. PMLR, 13-18 Jul 2020. URLpttts: http::/:////.ceeddnngg www.iiinnsmmm........mm........m prwss/ wwwxees/vv19/geeee / htm.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-11555 2021.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. .0t.tttma...mllm....
PMLR. URL
mlr
Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mezard, and Lenka Zdeborova. The gaussian equivalence of generative models for learning with shallow neu- ral networks. Joan Bruna, Jan Hesthaven, and Lenka Zdeborova (eds.). Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, volume 145 of Proceed-
ings of Machine Learning Research, pp. 471 PMLR, 16-19 Aug 2022. URL https 7/ //ppoceedings..r mlr www.........m..............e..a. ww http///11////d22//11 html
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Ian J Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio. Maxout networks. arXiv preprint arXiv: 3022.339,, 2013.
Mohit Goyal, Rajan Goyal, and Brejesh Lall. Improved polynomial neural networks with normalised activations. In 2020 International Joint Conference Neural Networks (IJCNN) pp. 1-8, 2020. doi: 10.1 10111000NNNNN800..22202 200.0..0..00.002555
Hamed Hassani and Adel Javanmard. The curse of overparameeriizaion in adversarial training: Precise analysis of robust generalization for random features regression. arXiv preprint arXiv:2001.05149, 2022.
Trevor Hastie, Andrea Montanari. Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation, 2019. URL https://arxiv.. http://awwxi..or//baaaaa/a 1903. 08560]
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statisties, 50(2):949 2022.
11

---

Published as a conference paper at ICLR 2023
Tamir Hazan and T. Jaakkola. Steps toward deep kernel methods from infinite neural networks. ArXiv, abs/1508.05133 03.3, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. 2015 IEEE International Conference on Computer Vision (ICCV), Dec 2015, doi: 10.1 1..11000/cc..2155.222
doi. org/
10.1109/ICCC, 2015. 123
Hong Hu and Yue M. Lu. Universality laws for dimensiiaa learning with random features, 2020. http:: wttpaaiwww...gaaaa.aaa 200p://009900..5.5
Lei Huang, Jie Qin, Yi Zhou, Fan Zhu, Liu, and Ling Shao. Normalization techniques in training dnns: Methodology, analysis and application. arXiv preprint arXiv:2009. 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and
generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Maryam Mahsal Khan, Arbab Masood Ahmad, Gul Muhammad Khan, and Julian F Miller. Fast learning neural networks using cartesian genetic programming. Neurocomputing, 121:274-289, 2013.
Jan Kukačka, Vladimir Golkov, and Daniel Cremers. Regularization for deep learning: taxonomy. arXiv preprint arXiv: 10686, 2017.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329-133 1347, 2020.
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sehastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher- student model. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 18137-18151. Cur- ran Associates, Inc., 2021. URL /pp hww.://eeeeee.n..........ee...e. cC cc/ppppr//222//
ppf
Yue M. Lu and Horng- -zer Yau. An equivalence principplleneeeiiipiilelllll kernel matrices, 2022.
principle for the spectrum random inner-product
06308
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. In Proc. icml, volume 30, pp. 3, 2013.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Gabriel Mel and Jeffrey Pennington. Anisotropic random feature regression in high dimensions. In International Conference on Learning Representations, 2022.
Mirco Milletarí, Thiparat Chotibut, and Paolo E. Trevisanutto. Mean field theory of activation functions in deep neural networks, 2019.
Theodor Misiakiewicz.
Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression, 2022. URL httpshttps:///rxiv.oor
abs/2200 10425
Andrea Montanari and Basil Saced. Universality of empirical risk minimization, 2022. URL
https://arxiz/ org/ atsgg///////// 22002 08832
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt, 2019. URL pttl:tttps:///rxii..oo
abs / 1912. 02292
Preetum Nakkiran. Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):12400) 2021.
12

---

Published as a conference paper at ICLR 2023
Andrei Nicolae. Plu: The piecewise linear unit activation function. arXiv preprint arXiv:1809.0953 2018.
Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang. Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference on Learning Representations, 2019. URL httts://openreviii net/ =orummmd----1-110000
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. The emergence of spectral universality in deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 1924 1932.
PMLR, 2018.
Riccardo Poli. Parallel distributed genetic programming. University of Birmingham, Cognitive Science Research Centre, 1996.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007a. URL http:tt:ppoccceeeiiiiiite
wtw.:/eweiiiinn......ieeeeeeeeee seeurips... cc/ http:////...........ooooooeee2e0
Paper.pdk
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007b.
Prajit Ramachandran, Barret Zoph, and Quoc V. Le. Searching for activation functions, 2017.
Andrinandrasana David Rasamoelina, Fouzia Adjailia, and Peter Sinčák. A review of activation function for artificial neural network. In 2020 IEEE 18th World Symposium Applied Machine Intelligence and Informatics (SAMI), pp. 281-286. IEEE, 2020.
Andras Rozsa and Terrance E. Boult. Improved adversarial robustness by reducing open space risk via tent activations. 2019.
Walter Rudin al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976.
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Fundamental limits of ridge- regularized empirical risk minimization in high dimensions. In International Conference Artificial Intelligence and Statistics. pp. 2773-27777 2781. PMLR, 2021.
Mohammadamin Tavakoli, Forest Agostinelli, and Pierre Baldi. Splash: Learnable activation functions for improving accuracy and adversarial robustness. Neural Networks, 140:1-12, 2021.
ISSN 0893-6080. doi: htt.a//cc.....ooooooooo.oooaaaaa
02..0000000222220000022..... URL https: wwww
sciencedirect com/
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparameterization improves robustness
to covariate shift in high dimensions. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:// openreview net/forum d=PxMFDGPnTFF
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Tumner, and Aleksander Madry. Robustmess may be at odds with accuracy. arXiv preprint
12152, 2018.
Michael Unser. A representer theorem for deep neural networks, 2019.
Daniel Weingaertner, Victor K Tatai, Ricardo R Gudwin, and Fernando Von Zuben. Hierarchical evolution of heterogeneous neural networks. In Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600), volume 2, pp. 1775-1780, IEEE, 2002.
Christopher Williams. Computing with infinite networks. In M. C. Mozer, M. Jordan, and Petsche (eds.), Advances in Neural Information Processing Systems, volume MIT Press, 1996. URL https://ptoceediinee www.eieee.iip...e wttppccppppppp..//////o/ /ile/ Paper.pp...... pdff
Adedamola Wuraola and Nitish Patel. Sqnl: A new computationally efficient activation function. In 2018 International Joint Conference on Neural Networks (IJCN)) pp. 1-7. IEFF, 2018.
13

---

Published as a conference paper at ICLR 2023
Zitong Yang, Yu Bai, and Song Mei. Exact gap between generalization enror and uniform convergence in random feature models. In Interaational Conference on Machine Learning, pp. 11704-11715. PMLR. 2021.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning. pp. 7472-7482. PMLR, 2019.
Yuan Zhou, Dandan Li, Shuwei Huo, and Yun- Kung. Soft-root-sign activation function. arXiv preprint arXiv:2003.00547, 2020.
Yucong Zhou, Zezhou Zhu, and Zhao Zhong. Learning specialized activation functions with the piecewise linear unit, 2021.
14

---

Published as a conference paper at ICLR 2023
A COMMENT ON THE CHOICE OF METRICS
A few reason for us choosing norms and in our setup are the following.
We use the LI and L2 norms because these are two of the most widely used functional norms.
We use these norms Gaussian- space because the dependency of performance on the activation functions (AFs) from prior work that we build involves Gaussian- weighted measures. To be specifie, both the sensitivity and error discussed in Section [2. and Section 2.2 depend on the AF only via μoo, f1, and jaz, defined in @.. and these in turn are defined using Gaussian distribution. In other words, Gaussian-weighte weighted spaces the natural space in our high-dimensional setting.
We focus on the derivative of the AF to impose the notion that the AF cannot have sudden changes, i.e. needs to be simple.
We are aware that other choices for functional norms possible, c.g. taking higher-order derivatives and/or higher-order moments of the AFs, and we plan to investigate them in future work as mentioned in Section 4
B COMMENT ON THE CHOICES OF SENSITIVITY
This appendix pertains the choice of definition for sensitivity in 7
We want to relate /r ((( with [| s(x)))? The expectations can be taken just with respect the test data since in the asymptotic regime these quantities concentrate around their expected values with respect to the other random variables.
The gradient V Vaffat,ele exx)) equals " (RO/Vd), where R = diag(o"(@z/Vdd), and for some vector diag(v) is diagonal matrix with diagonal equal v. We can write
V (())|
+(0)|= B Σ a RnOn Naz=
Σ at R(R i.ikk
(26)
Following D' Amour et al. 2020), Appendix E.5, when d - co, we use the fact that (0,z) / vd - Z. where Z ~ N(O, 1), and hence that E Rú = E Eo'((0, x) /Vd) (Z) + o(1) # o(1), to compute Rij.
We need to consider two scenarios. If j. then B R R BR,, , If j. then
Rú R2j BZ)) Let us define #3 = B(o (Z))) Replacing the formulas for R₂ Rjj in (26)
we get that
B| Vl/aaa.. uf TT 01 / (43- - ua) Σ
0 /d
a
(27)
t.k
The first term of the r.d.s. of (27 is exactly eq. (19) on D' Amour et (202)) for which we are
given asymptotic expression and which we use as the basis of Theorems 4 which are themselves a specialization of Theorem 13 The second term non-negative since by Jensen's inequality
H4 = (Z)) 2 (Z)) = Therefore, V[ fa
(ea,)l)))))))))) ,e,))l²) 2 |IE(V (e()).... ?e?=))l??
The results we present, especially those in Section 3.2, are already extremely complex to state and to interpret, even with us essentially optimizing only two parameters, μ1 and μ22 (MD can be assumed without loss of generality). Stating results on optimizing an extra parameter μ4 would make our exposition even more complex, with many more special cases. Only in the specific case where choose the objective (4) for the outer optimization problem ( it clear that μ1 is determined from μo- μn and μ2, and hence it is clear that there is no added complexity in the number of parameters to optimize. However, we still need to find an asymptotically formula for the second term in (27).
At the same time, while the first term in (27) can be expressed as the trace of product of random matrices, making it easier to use random matrix theory to get asymptotic formulas for it, the second term does not easily yield similar type of analysis.
15

---

Published as a conference paper at ICLR 2023
C MORE ON RELATED WORK
First attempts to optimize AFs include Poli 1996). Weingaertner et al. (002)) and Khan et al. (2013). where genetic and evolutionary algorithms were used to learn how to numerically combine different AFs from a library into the same network. More recently, Ramachandran et al. (2017) used reinforcement learning to empirically discover AFs that minimize test accuracy. Their search was done over AFs that were combination of basic units. This work produced the Swish AF. Similarly, Goyal et al. (2020) defined AFs as the weighted sum of a pre-defined basis and searched for optimal weights via training. Unser (2019) provided a theoretical foundation to simultaneously learn a NN's weights and continuous piecewise-lines AFs. They showed that learning in their framework is compatible with learning in current existing deep-ReLU, parametric ReLU, APL (adaptive piecewise- linear) and MaxOut architectures. Tavakoli et al. (202T) parameterized continuous piece-wise linear AFs and numerically learnt their parameters to improve both accuracy and robustness adversarial perturbations. They numerically compared the performance of their SPLASH framework with that of using ReLUs, leaky-ReLUU (Maas al. 2013). PReLUs (He et al. 2015)), tanh units, sigmoid units, ELUs (Clevert et al. 2015), maxout units (Goodfellow et al. 2013), Swish units, and APL units (Agostinelli et al. 2014). Similarly, Zhou et al. (202)) parameterized AF's piece-wise linear units and learnt the AFs parameters to optimize different tasks. Banerjee et al.] (2019) proposed an empirical method to learn variations of ReLUs. [Bubeck et al. (2020) studied 2-layer NNs and gave a condition on the Lipschitz constant of polynomial AF for the network to perfectly fit data. They related this condition to the model's s parameter-sin and robustness and numerically related the number of ReLUs in the model to its robustness.
Several papers proposed new AFs and empirically studied their performance without systematically tuning them. Milletari et al. 2019) identified ReLU and Swish as naturally arising components of a statistical mechanics model. Rozsa & Boult (2099) introduced a "tent" "tent" -shaped AF that improves robustness without adversarial training, while not hurting the accuracy on von-srversarial examples. Zhou et al. (2020) proposed an AF called SRS that can overcome the non-zero mean, negative missing, and unbounded output in ReLUs. Their work was purely empirical. Wurrolaa & Patel (2018) developed the SQuared Natural Law AF, Nicolae 2018) proposed the Piece-wise Linear Unit AF.
way to project input data into low dimensional random features space and it has since then been studied considerably. A great part of the literature has drawn connections between the expressive power of NNs and that of the RFR model, often via the study of Gaussian processes. For example. Williams (199) did this in the context of shallow but infinitely wide NN and the works Sturiga-AAonsse et al. (2019); Novak et al.) (2019); de G. Matthews et al. (2018); Hazan & Jaakkola 2015) did this for deep networks. Daniely et al.. 2016); Daniely (2017) connected the RFR model to training NN with gradient descent.
The RFR model was introduced by Rahimi & Recht (2007a)
In addition to Mei & Montanari (2022); D'Amour et al. (2020), already discussed, other papers studied the approximation properties of the RFR model. Ghorbani et al. (202T) studied both the RFR model and the neural tangent kernel model and provided conditions under which these models can fit polynomials in the raw features up to a maximum degree. These conditions were provided under two regimes, when results hold under weak assumptions on the AFs. Tripuraneni et al. (202T) used the RFR model to compute how robust the test error is distribution shifts between training and test data. This was done in a high-dimensional asymptotic limit when random features and training data are normal distributed. The derivations hold for a generic AF that satisfies some mild assumptions similar the assumptions in this paper. Hassani & Javanmard (2022) characterized the role of overparametrization on the adversarial robustness for the RFR model under an asymptotic regime when learning a linear function with
and N, d large but finite, or when N - co and n, d large but finite. Their
random weights and normal samples. Their AF was shifted ReLU.
Finally, a few papers have studied the behavior of models similar to the RFR but within a different context. For example, (Taher et al. (2021) and [ean et al. (2013) seek to compute the optimal loss function under similar asymptotic regimes of large data sets.
D DETAILS REGARDING THEOREM
The definition of the functions En E1 Ez and x is follows.
16

---

Published as a conference paper at ICLR 2023
(..tct...1.22.11 +x"50 (0102 1/2 1 1)x 50 - -2x -3x² -3x 30122x2 1/2
+ (V/ 1/22 30102+ 1)x
(. = v2x²2 - +1 - 12122 and
E 1/,, 1/2xx = x²5² - -3x²5 (1/1 1)x² + +2x² 5- +3x 52 52+ (- -12---122--222---
where x = x(5.v) = - (V - x2 1)2 452 + x - - (2x²).
(28)
Note that all functions are a function of the square of i.e. 5². Note also that 60 Br Er are polynomials of their respective variables.
E DETAILS REGARDING THEOREM
2
Bun (2.1) = (U2222 - 42)/((12² - 1) 3 + +1 - -3/2)o=2 + +342202 42)
(29)
V (S, 1/2 d)= (1oz² - -wz² M(1222 D)ozz +11 31/2))0 + +3/2202 - 1/22,
(30)
where
(31)
w2 = (V - 1)
-1) //
(32)
F DETAILS REGARDING THEOREM
Bramm (5, 11, (),(()(((1))) - (1-366))o1 +3111111 - -1),. (33)
- -1)/((11-)0r)
where
(34)
@1 - -VV - 4 +1 -
DD). - (2(22)
(35)
G GENERAL THEOREMS FOR THE ASYMPTOTIC MEAN SQUARED TEST ERROR AND SENSITIVITY OF THE RFR MODEL
This appendix referenced at the start Section 2.1 and at the start of Section
Theorem 12 (Theorem Mei & Montanari (2022). If assumptions 1, 2, 3 hold, and for any value of the regularization parameter à > 0, the asymptolic test error (6) for the RFR satisfies
& _ F7 B(G 11..,111222.0 A/12) + (+2 F2 W...1.1/.... A/12)) F??
(36)
where E denotes convergence
probability when d spect to the training data D. the random features O, and the random tar- get Sunction Sa. and where BCC.vi.12 (CC.VI,VV2.A = 8rl1, (1G.01.42) W) v1, V2, and the functions Eo. E, Or are defined as follows,
oa with re-
6.5..41.40 22, T)/Eals. Voll,,1,,,00 v2. d),
22,
x5 +3x 5t (112 1/2 4/ 1)X 2x -
+ +W/1 + 1/2 3t/ 1/2 + +x² 3//12x 11122.
BiCc 2/2, 5) 32X²((" " v/2x 2² 2 V162.
El6, V1, 2/, 5) = x556 3x + (11 3 +2x² + +3x3 --V1-
x2,
where Xb,, U2 = vi (i(w 22z))/1
v2 (=(((1 and v and v2 are two functions specified in Def. in Mei Montanari 22022
17

---

Published as a conference paper at ICLR 2023
Theorem 13 (Eq. (19) Amour al. (020 ). assumptions 1, and 3 hold, and for any value of
the regularization parameter d A/p O. the asymptotic sensitivity for the RFR, namely equation with f = fa.0 where fa.e is defined as in equations ① and (2) satisfies
s s = i
R? fr (x - 1)96(c, 11,22.))
91CC.V1. 12,1)
7 +
2213, 11K.411,22211
(37)
Dol. 1 22
where La denotes convergence in probability when d - with respect the training data X, the random features O and the random target function fa. and where
Pols. 12. 1) x 3x + (1/1 1/2 v/22222 5 2x 2x² 5" +3x
(38)
+ +31//1222 - 1/2 -
x2 31/ 3//22x 2 +
1/12//
91C.v11.2. 1) = x056 -2x² (W1022 - -1
(39)
+ +x*+² - -2(1 - -1 (wi 1/2 +0 1)x² 2²² -x²
2rl, 11, 1/2 2) - 1)x² 5d x²6² + (w) +
(40)
and where X is defined in 28
Remark 9. Eq. (19) in D Amour et al. (2020) is expressed in terms of the asymptotic limit of
||a+ See Appendix for the connection between this representation and equation 7 in our definition of
H DETAILS REGARDING THEOREM
(0.teoS..V1.000 = - -11- +
3x
(41)
+ +3b110 v/ - - - -x -x - 3611 + +0142
11, v2)
x - -2x² 11162-11-11 1)x
(42)
~ 2- 2(1 (1(2)x + 11/2 11x2+ 12x222-
22 (1.
1/2) = (v- - 1)x - x²62+ (0) + +1xx2++**
(43)
where x is defined as in 28 and 1/ = min(W)1.2))
I DETAILS REGARDING THEOREM 8
The formula for g($) is as follows:
g(s) = Pe (c))=(e)((ee (s/v2)) (1 (2+)))=++++)))) erf (s/v2)) (2112))-v221 -V2/zs)
(44)
J DETAILS REGARDING THEOREM 9
J.1 RELATIONSHIP AMONG THE CONSTANTS IN TABLE
This appendix is referenced in Remark 4
The following relationships can be derived either from the proof of Theorem or from a direct computation based on the formulas given in Theorem 9 They do not add critical information to what is proved in Theorem 9 but they give general rules to exclude some cells Table II
Remark 10. Let di < U22 If d/2 < min min 4/ 1), then at < ac < QR. In this case, the 4th and 5th rows of Table I never happen. If d/2 > min // 1), then aR ac d'. If #/2 = min(241. 1/1 + 1}. then az ac = a'g- We always have that a' ac ag E [0, 1], and 0 S B2 B2 < <1.. Since Ej and E2 cannot simultancously hold, no two
simultaneously hold. Since B3 < B2 < B1. no two columns can simultancously hold. Remark I0 follows from Lemma M.13 used in the proof of Theorem 9
18

---

Published as a conference paper at ICLR 2023
Remark 11. Let 1/ 4/2 We always have that a' E [O. 1]. It also holds that ac [0, 1] if and only if 1 = 12/(1 p|1 - 1/2l)) when 0 p f T and w1 2//(11 p|1 #/2)) when p 2 1wh-17 We
have that or E [0. 1] if and only if di = 2/2 + p 1)2 min (1/2. 1) and
11 -1 1 + p(vz - 1) + m 1,1)
(1/2.22.2 w22)
2(max 13 + - 1)9)
Note that 11 4/2 = then ar not defined, see statement of Theorem If we had attempted to use the formulas above we would have gotten that or E [0. 1] if and only if s 1 s 1, this last condition never being met when 1 4/2 = 1. Also, A I B always, where A and are given in (67) and (68). Furthermore, B 2/2 if and only if 1/p > y A min max 2 11}. Since A - B, it follows that Ej and E2 cannot simultaneously hold, and hence no two rows can simultaneously hold. We always have that B3 < f3 < B1, therefore no two columns can simultaneously hold. Remark follows from Lemma M.14 used in the proof of Theorem
J.2 STATEMENT OF THEOREM WHEN VI 2/2
Theorem conninnued). Ifv/ < U22 then Ei = (ar < aR)) E2 = (a > aRR)
B min - 4, -3411 - 88/1 vil maxmm/xx//1/_)) (??) + max (1/41,1444 (1/
(45)
B2 v1(01 21/11/11 1),
(46) B3 + |1 - 1 (min 1/v1),
(47)
aL = /2/(12 + 1 --
(48) ac = /2/ + v + max 1 41 + +
(49)
aR 22/(3/22 min(1 + vn. 201) + )
(50)
Furthermore, the polynomial p(x) is defined as follows.
1 # 1 then p(x) - po PIx p2x² p3x² pax* + paxx where
Po - 16 (p(a 4mhh + (3ar - 1) + a)
(51)
P1 2011 - 1)wh (p(arss11941 - 6662 4) 122 2//1222) -200h1)
(52)
P2 24/1 (p(a + ( 3) 1/244a 9an + +361 1)) a(3b) 1))
(53)
P3 4// (p(a(77/1 2) 30up2 2/2) ar)
(54)
= p(a(12)) - 1) - 304p2 + +122) - a.
(55)
P5 2ap,
(56)
I/v1 I then p(x) qo + q1x q2x² + q3x² where
40 = p0110
10a + 10a22 41/22 4a,
(57) 91 = p(-20k + 12a4//2 41/2 + 4a.
(59)
42 p011111 300b 2/22
(58)
and q3 -2ap.
(60)
19

---

Published as a conference paper at ICLR 2023
J.3 STATEMENT OF THEOREM 9 WHEN 11 1/2
Theorem continued), If vh > 1/2 and d2 # then Ei (bi<B) V ((a<aa)) A (B))))A))
E2 (1/>A) ((a>aR)) (B<))<A),
B1 r(B) 0, where is a 4th degree polynomial described in Appendix J.4
(61)
B2 2/2 + (20222(222 + 11+++ +1++=++1 ))))),
(62)
B3 2/2 + (min 2, 1/42)a//2 - 11 ((t/ - 1)2 + p 3))),
(63)
ar. (2/11 (22) +
(64)
ac (pvi (11 /2) (p (max {0. 4/2 + 2 -22) 1),
(65)
2 ( (1) max (1. -p (1/-1)) #2
(66)
(w2- 1)2 (p (2 min (1,v2) -26))+())) -p-1)
2/2 + (p min
12) and
(67)
P (2,==)))002=2++22mmm0-0=-1-1111 +201)))2222222-2 max
max 13-62
(68)
1/ 122 and 1/2 1 then E False, E2 True and eqs. 61 688) hold when reading Table 7
except (66), which is not defined, and (65) which becomes ac 00 implying (a > ac) is True
Furthermore, the polynomial p(x) is defined follows.
p(x)= - Po+ +pxx + p4x** +psx where
(69)
Po 3 (p (v² - 1 (2ar/) - (3a + 1)42 + a²) + (nv/ - 2(ar + 1)6b a 2011)
(70)
P1 24/ (w22 (2a (4/2-1 -1 + 11) -p (12-1) (7a+2 (4a4 1) +
(71)
P2 2// (a (31/22 - 1) (13a + 3) 2//2 (3arb) + 5a + 1) 20rh + a + w1
(72)
33 4/2 (p (2a (1/1 + 1) - (6a+ + 1)/2) +a)
(73)
P4 P (2ah1 (Ila 1)1/2 a) +
(74)
P5 -app.
(75)
J.4 DEFINITION OF THE POLYNOMIAL r(x) WHEN 1/ > 1/2
This appendix referenced in the statement of Theorem equation (61.
The coefficient B1 is such that r(ß)) O, where r(x) = ro FTX F +rxx + 14x* with
ro = p== ([144pp+p-6+pp) (aat)))+((((((( + 1)p 28a +5)+ +6) + 16alaap 1)(-4ap +( 1)3),
ri ((0)))((00000000000))))))))))))0 -3)=-11-- p+ 12arp1/2 -)
-4r(p 1)((2r 3)p 3)(((cr 1)p 1)),
72 2- 20pp+ +10-00000003332000000-----000000
= = p 12
+ 3p 4) 2(p + 1)3) - 4p and
r4 P²W2.
20

---

Published as a conference paper at ICLR 2023
K DETAILS REGARDING THEOREM 10
The coefficients of p(x) are given below
Po 1
(76)
P1 8/2p
(77)
P2 222
(78) = 4a,
(79) and p4
(80)
L IMPORTANT OBSERVATIONS
This appendix is referenced in Section 3.3
L.1 REPRODUCING FIGURE
The plots in Figure | come directly from theory. They involve experiments and can be obtained using many standard mathematical computing software tools. Nonetheless, since does require effort to code
equations, include code to generate Figure [ in the follow- ing Github link: https: /github. fom/Jefffange 7//77/FFFF /RFR_ This code is also available in the supplementary zip file provided. To generate the plots in Figure [ run the file named RunMeToGenerate eeweeeerateiiuuuue guur 1. nb. It runs using Wolfram Mathematica V12. We ran it using MacBook Pro with 2.6 GHz 6-Core Intel Core 17 and GB 2667 MHz DDR4, In this machine takes about second to run.
L.2 SOME DETAILS ABOUT OBSERVATION 1 SECTION
When 0 and 1 2/2 and using Theorem g explicitly compute the objective L Eg, (F3 F? max 1 d 0)b2 / ( if w/ < 1/2, This follows from making 0 in the expressions the paragraph before Theorem TO Observe that, as function of d/, the test error ERi achieves minimum of (F2 + r-)/(11 1/2) at 1 if d/2 1 1/p and minimum of (Fiv22 + F2 at 11 0 otherwise. In particular, if F+ 0* then the condition 1/2 1 1/p becomes 2/2 1.
When 0 and 1 2/2 the polynomial that determines x1 becomes
p(x) 4/2 (-4122² (1/+ 2 (342-2)) x² x2 (12 (11+02 (2/2-11)) x- (12-1) 2
(81)
One can show that in the range 1 > 1/2 and x (xL. (-1/, (0. 1 )2))), we have p(x) < and hence it has roots. Therefore, xı does not exist. Therefore, if furthermore have F. 0. then condition Eg is never true, so x must be read from the first row in Table [2] which implies that x .RR and the optimal AF linear also when 11= d2.
M PROOFS
This appendix is referenced in Section
M.1 PROOF SENSITIVITY PROPERTIES SECTION 2.2
Proof of Theorem The proof follows directly from Theorem 13 by taking the limit when 2
+0.
Proof of Theorem +00.
The proof follows directly from Theorem by taking the limit when d/
Proof of Theorem 400.
The proof follows directly from Theorem by taking the limit when e//
21

---

Published as a conference paper at ICLR 2023
M.2 PROOF OF NECESSARY AND SUFFICIENT CONDITION FOR LINEARITY OF SECTION
Proof of Lemma 3.7 If is linear function, a direct calculation shows that = 0. On the other
hand, since 0 < (Z) μo f4r Z)² n2 we have that μ O implies that o rr = #4 yuy Z almost
surely. Since the support of the probability density function of Z is R, it follows that o p40 + Mxx except on set of measure zero in R.
M.3 PROOF OF THEOREM
To prove Theorem 7 we first need state and prove series of intermediary results.
Lemma M.1. A necessary condition for optimally of (x) is that
2x)o'(x) 20 (x) + d1 d2x + 1x) O,
(82)
where d1 22, and 23 satisfy the following constraints,
dς + A3/1 = O,
(83)
-241 + 12 A3/11 0.
(84)
2B(((o 2B((o'(Z))) + 1140 + 12 + +A3/12 = O.
(85)
and that
lim (o'(x)) 4 lim (or 7 =0
(86)
Remark 12. Note that since 82 is a second order ODE, its solutions are parametrized by two constants in addition to being parametrized by d2, These five constants are set by our three constraints 19) together with two boundary conditions from our variational problem, which are
limy o (x)e 7
These last two we replace (see proof) by (86).
Remark 13. The lemma implies that knowing μo: Mr, H2 and the objective value B((r'())) is enough to determine d₁, 12, even without solving the ODE.
Proof of Lemma M.1
Derivation of equation 82
A Lagragian for 19 19--
is
B(Go' + +1 - (Z)) A2(11 - Zo(Z)) + 1s((1/2)42-0((2)
(87)
which can be written as I L(z,o, o' where, if we define p(z) = - x density
the Lagrangian
'2xx
Lzz,r,,')) = ( 2 d1(po o) + A2(111 - 20) As(1/2)( - 0²)).
(88)
We use the Euler- Lagrange equation with free boundary conditions Gelfand et al. 2000 to get the
necessary condition 82). To do so, compute in sequence
01.
p(2)(1 + +22 d20r)
(89)
åo
p(z)(2r))
(90)
do'
+ p'())2o'' + p(=)(2o')) =2(XK2200'200")
(91)
dz do
These lead to
d äL
aL
p(z)(-2zo' +20" d1 + d2z 1307) and
(92)
dz do
do
0L
0= lim
lim (z))
(93)
200
do
2000
where the last condition follows from the fact that there is no boundary condition on σ. Since p(z) > 0, equation (92) implies
82).
22

---

Published as a conference paper at ICLR 2023
Derivation of equations (86): Since we are working with necessary conditions, we can choose not list (93) in our lemma. Rather, include condition (86), which consequence of the fact that E( (())) must be finite. Indeed, B((or(Z))²)= [ ((z)
implies that (z)))
must vanish at too. Although not necessary for this proof, note that, since p(z) goes to zero as z #o0, equations (86) imply equations (93
Derivation of /equaaions
Equation (2) must hold for all x. Hence, we can replace in it x by standard normal random variable and compute the expected value of both of its sides. This leads
2 B (Z)) 2 B(o" d1 + Aap0 = O.
(94)
We can also multiply (82 by x, replace by a standard normal random variable Z and compute the expected value of both of its sides. This leads to,
-( 2B((z d2 + 13/1
(95)
Finally, we multiply 82 by (xx), replace by standard normal random variable Z and compute the expected value of both its sides. This leads to,
2 (B(Zo(Z))r' (Z)) (Z)or + A1440 + 1231 + A3f12 = 0.
(96)
Using integration by parts, and the fact that for p(z) V2x
we have that p'(z) = -zz((z) and
p"(z) (1 p22)p(2), we derive the following useful relationships
B(o"(()) B(Zo' B(Zo"((Z) = -((Z (Z))
(97)
(98)
B(o' M4.
(99)
B(or(Z))"(Z) B(Zo (Z)) -((o
(100)
To derive these relationships via integration by parts we made use of the following relationships
lim o' (=)))r))))() 2-2200
lim d'())p((z) = lim o'())((z) = lim ((z)p(z)= O. 2-200
(101)
2-200
z-20
which can be proved from (()))))))) B((o' (2)) co. Also, from B((r(2)) (Z)) 00
and R. we can show that each of the expected values in the right-hand-side of (97 110 is well-defined. Hence, the left-hand-side of 997
(100) is well defined.
To finish the proof we replace (97) in 94 to get d1 + d3/40 O, which is equation 83 Then we
replace (98) and (09 (95) to get 2p1 + d2 A3/1 = O, which equation (84). Lastly, we replace
(100) in (96) to get -2 B((o (Z))²) 11 A2 + d3322 O, which is equation (85)
Lemma M.2. The solutions of 82 are of the form
x2 1115)
o(x)=0(x) + C.H.
+ c2F
(102)
T
2
where
12x
2μx²
xx2
T(x)=
2
F
(1,111222)
2
if =0
(103)
Txx)
di
12x
π
d2e
erf(
x
1
d2x 2
x²
ifd3
=
(104)
2
2
V22
4
2
d1
dzx
T(x)=
1 (0
(105)
d3
dg
2
where erf is the Gauss error function F(ox).(b)) parameters (ax), (bx), and Hr is the Hermite polynomial, extended possibly non-integer
(br) is the generalized typergeometric function with
23

---

Published as a conference paper at ICLR 2023
Remark 14. By extension of (2(x) to non-integer mean that Hx(x) F -- (- (2)) which is defined for non-integer
Proof of Lemia M.2 Since 82) is second order ODE, its solutions are spanned by any particular solution (r(x) plus a linear combination of two solutions to associated homogeneous ODE. The homogenous ODE associate with (2) is -2xo'(xx) 2x" 13) O. The change of variable o(x)= (x)v2) allows to get (xx ō²()) (xx O, which is well-known ODE called the Hermite differential equation. This implies that the homogeneous solutions of our ODE are spanned by H
and
The particular solutions (xx) can confirmed by
V2
(
direct substitution.
Lemma M.3. Let o be of the form 102.. 1f 0, then B((o'(Z))² < co implies that oxx) is of the form
xd2
(xx) = c+
(106)
2
for some and that B(((r'(Z))²) 12
Proof of Lemma M.3 If A3 O then based on Lemma M.2 we can re-write that
x2
(xx) cieffi
+ c2
2d2
(107)
v2
2
for some C1, C22 where erfi is the inverse of erf. From this it follows that,
o' (x)
e
4c
v2rd
2.2
(108)
V2
The objective B((or((Z))) < co implies that (o (x))² = 0. Since limy erf(x) +l,
we have that lim (o (x)) - implies that 4c + V for both = simultancously. This implies that ci d1 0.
Substituting c₁
0 in 107 and simplifying get (r(x) c2
From this expression Aax 2
can then directly compute B((o' 3
Lemma M.. Let be of the form 102). If 2, then B((o'()))²) oo implies that oxx) is of the form
A1 2 (xx) cx
(109)
for some and that B((or(Z))) = c
Proof of Lemma
M.4 If 13 2 then based on Lemma M.2 we can re-write that
x²
o(x)=
x22 (1.11).(3.2)
+2
+ +2v Viczerfi
x
201
)
+
(VZndzerf
+ 402
2211
(110)
V2.
V2.
for some с₁ and c2, where erfi is the inverse of erf. From this it follows that
201 Viczerfi x
x
o'(x)=
A2x2
(1.1).(3.2)
(111)
22
2
The objective BZ(r)(Z)))
implies that (0
0.
Since
limy-
erri
lim, +200
(x2F (1.11.133.2 (2) =0, and since
2212
v2
x2F x2.(1.1.(322)) 2
lim x
17.
(112)
x erfi
v2
24

---

Published as a conference paper at ICLR 2023
follows we only have finite objective if -vec that 22 O.
v2 4 for both + simultaneously. But this implies
Substituting C = A2 = in (10), and simplifying, leads to (xx)) c1 V2x 4. The v2 The absorbed by From this expression one can compute B(())
factor can be
Lemma M.5. Let a be of the form 102 If $ (0, 2}, C1 = 02 = 0 then
11 A2x
oxx) =
(113)
A3
1 - 2'
and
d2
B((or(Z))))
(114)
(13 2)
Proof of Lemma M.5 This follows directly from Lemma M.2
Lemma M.6. Let be of the form (002). If & (0,2), and either 0ı e2 non-zero, then ((())(2))) < oo implies that d3 = 4k for E 2"
Proof of Lemma M.6 23 (). then by Lemma M.2 we have a formula for (xx) from which we get that
cıdaHl 4-1
v2
2
12
o' (x)
V2
2
F2
(1-)).1))
2
d1
(115)
where F and H are as defined in Lemma M.2
The boundeness of B((o'(Z))2) is dependent on how fast X + #00.
4/2
+ v2
and
(1- 11-47 (.(5)
grow as
c1 = 0 and C2 # 0, B((a'(Z))² < oo only if (xF
(1-4111)
< co, which in turn is true
only if lim (xF (1- ).())
(22 )² -
O. This implies that d3 is even.
cf # and C2 = 0, (Z)() < oo only i (H xz) [2 ())))) < co, which in turn is true only
lim, H
This implies that l3 is even.
v2
C2, C2 # (((o(((' (Z))²) < co only lom (z' = =0. But xF 2
grows much
(1-4
faster than H implies that d3 is even.
x
as - co, hence must be that lim (sF 11 1.11
This
Lemma M.7. Let d3 4k for k Zt. and let o(x) be a solution of
8 then
Ai
12x
(xx) =
+ cH2x
(116)
A3
13 -
v2
for some and
B((o((2)))) (1((22)!)
d2
(117)
(2k - 1)!
d7 -
Proof of Lemma M.7 Af 4k then
(-1)+k!
((2),,)) (2/2)
(2k)! Has/(x/V5,
(118)
25

---

Published as a conference paper at ICLR 2023
and hence the homogenous part of oxx) can be written as cHas/2(x), from which (166) follows. From this expression follows that
cd3H 13
(2
A2
o'(x)
(119)
V2
d3
and from this expression the value for B((or (Z.))) follows.
Lemma M.8. Let be of the form 102 of the form
If A3 $ {0. 2}, then B((o'(2))3) implies that o(x)
o(x) =
A
12x
+ cH2sf2
x
(120)
A3
A3 -
V2
for some that must be zero if A2 # 4k, k Z², and
4 ((2))!)
d2
Bi(o' (2)))
(121)
(2k - 1)!
1-
Proof of Lemma M.8 This follows directly from Lemmas M.5 M.7
Lemma M.9. If A1, satisfy
(83
85 then
22
= 11..
(122)
A1 2
Proof of Lemma
M.9 Defining R = B((o'(ZZ))² and solving the linear system (83
85
leads to
240 (R- 11))
2/11 (46 μ2 + R)
2 (R 21)
A 0 + mr 12
.2
.13
(123)
H + m H1
113 + m 142
Computing A2/(13 - 2) we get - from which the first relation follows.
2(R-Hi) for R and recall that μ #42 H - Mr, the second relation follows.
If we solve d3 1
We are now ready to prove Theorem 7 which we restate here for convenience.
Theorem (7). The minimizers of 19 are
(xx) ax² + bx c
(124)
where
a + H+ b pl, and c 4o a. V2"
(125)
Proof of Theorem 7
We will show that any minimizer of 199 must be function (xx) ax² +b for some a. b, c. From this fact, the variational problem can be reduced to a simple quadratic programming problem over a, b, from which it straightforward derive (24) and (125).
μ.+ then by Lemma 3.1 we know that the solution must be linear, and hence we are done.
If μu, 0 then by Lemma 3.1 know that (xx cannot be linear function. Hence, from Lemma M.3 and
and Lemma M.4 we know that A3 cannot be 0 or 2. Therefore, its solution must be of the form specified by Lemma M.8 with 0 and 4k for some & Zt
Define R = (Z))) From the constraints 19 we know that d,, d2 and R can be written as linear function of A3 4k. In particular, R = nr
da 22. From [11 and Lemma M.9 we can write
$*(22102 c + = which implies that c = that R = 12k-1y
R-H²
is also a function of 13. Therefore, the
Akazaan
solution to is parametrized by d7 alone which must be chosen to minimize R = μ4 2 μ² Therefore, must choose d₃ 4, the smallest possible multiple of 4. This implies that Hxx22x/VV2) is quadratic function, from which it follows that (xx) also a quadratic function, and hence we are done.
26

---

Published as a conference paper at ICLR 2023
M.4 PROOF OF THEOREM
Before we prove Theorem 8 we will state and prove series of intermediary results.
Lemma M.10. A necessary condition for optimality of (x(x) that
x x + A2x + (xx O, for all x : (x) #0.
(126)
where d1 12, and 23 must be such that,
B(rr(Z) μ0-
(127)
B(rr(Z)Z) 141
(128)
B((r(())) M22
(129)
Proof of Lemma M.10 A Lagragian for 126) is
(()o (Zz) d2(111 (z(Z)) A3((1/2)(u2- -
(130)
which can be written as _ L(z, or, o o')dz where, if we define p(z) = 1 + the Lagrangian
122m
density L is
1(2,0,0')) p(=)(oo)) - σ) 12( 20)) 13(1/2)( - o²)).
(131)
Any variation ( of optimal (z)) must yield (z)+ B()or((2))), In particular, this must be the case for any variation such that 17(2) = 0 whenever (2)2) = 0. If we focus on these variations, from B(}or'()) + (z)()))) 2 B()o'(z))) the Euler- Daglan-aggangge equation can be derived despite |-| not being differentiable at O. To be specific, must hold that
d aL dz êo do
dL
= 0 Vz (z))) * 0.
(132)
Since there are no fixed boundary conditions on our integration domain (-o0, oo). it also needs to hold that lim AL 0o = lim p(2)o'(2) 00, which we choose not to list in our necessary conditions.
Since d AL 0 if (2 # O, equation (32 implies (126). First order optimality conditions imply that the Lagrange multipliers must be choose such that B(o(()) μoo B(o)()Z)) μn, B((o(Z))) 42.
dz 0o'
Lemma M.11. 1f # O, the solutions of (26) are of the form
o(x) = 21
1 1 d2
min(max (x, (x,bb,c),...
(133)
d3 d3
for some constants b, where < c if 1odg s 0 and b > otherwise.
Proof of Lemma M. Since or is one-dimensional function, the requirement of existence of weak derivative implies that there exists v absolute continuous that agrees with or almost everywhere. We will work with these absolute continuous representations of a. Other solutions can differ from the absolute continuous solutions only up to set of measure zero with respect to the Gaussian measure.
From (26) we know that wherever o' (xx o O, we have that o(x) ax + b for the same fixed and b. Hence, since or is continuous, or must be an alternation flat portions and portions with the same slope Because of continuity, cannot have a flat portion interrupt portion of slope (unless a = 0), as illustrated in Figure right, and or must be as in the other two cases Figure These have a form as in (133).
Lemma M.12. Let or be of the form
133 Then,
1
1
d2
B(lo' (2))
P(Z (b.
(134)
2
1 d2
#n - B(Zo(Z))
P(Z [b. cl).
(135)
A3
where [b. c] should be interpreted (c, b) if b. In particular, B((o'(Z))) [pn].
27

---

Published as a conference paper at ICLR 2023
Figure 2:
The first two functions are the only two possible types of continuous functions that satisfy 126 The right-moot most function also satisfies (126) but is not continuous.
Proof of Lemma M.12 From Lemma M.11 we have explicit formulas for or and o' The proof boils down direct calculation of the expected values, which themselves boil down to computing few Gaussian integrals.
We are now ready to prove Theorem 8
which we restate below for convenience.
Theorem (8. One minimizer of 33
(xx) = po + a min -x)
(136)
where a erfis/va) erf is the Gauss error function, and E R is the unique solution to the equation
e + erf
s
2
M
g²
(137)
xx (1 (1-erf erf
52 erf
12
if Ux # 0, and s if u+ =
know that if d3 * O, then any minimizer must have the form (33). From Lemma M.12 we know that all of the functions this form have the same objective. Hence, if l3 # O, all the functions of the form (13 that satisfy constraints [19 are global minimizer.
Proof of Theorem From Lemma M.11
1 # 0. To satisfy the three constraints (9)) have 4 remaining values play with, namely d2, b, c. Hence, we set b -c. With reparameterization, this leads to o having the form o(x) = 5 mma (x. s). where has a new meaning. That is, or is flat outside of the interval [-s/|a|, s/la|]. 2 0, and inside of this interval it has slope a. The goal is to find a, b, from the constraints 119.
We
From (xx)= b + min mammmmmmmmaaa (max(x, -st, ss direct computations leads to
Ho b,
(138)
#1 aerf
(139)
1/2
2 π
#1 = a² 152-1) erfe
+ a²
se
+ b
(140)
where erfe = 1 erf. We can use the first two equations to write b and function of μo- $1.5. Substituting a and with these functions the third equation, and simplifying, leads to
1 (s² 1) erfe
s s--1
#12 = 1á0
(141)
erf
Recalling that μ22 212 11 + H3: replacing this definition into the above equation, and simplifying leads to
erf
V2
(142)
2
e
erf
(s2 + erf
v3
28

---

Published as a conference paper at ICLR 2023
One can show that the function the right hand side (142) is monotonic increasing in [-00, co] with range [0, oo], which implies that there is only one s that solves (142).
M.5 PROOF OF THEOREM 9
This proof involves heavy algebraic computations. To aid the reader, this paper is accompa- nied by Mathemetica file that symbolically checks the equations both in the theorem state- ment as well as in the proof below. This file is in the supplementary zip file, as well as in the following Github link pettps://githan com/Jefwwangg//RRRRRR..... AF is called www.aeeTocchcc.Poooffffeeee
.n..
Proof of Theorem? 9
Theorem 9 amounts statement about the solutions of the optimization problem
22 for regime R
Its proof amounts to studying the local minima of the objective via its first and second derivatives, both the inside and on the boundary of the variables' domain.
We will prove the theorem for v < 2/2 and v > 2/2 separately. For v/r = 1/2 the objective is not defined.
In what follows, we let L = (1 - a + aaSp
Ri We will use the fact that L is a one-dimensional function of 2² [0, +oo], as be seen from (13) and (16). We will use this and the fact that (28) defines a monotonic function between, X and Z2, to express I. as a function of x and study the
solutions of the optimization problem 22
in the variable X- Notice that 28 can be solved for z² as 52
y( mix 4h and, calling
r+min (n) )
by x, this can be arranged to get 23 which connects optimal values of with optimal values of μoo M1, u2. Henceforth, we denote X by x. We note that since z² [0, too], from (28) it follows that x E [x1,xR] A [- min v/2,, min - min( H. Hence, we only need to study the function L(x) in this interval.
Case 1, 1 3/2:
For the sake of simplicity, and for the most part, we will assume that 1/1 # and omit the argument for 11 = 1. The argument when 1/1 1 is almost identical to the argument when 1/1 o if we work with the extended reals [-o0, oo). Furthermore, most conclusions for 1/ can be obtained by taking the limit of 11 - 1 with 1 $ 1. The only situation where this is not the case is that the polynomial p(x), referenced right after [ has an expression when 1/ = that cannot be obtained as the limit of its expression for # 1/- We will also assume that 0. Recall that we are already assuming that a < because when a = our problem is trivial. If a = one can check that L(x) is a decreasing line, hence the minimum is at XR, and this solution can be obtained from the first row of Table
[ This solution for a can also be obtained by studying a > O and taking - O. Below thus assume that 0 < a < 1.
We start by studying the second derivative of I.. A direct computation yields
L
L(x) + C, where C 2F/aa
(143)
dx
1/1 12
and L(x)= 20FFfi(-3x"(01-1 -12 1
((x+)))-)1)
dxa tedious calculation (omitted) shows that JLL 2 0 for x [xL,xR] (i.e. it convex), that
L(x)) < L(xx), and that d x2) From this it follows that, depending on the value of v/2, the concavity LL is positive negative, illustrated in the following figure:
di
To be specific, starting from large 2/2, i.e. small -C, and decreasing its value, i.e. increasing -C, obtain the following four scenarios. While d/2 is large and -C is bellow Ag, the function L is convex. After 2/2 reaches a value B1 at which -C touches A2, the function L is convex for small x, then concave, and then convex for large x. As 1/2 keeps decreasing, and after it reaches value B2
29

---

Published as a conference paper at ICLR 2023
A3
(())
(
Ö(æ)
Ö(x)
A
Ag
-C'
convex
2R
convex 2
concave
concave
RR
Onnve Mon
Figure 3: Depending on value of (/2, the function convex, convex-concvve-convee, concave-convek, or concave respectively. The points A, B, and will referenced later in the proof. It is possible to compute closed-form expressions for the y-coordinate of these points.
which -C touches A,, the function L. is concave for small x, and then convex for large x. Finally, after 2/2 reaches value B3 which -C touches A3 the function L is concave. Note that by definition 0 s B3 < B2 < B1.
is possible compute closed-form expressions for the y-coordinate of the points A1, A2, A3,
VI-M++
which we denote by A1, and A3. Namely, A1 12a(2 in A. Ffax
2 if
V s 1, and A Ffer M1-
if 1 1, and A3 Fia max
20h 11-1612 Φ1
Using
41
the closed-form expression for -C, see 143). we find closed-form expressions for B1. B2, and B3 as Bi 1/2 A2(12) + C(b2)
B2 1/2 (1 + C(122 0, and /3 1/2 As(w2) + C(v22 O.
By definition of B1, B2, and B.. these equations have a unique solution when //2 > 41 and their explicit expressions
given in (45). (46) and (47 respectively.
Now that we have characterized the curvature of L(x), we are ready to locate its global minimum. To do so, we will use the curvature of L(x) together with the first-order optimally condition dL dv = 0, and
the following three extra pieces of information: the sign of the derivative of L(x) at x1; the sign of the derivative L(x) at x XR; and the sign of L(x1.) - L(vR).
A direct computation yields
dL
Pn + PIx p2x² + p2x² + p4x* + psxx
if * 1, and
(144)
dx
(W1 (x + (2 1/22)
dL 40 + 41x 92x² q2x²
if 1.
(145)
dx
(-+x)
where the coefficients .o..... P5 and qo ... ..... 93 are, apart from multiplying constant, given in 51 (60).
The roots the first denominator, i.c. V أ and vor v/. are not root of the first numerator when 1/ * 1, and the roots of the second denominator, i.e. -2, are not root of the second numerator when W/2 1/1
Therefore, the first-order optimality conditions are p(x) O.
Not all solutions of p(x) 0 minimize L(x). To locate the minimizer, we use the sign of the derivative
of L(x) a = xx; the sign of the derivative of L(x) at x = XR; and the sign of L(xx) ) L(xR). These
signs can be determined using Lemma M.13 Lemma M.13 also proves Remark 10
30

---

Published as a conference paper at ICLR 2023
Lemma M.13. 11 2/2 the following relationships hold,
dL
Fi (a - 1)/22) + (F.2 +2²
(146)
dx X
1/ -1-4/2 1/2
dL
1/24/22 (17(-4V/ + 31/2 + 1) + F2 + +
if S 1.
(147)
dr
V/ - 1/2
[==x
dL
(a +2a011 30/2 + 1/2) (F+ 2 +2
i/ > 1,
(148)
dx x=*
1 - 1/2
L(XL) L(xR)= = 1 (Fi 200/ + (2a 1222) a (F2 +-))
if S 1, and
(149)
4 - 4/2
a (F+ 2 + +-) Fi Fi2(1 - 22r2/22 + 122
L(x)) =(XR)=
if 1.
(150)
$1 V 1/2
Also.
dl.
dl.
< < a < az and
2 0ifa 2 aL
(151)
dx x=x
dr x==x
dL
<0ifa ag and dL
0f aR. and
(152)
dx
x-xg
L(x)) - L(xR) 0 i < ac and L(x)) L(xx)
50 ac.
(153)
where L og and ac given in (88) (50). and 49) respectively.
Furthermore, the following are true and help determine from which row in Table to read x. If 2/2 < min (2/11, 1/11 1}, then an ac ar. 1f min 1), then aR < ac ar- Wi+ + +1, then 01 = ac = ag. In particular, it follows from this that if if 2 Br. then
2/2 = m2n////11 1,11 aR S ac at and if 1/2 S B3, then at ac aR.
Finally, or,, aRR ac E 10, 13.
Proof. The derivation of (146) 150 follows from direct substitution of x = Xt or x XR into (for which we have expressions from Theorems (nd or its derivative (in eq. (14 [45 ). The derivation [5]] 153) follows from the observation that the equations (146)- 150) are linear in a, and hence we can easily compute the values of a at which these expressions change from negative value to a positive value. Once an explicit formula for a', ac, and ag is obtained, it is easy to find the criteria to decide their relative magnitude by comparing the term under parenthesis in the denominators of (48). (50). and (49). It is also easy to see from their formulas that their value is always in the range [0, 11.
To finish the proof of Theorem 9 we consider the different scenarios in Table I In what follows, statements about the concavity of are justified via the explanation accompanying Figure 3 and statements about the slope of I. are based on Lemma M.13
Case 1.1, Wir < 122 222 2 B1 A a < at a ag: The function convex and is decreasing at x xz and decreasing at XR. Hence its minimum is at XR.
Case 1.2, 1/1 4/2 A d2 2 B1 A UR < a < ar; The function L is convex and it is decreasing at x xz. and increasing
.R- Hence it has unique minimizer at
When di </2/2 A 4/2 2 B1, we can use Lemma M.13 and a tedious calculation (omitted) to show that dR aa, which is why the 4th and 5th rows of the first column of Table I are empty. A simpler way to see that the 4th and 5th rows of the first column of Table must be empty is as follows. Since di < 1/2 A $22 2 Bi then a > aL and a < aR (i.e. E, holds) then by Lemma MM.3 we know that L is increasing at x = X and decreasing at x XR. but this is impossible for convex function.
know (from the argument following with Figure 33 that L. is convex. If
Case 1.3, 11 < 1/2 A 2/2 2 B1 A a > a1 A a > dgg: The function L is convex and it is increasing at both xz. and .R. Hence its minimum at XL.
31

---

Published as a conference paper at ICLR 2023
Case 1.4, 1 < 4/2 B2 < 1/ < A ag: The function L is first convex, then concave and then convex. It is decreasing at both x = xy and at x = Xg- Hence L has at most one local minimum in the interior of the domain, at = X1 if it exists, and a local minimum at Xg. the domain being XR]. Therefore, the minimum can be expressed as XR X1-
Case 1.5, 1/1 and then convex. It is decreasing at x X7, and increasing at = xg- Hence L has no local minimum the end points of the domain [R.. Also, L either has exactly one local minimum in the interior of the domain, at = X1, or, L has exactly two local minimum and one local maximum (resp.) in the interior of the domain, at x x1, x = X3 and x x2 respectively. Therefore, the minimum can be expressed as X3. Note that x1 always exists but X3 might not.
1/2 B2 < 1/2 B1 og
o1: The function L is first convex, then concave
Case 1.6, i1
4/22 B2 < 4/2 <B 0L <a a aR: The function is first convex, then concave and then convex. It is increasing at x xz and decreasing at = XR. Hence, the minimum is either at the .y, or xg. depending whether a > ac or a < ac. This case is an example where is clear that allowing ac leads to non-uniqueness in the optimal See Remark 9
Case 1.7, 1 < 1/22 A B2 < 1/2 < Bi A > dr Aa > ax: The function L is first convex, then concave, xR and x Xt., Hence I. either has no critical point
and then convex. It is increasing at both in the interior of the domain, or it has two critical point the interior of the domain, at x X1 (local maximum) and x x2 (local minimum) if they exists, and always has local minimum at XL- Therefore, the minimum can be expressed as xL X2. Note that x always exists, but x2 not always exists.
Case 1.8, 11 < 1/2 A B3 < 1/2 S B2 A a < aL A a < ag: The function L is first concave and convex. and is decreasing at both x = and xg. Hence its minimum is at Xg-
Case 1.9, 1/1 < 1/2 A B3 < Φ/ S B2 A ag < a < al: The function is first concave and convex. It is decreasing x xz. and increasing interior of the domain, which is at = x1 and always exists, and which is also a global minimum.
XR. Hence, L. has exactly one local minimum in the
Case 1.10, 1 4/2 A B3 1/2 S B2 Aa < ag: The function L is first concave and convex. It is increasing at x x1. and decreasing at = xR. Hence, the minimum is either at the x,, or XR. depending whether a ac o <cc.
Case 1.11, V1 < 1/2 AB < 1/2 S B2 A > 01 A > ag: The function /. is first concave and convex. It is increasing both x XL and x XR. Hence L either has no critical point in the interior of the domain or it has two critical point in the interior of the domain, at x = x1 (local maximum) and x X2 (local minimum) if they exists, and always has local minimum xz. Therefore, the minimum can be expressed as XL L X2. Note that XL always exists, but x2 not always exists.
Case 1.12, 1 2/2 1/2 S B3 A < aL A ag: The function L is concave. It is decreasing at both x = xy. and x XR. Hence. its minimum is =XR
When 1/1 < d/2 A 222 s fs. Lemma M.13 and tedious calculation (omitted) shows that that a' < a'R. which is why the 2nd and 3rd rows of the last column of Table [ are empty. A simpler way to see that the 2nd and 3rd rows of the last column of Table [ must be empty is as follows. Since d/ < 1/2 A 1/2 S A3 we know (from the argument following Figure 3) that L is concave. If a', and a dR (i.e. Eg holds) then by Lemma M.13 we known that is decreasing at x = x1. and increasing at Xg. but this is impossible for concave function.
Case 1.13, 1 22 A U2 S B3 A ag < < agt The function L is concave. is increasing at = XL and decreasing x .g. Hence, the minimum is either at the xL or XR. depending whether > ac or a < ac.
Case 1.14, 11 2/2 A 2/2 f3 A x = XL and at x = XR- Hence, the minimum is at.
a1 A ax: The function L is concave. It is increasing at
Case 2, +1 ج2=
The case when / 1 can be proved by taking appropriate limits of the case when 1/2 # 1, For now, assume that 1/2 # 1.
32

---

Published as a conference paper at ICLR 2023
We first prove that the second derivative of L is convex, just like in the case when di < 4/2 A direct computation yields
LLL dx2
2F7er
-(x)+ C, where C
(154)
111 1 42
22 11 (F700))))) (1x+
and L(x)=
A tedious calculation (omitted) shows that dr 2 0 for E [RL.xR] (i.e. it is convex), that L(xz)= < [(xx), ). and that de = xx.) < O. To do this calculation, we recommend the following. First break into two components. One component proportional to F7, called L1, and one component proportional to (F2 r"), called 7., Then, show that both components convex, that (x1. (XR), that Li(x)) < Li(xR), that dL
di dx (x = x1.) = O, and that ينه dx (x (x=xx,] x1.) < O.
From this follows that, depending on the value of v/, the concavity dxf is positive or negative. The situation is exactly the same as in the Figure 3 but now the axis is v1, the points A1, A2 and A are different, and so are the definitions of Bi. B2 and B3. We do however have that, by definition, 0 s B3 B2 B1.
d1
With a slight abuse of notation we refer to the y-coordinate value of this points by AI, A2. and A3. We 2 max
now have A₁ 2 ((="0=++)00++++) and A3 =
(33++= min )+mmxx
de
(12-1)² min(1.02)
Notice that when 2/2 = we have that A3 +0o, and in fact we also have L(xR) +oo. Getting A2 is bit more complicated. From the first order condition df 0 and the convex- ity of L recall that L a rational function we can extract that the x-coordinate of A is the unique root of 4th degree polynomial h(x) = ho + hix + h2x² + ha82 + h4x* in the range x E NRl, where ho 2 (p( 1)2 + 20122 + 1)). h1 24/2 (p(tb/2 - 1)2 + (31//2 + 1)), h2 61/2. h3 = 2 - p(12 1)), h4 = -p. Call this root XAx- We then have A [(xA,).
turns
out that we can write A2 directly as the solution of g(A2/((T² + Fl)))) = O. where g(x) = go g0 +gex* with go pt. 81 -4 (pv2 + + 1) (pvz (2p4/2 3p+ +2(p + 1)?). 82 = 44/ (pV2 (7pb22 - 20p+ + 14) + 7(p + 1)²). 83 = 166 (pv2 + p 1), and 84 = 16
Using the expressions for A and A3. and the expression for C, see 154 B2 and ß3 are detined as
B2 b : A1(h1)+ + (((1)) 00, and f3 = 4/1: A3(d1) C(+)) = O. By definition of β2 and B3. these equations have a unique solution when 1 > 4/2 0 and their expressions are given in 62 and (63) respectively. We can also define BJ as the solution of Bi 1 A2(w)) + C(W)) = 0. By definition of B1, the solution is unique in the range 1 > 4/2 0. We use the fact that A2 L(xA.) write
2FFa
that Bi 1/2 "(xa))* We can also use the fact that g(A2/((22 F2w2))
O, which implies that
g(-C(()) / ((T2 + +F 0 when 1 = B1, to write B1 as the root of a 4th degree polynomial r(x) that is specified Appendix I.4] which is the way in which we decide to state Theorem g
Now that we have characterized the curvature of L(x), we are ready to locate its global minimum. To do so, we will use the curvature of L(x) together with the first-order optimally condition dl. O, and the following three extra pieces of information: the sign of the derivative of L(x) at xz;; the sign of the derivative of L(x) at x xR; and the sign of L(xL) - L(xg).
dx
direct computation yields
dl. Po + PIX + p2x² + p3x² + pax* + psx
(155)
dr
(v2 (x + 1/2 22 -22
where the coefficients po. Ps are, apart from a multiplying constant, given in 77)
75 The
roots of the denominator, i.e. Vw - 1/2 and vib 2/2, are not a root of the numerator, therefore, the first order optimalit conditions are p(x)= 0.
Not solutions of p(x) = minimize L(x). To locate the minimizer, we use the sign the derivative of L(x) x xz, the sign of the derivative of L(x) at xR; and the sign of L(x,.) L(xR). These signs can be determined using Lemma M.14 Lemma M.14 proves Remark 11
33

---

Published as a conference paper at ICLR 2023
Lemma M.14. 11 1/2 then the following relationships hold.
dL
(F2+T2) + (ar (-1/2) +2(0-1))
(156)
dx
x-xx
dL
1/222 then
+00.
(157)
dx I=ER
1/ < 1 then
(158)
dL
2 (et==(a(+t))x++2/// (F2+T") ( +F7 (U2-1)² (2aw1
(159)
dx x==
(V1-422 (#2-1)2
4/2 > 1 then
(160)
dL
F?
(W2
+00 (F2+T?)
(161)
dx s=ER
(w2 (1/-v(1)
4/2 then L(XL) L(xR) -00.
(162)
1/2 < then
(163)
L(x,)- L(XR)= 1/2 (Fi (12-1) to (() (F(+r))
(164)
(01-42) (12-1)
1f 1 then
(165)
L(x,)) - L(xR)=
(166)
1/2 ((a- (F2+TP) +or +2t +hh ((2x-1) (1/2-1) (12-1) (12-4/1)
(12-1))+(+++) (20=-))(((/2-1)+// ( -a
(167)
Also, the following is true.
If az then dL
dL
O; and if 0z then
0.
(168)
dx X=XI.
dx X=XI
dL
DL
Let 1/2 $ 1. Ei is true then
<0; and if Eg is true then
> 0.
(169)
dx 1x=NR
dx x-xXR
Conditions En and Ez are defined in Theorem
Let t/2 # 1. If < ac then L(x1) - L(xx) > 0; and if a 2 ac then L(x)) - -(xx) s 0 (170)
Constant ac is defined in equation (65 in Theorem 9
Furthermore, we always have that at E [0. 1]. It also holds that ac [0, 1] if and only if v1 s v2/(1 p|1 - vzl) when O < S We have that [0, if and only if
Tw2-1| or v1 2 42/(1 p|1 v2l) when p 2 Ww-
V1 S $2 + p 1)2 (1/ 1) and
(171)
v1 -1 -1+ 1)2(2//2 minn 1, #2(2 max( 422))
(172)
2(max 2/, 1) + 2 -1)a)
Finally, A 2 B always, where A and B are given in 67 and 68 Furthermore, B 22 if and only 1pp > min(1, max (0, 20/2 1}}.
Proof. Except [622 and (57). the derivation of (156) (66) follows from direct substitution of XL XR into L- for which we have expressions from Theorems 1 and 4 or its derivative in
equation 155
Equation 162), for when 1/2 1. is obtained by taking the limit of (164 and (167) as d/2 1 and 1/2 1 respectively. Equation (157) for when 1/2 = is obtained by taking the limit [19) and (16T 1/2 and //2 J. respectively.
34

---

Published as a conference paper at ICLR 2023
The derivation of condition (168) follows from the observation that the equation (156) is linear in a and is always negative for a = O and positive for a = 1. Hence, we can easily compute a value at E [0, I] which the expression changes from negative value to positive value. The expression for oz we obtain is (64)
The derivation of condition (669) can be obtained through following the observations. First notice that dx Xx=x is a linear increasing function of a. Now focus on the following three implications.
1. If at a = we have dl
< O, then
dL de XxxxR < O for all o [0, 1];
dx x-xxR
2. If at a = 0 we have dx
di
x-xx
O, then
dL dx
Xx-xR
0 for all a [0, 1];
3. If at 0 we have dr
AL
Ia=xe < 0 and at I we have
dL är x=xx O, then there exists
oR E [0, 1] such that (a < or dx x= < 0) and (ar > ar dx x= > 0);
direct computation shows that the sufficient condition in the first implication holds if and only d/ < B, where B is given in (68 , the sufficient condition in the second implication holds if and only if
#1 > A, where A is given in 667) : the sufficient condition in the the third implication holds if and only
if B 1/ < A. Therefore, if Ej (d/1 < B) ((a aRR) (B 1 < A)) is true, we can use the first or third implication conclude that dx xx-xg < O. Also, if E2 (1/1 > A)v((a aRR)((B < 5 A)) true, we can use the second or third implication conclude that dx |E=ER > O.
dl
A direct calculation shows that A 2 B and that B < 4/2 if and only if 1/p A min I. max 2 1)). A direct calculation also shows that ar E [0, 1] and only if the conditions in 171 and (72) hold.
Condition (170) can be obtained through following the observations. First, notice that both (I64) and (167) are linear decreasing functions of a. Second, when 1 we always have [(xz)- [(xx) < 0. Therefore, there exists ac 1 such that (ar < ac = I(x1) [(xR)= 0) and (a ac = L(xz) L(xR) 0)). The expression for ac is given by 665 From this expression, a direct 1
calculation shows that ac 2 0 if and only if 1/ s 1/2((1 - p| (/l)) when < < W1-11 or
$1 2 122(1 - pp1 - 4/2)) when 2 102-11"
To finish the proof of Theorem 9 for 1 > l/2 we consider the different scenarios in Table 1 These studied via cases that exactly the same the Case 1.1 Case 1.14 for 1/1 < 1// but with < aR replaced by Ei and > aR replaced by Eg because when 1 > 6 it is E and Eg that determine the sign of dL
क 1x=x-- For example, for the top left-most cell in Table both when 1/ < 1/2 or //1 2/2 have that L convex and its decreasing at x7, and XR. its minimum is at xR- As another example, the 4th and 5th rows of the first column are not possible for exactly the same reasons as when 1/1 < 2/2. Namely, when B1 < & = d/ then L. is convex. If a > 011 and Ej holds, then by Lemma M.14 we know that L is increasing x x and decreasing at x Xg. which is impossible for a convex function. Similarly, the 2nd and 3rd rows of the last column are not possible because when V 1 S f3 then L is concave and if a < az A Ez then Lemma M.14 tells us that L is decreasing at = X2 and increasing at x = XR which is not possible. We omit repeating the arguments for Case 1.2 to Case 1.14.
Above, for both vi1 d2 and V > 1/2 # Table ! was derived using the fact that E₁ holding implies that the derivative of L at x XR is negative and Eg holding implies that the derivative of at x = XR positive. It was also derived using the fact that < ac implies that L(xz) > L(xR) and that a > ac implies that L(x,)) < L(xR). When 1/2 = 1, from Lemma M.14 we know that the derivative of L at x = XR is t00, and that L(xI.) < L(xR). Hence we can keep Table for t/ > 1/2 = I
unchanged if in this case we set E, to be false, Eg to be true, and d' -o0
M.6 PROOF OF THEOREM 10
This proof involves heavy algebraic computations. To aid the reader, this paper is accompa- nied by a Mathemetica file that symbolically checks the equations both in the theorem state- ment as well in the proof below. This file is in the supplementary zip file, well as
35

---

Published as a conference paper at ICLR 2023
in the following Github link Run.deercchiekkrrooffffTooooeee
AF It is called
Proof of Theorem 10 The proof amounts to a long calculus exercise, which we shorten by some careful observations.
We first notice that ER; and SR. can both be written function of w22 = cu2(122 A, noi Mi 42), and we can use this reduce the optimization problem 22 to an optimization problem over just one variable.
The variable w2 is function of μuo. M), M4 2 O, which we want to optimize, and has range [-00, 0], the value -co being achieved when u²= = μ22 2 μ O.
To avoid having deal with infinities, we make use of the Mobius transformation instead work with
1te wu-1
and
we substitute we confirm that 24 is satisfied.
Itwn into the left hand side 24 and substitute
32) in the resulting expression
-1+m
Itwn and 32 to write x as a function of μoo Ml, μ2, we can use the fact Furthermore, if we use x = -I+ws
that μo: #1, μ1 2 0, to conclude that x E min
2//2]]-
Our problem is thus equivalent to solving mi +aSR, subject min, I, -1+2/2)1 Once we know any μoo M1 M1-M2 n22 that satisfies (24) will be minimizer.
R: and observe that this is rational function of x. The numerator is, apart from multiplying constant, p(x), and the denominator is zero if and only if +
At this point we compute dx [(1 aa) +oSo
x = 2V or 2 2 Both are outside the range of x unless 1/2 x When 1/2 the 1 zeros of the denominator only cancel zeros of the numerator if F. 0. In the remainder of the proof we will assume that r2 + F > O. The optimal AFs' parameters when r = F. = can be obtained as limit when T, F. - O. Since the zeros of the numerator and of the denominator never cancel out (assuming r² + F > 0), all of the critical points are given by p(x) =.
Now we compute the value of the derivative at the extremes of the range of namely, x =-1,, 1, or -1 + 24/2. The value the derivative x = -1 is F- a) < O. which implies that x = is not a minimizer. The value of the derivative at. 1 is aF? -1
(2 0, and converges to when
2/22 which implies that 1 is not minimizer. The value of the derivative at = 24/2 F2+r²
is aFF (d2-1)2 > O, and converges to when 1/2 1, which implies that -1 24/2 is not minimizer. Another way to see that neither x nor x 1 + 2//2 will be a solution is to see that these choices will not satisfy the equation in (24) unless O, which never happens in this regime. This calculation implics that we can assume that x (-1, min (1, -1 2d2)), which we will assume from now
Finally, we show that the objective is convex in the domain of x, which implies that there only one critical point that is p(x)= 0 has only solution in the domain (-1, min -1+ 24/2)) and that this critical point is global minimum. To show that the objective is convex, we compute its second derivative, which is
81//2 (F? (4/2 W2(3(x 2)x 5) 5)-x² 3x +) (K2 + (4 + 3(x 1)2))
(173)
(4th (x 1)2)
[4
The minimum of denominator for [-1,
2//2] is
[-4(12 1 1) 4/2
which is always negatega,ive, and is zero only x or x =1 2/2, which have already been
excluded because they are not minimizers. Hence, for x e (-1, min (1, -1 22/2)) )), the denominator is strictly positive.
36

---

Published as a conference paper at ICLR 2023
To show that the numerator is non-negative, we only need to show that 4v2 + 4/2 - 2)x - 5)
x² 3x + 2 in the range of x. The minimum of 4v2 + 4 2)x -)- + 3x + for
44//2 - 1)² 1/2 >
x E [-1, min 2 is
which is always non-negative.
44(/22 - 1) ,0 s 2 s 1,
M.7 PROOF OF THEOREM
This proof involves heavy algebraic computations. To aid the reader, this paper is accompa- nied by a Mathemetica file that symbolically checks the equations both in the theorem state- ment as well as the proof below. This file in supplementary zip file, as well as in the following Github link /tttps:/ggttann com com/Teefaaassg88//RR AF It is called hunkeeTocheekkrroffffoooooo
Proof of Theorem Similar to proof of Theorem the majority of the proof is long calculus exercise.
We first notice that &gg and SR: can both be written as function w and z².
The variable w a function of poo M2- 2 and has range [-co, 0], the value -oo being achieved when 2 #22 / - /= = 0.
To avoid having to deal with infinities, we make use of the Mobius transformation.
ou-1 and
Iten
instead work with If we use wn-1 and 335 write x as function of μoo M1, the fact that μoo nn, μ22 2 0, conclude that E [-1, (1, 2 }]-
M2, M2, we can
Our problem is thus equivalent to solving ( (1-a)88 and z² 2 0.
Rg +a R; subject xo E [-1, (1,n=111+441)
Let I. = (1 - & + aSS R," With a direct calculation we can check the following. The derivative dx x---1 is always negative (recall we are assuming a < 1) which implies that there no local minimum at -1 The derivatives dl
di Ix-1 and dL dx x+-11 are always positive (recall that we assuming 1 > 0 in addition a < 1), which implies that there is local minimum at either x= 1 or = -1 + 14/1 Therefore, we know that the minimizer has E (-1, min 11-1 2413)) For x E (-1, min 1, 1)) the derivative dzz 122=0 is always negative (when or < 1), which implies that there is no local minimum at 2² = O. We thus know that the minimizer of is the interior of the domain for x and g2 and hence it can be found via VL_ 0, where the gradient is with respect and 2
d/.
The remainder of the proof considers few different cases depending on the value of a and 1/1
Case when a = 0:
In this case = E and dL 1 J ((xx1)))-41) The only way that d( 0 is if (2 _ 0a (we
already know that x 1), which corresponds to μxx 0.
As we noted in the beginning, L is a function of W and g², and since w) is function g² and μf and 2 is function of 2 and 22, we know that L is function of 2î and p². We express L in these variables and compute dL when μ* - We get that d(p)))
2F7
dL d(u
(174)
(247 (1 - n2) + ? (2 (++1 +
By minimizing the denominator with respect to μn 2 0, we conclude that its minimum is x2W? > which implies that dl < O, which implies that to achieve the minimum L one must have - co.
dyr)) In this case, we express L as a function of μI and μ. and take μ - oo and μ - 0, we get - F?.
37

---

Published as a conference paper at ICLR 2023
Case when 1 1 A a a
dr In this case diz and > which corresponds to μ =.
(xx
[x- 1x=33x+ The only way that dr. d(2
= 0 is if g2 (recall that x # 1, a <
As we noted in the beginning, L is a function of wn and 52, and since wn is function &² and μf and ? is function of un and nn we know that L is function of 2t and μº. We express L in these variables and compute _L__ when μx d(pp)
We get that
2F
4xa((+4pp)
(V
dl.
(175)
d(r))
(1 (d 4x²)) 3/2
By maximizing the numerator with respect to of 2 0, we conclude that its value always strictly smaller than 2F +4a) z 0 for any finite μl. Hence, dL O, which implies that the minimum diur))
is achieved only when μN - co. In this case, if we express L as a function of and and take #1 and u
get L aFF (1 R.
Case when 1
<<
This case is very similar to the previous case. The only difference being that, because 1 < a < when we solve
2F
4ad(1+44²)
[va(A+api))
dL
0,
(176)
d
(1 + 4x²)) 3/2
we now get two possible solutions, namely,
n 14a 3xd + (-va) A -4a2 + 3ad Vad
(177)
16a - 8a++
16a - 8a +
First notice that if A = O, both expressions give μu 0. Let us assume now that > 0. If we maximize the first expression with respect to 4 < a < 1, we conclude that its value is always smaller than -((22)/16) < O, which implies that it is not valid solution in the range 2² 2 0. If we minimize conclude that its value is always non-negative, which implies it is a valid solution in the range i 0. We therefore conclude that the second expression is the only stationary point in the range 2² 2 whether A = or not.
the second expression with respect to 4
Given that this is the only stationary point of L in the range #? 2 0, and given that the derivative dL 0 at μn 0 (which can be checked via substitution), conclude that the critical point must Kig)
be a global minimum.
we substitute the optimal values for μ³ and μ² 0 in L. we get L = (4vā 3aa) 2
Case when v11 # 1:
(a- (0x1)) As before, we start from knowing that the minimizer cannot be at In this case d (401-(+))))
the boundary of the domain. Therefore, since # 1, the only way that dL corresponds to μ4
is 2 co, which a
1twr into the left hand side of the last equality in 25 namely, , + 24h1 If substitute x - x)(-1 2 x), and let μ+ 0, we get O, which confirms the condition when 1/1
38

---

Published as a conference paper at ICLR 2023
We take < + in L to obtain,
4/ 1)2
L F1
41/1 - (x + 1)2 ax - (ar 1)F,?
(178)
dL
a 401(x 1)(2/111 - -x- 1)
Fi2
(179)
dr
((x + 112 -401)
LLL dy2
8F (416) + 13((((1 22xx 5) +x+
(180)
(4th (x 1)2)s
If we minimize d- over x E [-1, min(1, + 24) and 1 2 0, we obtain F//8 > O. This shows that our objective L. is strictly convex in the range x [-1, min(1, 2//1)) and hence there is only one solution
dL- 0.
dx
The rational function dL has a denominator which is zero only if = -1 2 or -11x==1-0 2 de
both of which are outside the valid range for x. Hence the unique solution to d/. äx = 0 comes from the zeros of the numerator of dL dr This numerator is (a constant times) polynomial in x whose coefficients are described in Theorem
N EXPERIMENT ON A REAL DATASET
is tempting to extrapolate our theory to practice. The scope of validity of our claims is rigorously stated in our theorems' assumptions and one should be cautions not claim their applicability beyond this scope. In particular, we are not attempting to improve on existing empirical techniques to design AFs but rather seek better understanding of already popular model, the RFR model. Namely, we want to understand the effect that using optimal AFs has on the RFR model. Within the context of designing good, or optimal, AFs for practical settings with empirical/heurritic methods we refer the reader to Section C Nonetheless, here we test some of our more general conclusions on real data. This appendix is referenced in the main text in Section 3.. this section, the data, and the fact that we do not work with infinite dimensions, are the only deviations from our theoretical setup. In particular, we work with an RFR model.
We use the MNIST data Deng (2012) to train an RFR model that approximates a function f. our ground truth object, defined as follows. For a given digit image x with class c E {0. I,..., 9}, define f(x) -5 c/9. Note that in the RFR model classification. The MNIST data set has input dimensions d = 28 x 28 784. For the test set we use 10000 random samples.
working with regressions, not
In Figure 4 we plot the test error & has a function of v 11//22 = N/n when we have n = 4000 train samples and when the number of features N ranges from to 14250. Training is done with 2 10 We do so in three different settings: (1) the AF is a fixed linear function; (2) the AF a fixed ReLU; (3) the AF is numerically optimized linear function. This AF is optimized as follows. For each value of tn /U2, we run a Bayesian optimization subroutine that minimizes the test eиror across all possible linear AFs. We note that, despite the fact that with linear AF our model linear, optimizing the test егror via linear AFs is different from optimizing the weights in the second layer during training. In this third setting, for each value of /1/22, we are working with a different AF, which why we use the set notation { around o in Figure
We observe that we see double descent curve phenomenon also for MNIST. This was previously known Belkin et al. (2019a), as it was also previously known that double descent curves appear for more complex data sets and neural architectures. e.g. Nakkiran et al. (02T). Unlike for the RFR theory, the interpolation threshold is not at /1///2 setting, and consistently with what we stated in our main observations for our theoretical setting, using different AFs affects the double descent curve phenomenon. In particular, using linear optimal AFs (one for each / v1/42) can beat using a single ReLU function and seems to destroy the double descent curve phenomenon.
but it around v /1/22 2. In this practical
The code to produce Figure is in the following Github link: https: /tt::://gtttubbuu com/ Jef Fwang87/RFR_ AF This code is also available in the supplementary zip file provided. To
39

---

Published as a conference paper at ICLR 2023
107
Test error. 8
10
Fixed linear
10
Flixed Rel
10"1
of Pos
optimizee
/
Figure 4: Learning a function from the MNIST data also produces double descent curve, i.e. the eтror decreases as model's complexity increases, then increases until the interpolation threshold, which around // 1/222 = 2, and then decreases against past the interpolation threshold. By optimizing the AF this phenomenon disappears. The meaning of this figure is related to the meaning of Figure I (A) in the main text.
generate the plot the file named 2020b. We ran it using a MacBook Pro with 2.6 GHz 6-Core Intel Core i7 and 32 GB 2667 MHz DDR4. In this machine it takes about 10 hours run.
4. It runs using Matlab
In Figure 5 we plot the test error & has a function of when 1/2 10, when we have = 12d train samples, and when the number of features is very large, namely, N 10000. We do in two different settings: (1) the AF is a fixed ReLU; (2) the AF is numerically optimized quadratic function. This AF optimized as follows. For each value d, we run a Bayesian optimization subroutine that minimizes the test error across all possible quadratic AFs.
0.07
0.06
Test Test error,
0.05
0.04
Fixed ReLU
0.03
optimized
0.02
0
-2
-1.5
-0.5
12)
Figure 5: Learning a function from the MNIST data set using the RFR model can be improved by selecting the appropriate ridge regularization parameter A, around 10 1 plot. we are careful about choice, but instead we use an optimized AF, we can achieve similarly good performance. The meaning of this figure related to the meaning of Figure (C) in the main text.
We observe that choosing optimized AF and being "careless" about the choice of regularization leads to as good results as using a ReLU and optimizing 1, which the common practice.
The code to produce Figure 5 is in the following Github link: https: httpbbtttb......////g com/ Jeffwang87/Rel AF This code is also available in the supplementary zip file provided. To generate the plot run the file named RunMeToGGneraten gure_5 It runs using Matlab
40

---

Published as a conference paper at ICLR 2023
2020b. We ran it using a MacBook Pro with 2.6 GHz 6-Core Intel Core i7 and 32 GB 2667 MHz DDR4. In this machine it takes about 3 hours to run.
O EXPERIMENTAL RESULTS FOR DIFFERENT RANDOM FEATURES INITIALIZATION
Our results assume that the features in the RFR model sampled i..d. uniform on the (d 1)- dimensional sphere of radius Vd.
In this section, we numerically examine two other initializations of lead to similar, or different, asymptotic mean squared test error. Specifically, initialize O with either Xavier initialization (Glorot & Bengio, 2010) or Kaiming initialization (He et al. 2015), and compare the resulting error curve (L when 0) with the curve for the original initialization for the three different regimes in our paper.
If the new error curves agree with the ones for the original initialization for some regime, we take that as evidence that our conclusion might hold for these initializations and that regime as well.
In Figure (A) and (D), we that in regime I and when a O, there is a agreement between the three initializations. However, this is not the case for regimes (Plot (B) and (E)) or 3 (Plot (C) and (F)). In regime 3, is unclear if Xavier and Kaiming initialization agree for large values of A.
(A)
(B)
(C)
10
4.0
4.0
Fl
Durae: cane
== VO.5
F1
VO.5
Mcsn segteedeett caroe.
3.5
3.5
8
3.0
3.0
01
F6 =
A2 3
Fe
v0.5
- 3
F+
v0.5
de
A D.I
2.5
2.5
7 V0.3
A A-40
Mesn squndd
2.0
Menn squand
2.0
1.5
1.5
1.0
1.0
0.5
-3
-2
0
-2
# 1//22
log 2
log
(D)
(E)
(F)
Fl
8-
d 200
Moin squane kst eno
3.5
6-
Mei squared lot
2
T=1
F1
4-
V1 -
Monn
Fx
V/2 -
2
0.1
1.0
F. =
02 - 200
2 0.1
0.5
0.0
0
-4
-4
-2 -1
1
#1/42
Ing
Figure 6: Plot (A), (B), and (C) are generated under the condition when F1 1, d 200, F. = vO.5, and T V0.5. Plot (D), (E), and (F) are generated under the condition when F, 1, 200, F. = 1, and r 1. (A) shows the error curve for regime (ridgeless-limin regime) when A - 0 and 1/2 = 3. (B) shows the error curve for regime 2 (over-parametee parameterrzee regime) when d/ 100, 2/2 3, and 2 = 0.1.6 (C) shows the error curve for regime 3 (large-sample regime) when /1 3, //2 = 100, and 0.1. (D) shows the error curve for regime (ridgeless- regime) when regime) when 1/ 200, 3 2, and 2 0.1. (F) shows the error curve for regime 3 (large-sample regime) when V1= 2, 2/2 200, and = 0.
and 2/2 5. (E) shows the error curve for regime (over-panc nover-parameterized
41


Reviews:
[{"review_id": "t2b-3MjMwR", "reviewer": "Reviewer_1hhM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This submission studies the optimal activation function in a two-layer random features model that minimizes a weighted sum of the test error and the model sensitivity measured by a Sobolev norm. The analysis assumes the proportional limit and spherical data; in this setting both the test error and the sensitivity have been analytically derived in prior works. Using these analytic formulae, the authors presented a few cases where the optimal activation can be either linear or nonlinear. ", "summary_of_the_review": "In my opinion this submission requires some major revision to be relevant to the ICLR community. Hence I cannot recommend acceptance. \nI am willing to update my evaluation if the authors can address my concerns and elaborate on the motivation / importance of the studied problem. ", "strength_and_weaknesses": "## Strength\n\nThis paper contributes to the growing literature on the asymptotics of random features regression. Unlike most prior works that focused on the shape of the risk curve (double descent), the current submission considers the design of optimal activation function, which is a new application of the precise error formulae. \n\n## Weaknesses\n\nMy main concern is on the motivation and implications of the analysis. \n\n1. Under the setting of [Mei and Montanari 2019], random features model in the proportional regime can only learn linear functions on the input. Specifically, the test error of the RF model only depends on the activation function through the first two Hermite coefficients, and is equivalent to that of a Gaussian linear model -- this is often refereed to as the Gaussian equivalence property [Hu and Lu 2020] [Loureiro et al. 2021] [Montanari and Saeed 2022]. \nConsequently, designing the activation function is equivalent to tuning the magnitude of Gaussian noise added to the features (this can be interpreted as implicit ridge regularization), which I do not find very meaningful because the resulting model cannot outperform linear regression on the input (see [Ba et al. 2022] Section 4). \n\n2. Given the Gaussian equivalence property, it is not surprising that the optimal activation function can be linear, which reduces the RF model to linear regression on the input in certain regimes. Similarly, due to the self-induced ridge regularization of the nonlinear activation function, it is intuitive that tuning the Hermite coefficients provides similar benefit as tuning $\\lambda$.  \n\n3. I also do not see the motivation of minimizing the sum of test error and sensitivity; this no doubt makes the computation more involved, but ultimately we are still designing noisy Gaussian linear models. It would be nice if the authors can outline an example where the deigned RF model achieves smaller loss + sensitivity than directly doing ridge regression on the input. Such result can provide some justification of the use of nonlinear random features. \n\n4. It is unclear how the analysis can benefit practitioners in choosing the activation function, since the optimal Hermite coefficients require knowledge of the target function and SNR, which is not known in practice. \n\nHu and Lu 2020. Universality laws for high-dimensional learning with random features.  \nLoureiro et al. 2021. Learning curves of generic features maps for realistic datasets with a teacher-student model.  \nMontanari and Saeed 2022. Universality of empirical risk minimization.   \nBa et al. 2022. High-dimensional asymptotics of feature learning: how one gradient step improves the representation.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "nGn_RePw40M", "reviewer": "Reviewer_X96N", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies random features ridge regression where the data $\\{(x_i, y_i)\\}_{i=1}^n$ is generated from a noisy nonlinear model $y_i=f_d(x_i)+\\epsilon_i$ with the covariates $x_i$ i.i.d. uniformly sampled from $\\mathbb{S}^{d-1}(\\sqrt{d})$. \n\nThe estimator is given by $f_{a,\\Theta}(x)=\\sum_{i=1}^{N}a_i\\sigma(\\langle\\theta_i, x\\rangle/\\sqrt{d})$ with $\\sigma$ being the activation function and $\\Theta\\in\\mathbb{R}^{N\\times d}$ with $i$th row $\\theta_i\\in\\mathbb{R}^d$ satisfying $||\\theta_i||=\\sqrt{d}$, where $\\theta_i$ is i.i.d. uniform on $\\mathbb{S}^{d-1}(\\sqrt{d})$. The authors aim at finding the optimal activation function $\\sigma$ in the asymptotic regime by minimizing a linear combination of the test error and sensitivity of the random features regression models.", "summary_of_the_review": "This work provides some interesting insights on the understanding of finding optimal activation functions in the random features regression models, which should be of interest to the ICLR community. However, I am not quite sure whether these theoretical findings can benefit the design of learning algorithms in practice, esspecially for the deep architecture case.", "strength_and_weaknesses": "$\\textbf{Strength}$\n\n1. This is a novel contribution that provides insights into the understanding of finding optimal activation functions for random features regression models in the asymptotic regime.\n\n2. This paper provides some interesting observations on the benefit of finding optimal activation functions (and figure out whether they are linear or nonlinear) from the theoretical perspective.\n\n3. Codes are provided.\n\n\n$\\textbf{Concerns}$\n\n1) How to use these theoretical findings in practice? e.g., how to choose $\\alpha$;\n\n2) How to combine the optimization problems (2) and (8)?\n\n3) The theoretical results only apply to shallow architecture, which may restrict their significance.\n\n4) All theorems in Section 3.1 are the special cases of Mei&Montanari (2022), which are essential for the main results in Sections 4.1 and 4.2. \n\nMinor typos:\n1) Below (23), Guass error should be Gauss error", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KMcSIYS-Lr", "reviewer": "Reviewer_riDW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work considers the problem of finding optimal activation functions for a random features regression setting under a performance vs. sensitivity trade-off. Under the same setup as in [Mei, Montanari '22] (spherical input data, linear target function + noise, Gaussian random features projection), the starting point of the analysis is the exact formula derived in [Mei, Montanari '22] for the asymptotic generalisation error of the model in the proportional regime.\n\nThe main new technical contribution is an exact asymptotic formula for the sensitivity (squared norm of the model gradient). Combining this with the asymptotic formula for the error allow the authors to study the optimal RF activation for the different regimes of interest by minimising a convex combination of the error and the sensitivity. In particular, the authors discuss when it is better to have a linear vs. non-linear activation, and how the optimal choice of activation compares with optimal cross-validation of the $\\ell_2$ penalty.", "summary_of_the_review": "Overall, although the discussion is novel and the sharp results derived from cumbersome algebra is impressive, I think this manuscript could be considerably improved. See the points raised above for some constructive suggestions.\n\n", "strength_and_weaknesses": "**Strengths**:\n\n- Given the cumbersome asymptotic formulas, getting sharp results for the optimal activation is a quite impressive *tour de force*.\n- The authors make an effort to connect their discussion to more realistic settings, despite leaving this to the Appendix F.\n\n**Weaknesses**:\n\n- The work strongly builds on previous theoretical results, with only small novel technical contributions.\n- The analysis is limited to ridge regression with Gaussian random features, despite the progress in the literature deriving similar asymptotic results for more general feature matrices, losses and regularisation.\n- The discussion is sometimes hard to follow, specially because of the heavy notation which requires the unfamiliar reader to go back and forth for the definitions.\n\n**Comments**:\n\n- **[C1]**: A drawback of this work is that it lacks a discussion of some important intuition underlying the key conclusions. For instance, I believe some of the results in this paper can be directly understood from Gaussian equivalence of random features in the proportional regime. For some context, Gaussian equivalence builds on early spectral universality results in the kernel regression literature [El Karoui '10; Pennington, Warah '17] and is an important ingredient for the derivation of the exact asymptotics in the regression case [Mei, Montanari '22], but it also allow one to extend the exact asymptotic analysis of the RFs model to other loss functions and projection matrices, as shown in [Gerace et al. '20; Goldt et al. '22] and later proven in [Hu, Lu '20].\n\nGaussian equivalence states that the asymptotic statistics of the random features estimator is equivalent to the asymptotic statistics of an equivalent Gaussian problem. Employing the notation in the paper, one way of writing is:\n$$\n\\sigma(\\Theta x_{i}) \\asymp \\mu_{0} 1 + \\mu_{1}\\Theta x_{i} + \\mu_{\\star} z_{i}\n$$\nwhere $z_{i} \\sim\\mathcal{N}(0,I_{N})$ is an uncorrelated noise. Therefore, the problem considered here is asymptotically equivalent to:\n$$\ny_{i} = f_{d}(x_{i})+\\rm{noise} = \\beta_{0} + \\langle\\beta_{1}, x_{i}\\rangle + \\rm{noise}\n$$\n$$\n\\hat{y} = f(x) = \\mu_{0}\\langle a, 1\\rangle + \\mu_{1} \\langle a, \\Theta x\\rangle + \\mu_{\\star}\\langle a, z\\rangle\n$$\nwhere in this regime the non-linear part of the target is also equivalent to additive mismatch noise. From the equivalent model perspective, it is clear that the random features is just introducing a model mismatch that hinders performance. Indeed, since the target is just a linear function in $\\mathbb{R}^{d}$, the optimal predictor would just do linear regression in this space, while the projection $\\Theta x\\in\\mathbb{R}^{N}$ is forcing the model to fit a linear function in $\\mathbb{R}^{N}$. From this characterisation, it is also clear how $\\mu_{\\star}$ plays the role of an effective regularisation $\\lambda$. However, since it also appears in the effective model mismatch noise this leads to the richer behaviour observed by the authors in Fig 1 (C) & (D).    \n\nI am not sure if the authors exploited this intuition, but I believe it would be very important to explicitly discuss it in the manuscript.\n\n- **[C2]**: One important aspect which is missing in the discussion is how much the conclusions depend on the target function. For instance, if the target function itself was given by a random features model with features $\\sigma_{\\star}(\\Theta x)\\in\\mathbb{R}^{N}$ for some activation $\\sigma_{\\star}$, it seems an optimal linear predictor would be obtained by matching the features $\\sigma=\\sigma_{\\star}$. Would this substantially change the conclusion?\n\n- **[C3]**: The heavy use of notation in the discussion can be confusing for the unfamiliar reader, who has to go back and forth to definitions in order to follow. Reminding the reader of what the different quantities mean over the discussion and the plots would be very helpful. For instance, here are some suggestions:\n  - In Fig. 1, instead of having in the x-axis $\\psi_{1}/\\psi_{2}$, one could write directly $N/n$ .\n  - Using $n/d$ and $N/d$ instead of $\\psi_1, \\psi_2$ could be helpful also during the discussion. Instead of $\\psi_{1}<\\psi_{2}$ one can say $N<n$. Of course, this is always understood asymptotically.\n  - Instead of saying \"In regime $R_2$\", one could be redundant and say \"In the highly overparametrised regime $\\psi_{2}\\to\\infty$\". Same for $\\alpha = 0$: \"minimising the error\" or $\\tau=0$: \"noiseless\".\n  - The whole notation in Table 1 is very hard to parse. Unfortunately I don't have a suggestion on how to improve it, but from the reader perspective one just skips it.\n\n- **[C4]**: A few comments concerning the related literature:\n\n  - The sensitivity has been studied in the closely related setting of kernel ridge regression in [Simon et al. '21], where a non-asymptotic formula for this quantity as a function of the kernel spectrum was derived. This should coincide with the expression here in the overparametrised regime $R_{2}$ which corresponds to the kernel limit of random features.\n\n  - In Sec. 3, point 4 the authors mention that:\n    > Existing proof techniques make it very hard yet to extend our type of analysis to more than two layers or complex architectures.\n\n    Although the authors are right that there are no rigorous multi-layer generalisations (except for not-so-interesting cases such as $\\mu_1 = 0$, c.f. [Pennington, Warah '17]), in [Goldt et al. '22, Loureiro et al. '21] it was empirically shown by comparing the learning curves that Gaussian equivalence holds in multi-layer cases, including in cases when the layers $\\Theta$ are pre-trained.\n\n\n**References**:\n\n[[El Karoui '10]](https://projecteuclid.org/journals/annals-of-statistics/volume-38/issue-1/The-spectrum-of-kernel-random-matrices/10.1214/08-AOS648.full) N El Karoui. *The spectrum of kernel random matrices*.  Ann. Statist. 38(1): 1-50 (February 2010). DOI: 10.1214/08-AOS648.\n\n[[Pennington, Warah '17]](https://papers.nips.cc/paper/2017/hash/0f3d014eead934bbdbacb62a01dc4831-Abstract.html). J Pennington, P Worah. *Nonlinear random matrix theory for deep learning*. Part of Advances in Neural Information Processing Systems 30 (NIPS 2017).\n\n[[Gerace et al. '20]](https://proceedings.mlr.press/v119/gerace20a.html) F Gerace, B Loureiro, F Krzakala, M Mézard, L Zdeborová, \"Generalisation error in learning with random features and the hidden manifold model\", Proceedings of the 37th International Conference on Machine Learning, PMLR 119:3452-3462, 2020.\n\n[[Goldt et al. '22]](https://proceedings.mlr.press/v145/goldt22a.html) S Goldt, B Loureiro, G Reeves, F Krzakala, M Mezard, L Zdeborova. *The Gaussian equivalence of generative models for learning with shallow neural networks*. Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, PMLR 145:426-471, 2022.\n\n[[Hu, Lu '20]](https://arxiv.org/abs/2009.07669): H Hu, YM Lu. *Universality Laws for High-Dimensional Learning with Random Features*. arXiv: 2009.07669 [cs.IT]\n\n[[Simon et al. '21]](https://arxiv.org/abs/2110.03922) JB Simon, M Dickens, D Karkada, MR DeWeese. *The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks*, arXiv: 2110.03922 [cs.LG]\n\n[[Loureiro et al. '21]](https://proceedings.neurips.cc/paper/2021/hash/9704a4fc48ae88598dcbdcdf57f3fdef-Abstract.html) B Loureiro, C Gerbelot, H Cui, S Goldt, F Krzakala, M Mezard, L Zdeborová. *Learning curves of generic features maps for realistic datasets with a teacher-student model*. Part of Advances in Neural Information Processing Systems 34 (NeurIPS 2021).\n\n**Small typos**:\n\n- Below eq. (23): *\"Guass\"* -> Gauss.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DUSXsBFQSLg", "reviewer": "Reviewer_7nWY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper designs optimal activation functions for the Random Feature Regression model: a special case of a two layer neural network. Here, consider a two-layer neural network with inputs of dimension $d$, a second layer of dimension $N$, and a single output node. The mapping from the input to the hidden layer is generated as a random matrix, passed through a nonlinearity function we can pick, and Ridge regression is used to learn a linear combination of the hidden layer parameters and predict the output value.\n\nThis paper studies proves what activation functions are optimal in various limits as the problem grows larger. \"Optimal\" is characterized in a variety of ways, like balancing mean squared error of the solution against the flatness of the optimization landscape, or by picking regularization criteria on the activation functions (so when there's many possible optimal activation functions, we still typically have a unique solution). The paper always studies the limit as $d \\rightarrow \\infty$, with analysis specialized to three cases:\n1. _Unregularized Case_: The limit as $d \\rightarrow \\infty$ and $\\lambda \\rightarrow 0$ (the regularization parameter), but $\\frac{d}{n}$ and $\\frac{d}{N}$ remain constant\n1. _Way Overparameterized Case_: The limit as $d \\rightarrow \\infty$ and $\\frac{d}{N} \\rightarrow 0$, but $\\frac{d}{n}$ and $\\lambda$ remain constant\n1. _Large Sample Complexity Case_: The limit as $d \\rightarrow \\infty$ and $\\frac{d}{n} \\rightarrow 0$, but $\\frac{d}{N}$ and $\\lambda$ remain constant\n\nIn all cases generated by all combinations of these parameters, exact characterizations of the optimal activation function are given. The details and notation get a bit laborious, but the theory provides a nice model for understanding the value of different activation functions. Like in the limit when we have a huge number of samples, we should just use a linear activation function, making the overall neural net linear. Or in showing that choosing the right activation function can completely avoid double descent, whereas the same data with a ReLU activation function would suffer from the spike in double descent.\n", "summary_of_the_review": "Nicely intuitive and very well written paper.\nI don't know how significant it is, since I don't especially work in this area.\nStill seems like it should be published imo.", "strength_and_weaknesses": "The paper is long, and the detailed math is....pedantic, but the key takeaways are really neat and the bulk of the math is buried in the appendix (as it should be).\n\n---\n\nLet me first note that I'm not an expert on anything in this paper, especially the deep learning theory literature. I can't really speak to novelty or significance, so I'll leave that to the other reviewers. I'll just give my impressions, as a relative outsider who can read a nice proof sketch and enjoy a good paper.\n\nThis paper was pretty fun to read. It's got a precise statistical model that's been used to study neural nets in the past. The paper's got really precise results on the shape of optimal activation function. The proofs are long, but the proof sketches in the body of the paper are short and sweet and clear. The paper's got really nifty implications of these optimal functions. These are the key strengths of the paper. I recommend publishing the paper.\n\nThis paper kinda feels like a shoe-in to get accepted. I only really see two potential weaknesses in this paper:\n1. The mathematical choice of norms and objective function and regularization and generative model are all very arbitrary. These are arbitrary, and the authors notes these are arbitrary but have some foundation in recent research (e.g. bottom of page 3, top of page 4; bottom of page 9). It's a theoretical exploration and these choice are arbitrary so they have to analyze _something_. It's a weakness, but not a serious one.\n1. There's no way for someone to review all of the math in the appendix in time. This is an issue with the broader peer review process for ML though. Not the fault of the paper in the slightest.\n\nThe paper is well written, intuition is regularly given, and for a paper with such mathematically precise results in so many different cases of analysis, the huge list of optimal activation functions is broken down in an impressively not-unapproachable way.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster