Learning Expressive Random Feature Models via Parametrized Activations

Jiansheng Yang; Yaodong Yang; Zailin Ma

REVIEW 5 major objections 5 minor 1 cited by

Learning Expressive Random Feature Models via Parametrized Activations

T0 review · 5 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Replacing the fixed activation of a random feature model with a learned sum of basis functions enlarges the representable function class and reaches O(ε) error with M = Θ(1/ε²) random features.

desk verdict Real theoretical contribution with a clean kernel formula and bounds, but the experimental section is outside the theory's regime and the paper overstates the connection. read the letter →

arxiv 2411.19468 v4 pith:ZI7C2EBE submitted 2024-11-29 cs.LG

Zailin Ma , Jiansheng Yang , Yaodong Yang This is my paper · ORCID

classification cs.LG MSC 68T0768Q32

keywords randomfeatureslearnableactivationfunctionsradialbasiskernelapproximationexcessriskgeneralizationboundstwo-layerneuralnetworks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Random feature models typically fix the activation function, which caps the functions they can represent. This paper introduces RFLAF, a random feature model whose activation is learned as a weighted sum of basis functions (radial basis functions, splines, or polynomials), and argues that this modest parametric change expands the represented function space without leaving the random feature framework. In the theory, a single RBF activation is shown to induce a kernel with an explicit closed form, and multiple RBFs are shown to approximate any Lipschitz, compactly supported activation. The paper proves that this model attains $O(\epsilon)$ mean approximation error and $O(\epsilon)$ excess risk with $M = \Theta(1/\epsilon^2)$ random features, a count that scales with the square root of the sample size up to logarithmic factors. On seven datasets, RFLAF with RBF or spline bases consistently beats fixed-activation random feature models, with RBFs about three times cheaper than splines.

What carries the argument

The central object is the parametrized model $\hat{f}(x) = \frac{1}{M}\sum_{m=1}^{M}\sum_{i=1}^{N} a_i B_i(w_m^\top x) v_m$, where the $B_i$ are basis functions with fixed centers and widths and the $a_i$ and $v_m$ are learned. The load-bearing identity is Theorem 3.1's closed form for the kernel induced by a single RBF activation, which yields a rotation-invariant Taylor expansion and an explicit feature map with rapidly decaying coefficients. The argument proceeds through the Gaussian universal approximation theorem to approximate any compactly supported Lipschitz activation by a weighted RBF sum, then through sub-Gaussian concentration bounds and Rademacher complexity to convert that approximation into finite-width and finite-sample guarantees.

What would settle it

Train RFLAF with $N = 16$ and $M = 1000$ on a synthetic target whose activation $\sigma$ is a narrow high-frequency oscillation on $[-2,2]$, and compare against the best fixed-activation random feature model; if RFLAF fails to match or beat that baseline, or if its excess risk does not decrease at the predicted $O(1/\sqrt{M})$ rate as $M$ grows, the claimed consistent superiority and the $M = e^{\Theta(\sqrt{n})}$ trade-off would be contradicted.

Watch

Extended reading notes

Core claim

The central claim is that learnable activations, not the random first layer, are the source of expressivity in random feature models. The paper derives the first closed-form kernel for a single RBF activation, $K(x,x') = \frac{h^2}{\sqrt{(h^2+\|x\|^2)(h^2+\|x'\|^2)-\langle x,x'\rangle^2}} \exp\left(-\frac{c^2}{2}\frac{(h^2+\|x\|^2)+(h^2+\|x'\|^2)-2\langle x,x'\rangle}{(h^2+\|x\|^2)(h^2+\|x'\|^2)-\langle x,x'\rangle^2}\right)$, and a rotation-invariant Taylor expansion whose coefficients are squares of explicitly defined polynomials. For the multi-RBF model, the approximation theorem gives $E_x|\hat{f}(x)-f^*(x)| \le 18(\|\sigma\|_\infty R+\epsilon)\sqrt{\log(4/\delta)}/\sqrt{M} + \epsilon$, and the generalization theorem bounds the excess risk by $\rho C \log(16/\delta)/(h\sqrt{n}) + \rho C \sqrt{\log(8/\delta)}/\sqrt{M} + \rho\epsilon$. With the RBF width chosen as $h = e^{-\Theta(1/\epsilon)}$, the required number of random features is $M = e^{\Theta(\sqrt{n})}$, matching the known feature-count scaling for standard random feature models. The paper concludes that a learnable activation component buys the extra expressivity, and it validates this transfer by unfreezing the first layer, where the resulting two-layer networks generally outperform plain MLPs and a KAN baseline on the tested datasets.

Load-bearing premise

The load-bearing premise is that the true data-generating activation function is well approximated by a small weighted collection of basis functions; the paper's theorems actually require that collection to grow exponentially as the error tolerance shrinks, while the experiments use only sixteen RBFs.

Editorial extensions

If this is right

RFLAF learns the data's effective activation by gradient descent, removing the need to hand-pick or grid-search the activation of a random feature model.
The theoretical feature count $M = e^{\Theta(\sqrt{n})}$ matches the known scaling results for standard random feature models, so the added expressivity does not worsen the sample-to-feature trade-off.
Because any universal approximation basis can replace RBFs, the learnable-activation mechanism transfers to spline, polynomial, and other random feature constructions.
Unfreezing the first layer turns RFLAF into a two-layer learnable activation network that the experiments show is competitive with or better than plain MLPs and a KAN baseline at a fraction of the cost.
The explicit single-RBF kernel formula invites spectral analysis of the induced kernel, which the paper identifies as the next step for understanding the model's inductive bias.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The experiments use $N = 16$ basis functions with $M$ between 1000 and 3000, while Proposition 4.1 asks for $N = e^{\Theta(1/\epsilon^2)}$; the empirical gains are therefore better read as evidence for a low-complexity regime that the paper's bounds do not yet cover.
The closed-form single-RBF kernel could be used to compute a Mercer expansion numerically, which would let practitioners compare RFLAF kernels with standard kernels and predict when the learnable activation helps.
The two-layer results suggest that a single learnable activation may be the minimal ingredient of a Kolmogorov-Arnold-style network needed to beat plain MLPs on standard tasks, and it is much cheaper than KAN's many learned univariate functions.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is worth a serious look. The theoretical core is genuinely new and internally coherent: an exact kernel formula for a single RBF activation, a representation theorem, approximation guarantees via Gaussian UAT, and a Rademacher-based excess risk bound that recovers the sharp M = Theta(sqrt(n)) scaling for random features. I checked the structure of the proofs, including the Riemann-sum argument, the concentration steps, and the Rademacher bound, and they are sound. The authors also cite the prior work on optimal activations (Wang and Bento, Demir and Dogan) and are explicit that their contribution is the specific construction and its analysis. That is honest scholarship.

The soft spot is exactly where the stress-test puts it: the experiments live an order of magnitude outside the theoretical regime. The theory needs h = Theta(epsilon) and N = Theta(M polylog) with M = Theta(1/epsilon^2); the experiments use N = 16, h = 0.25, and M = 1000-3000, which makes the Proposition 4.1 conditions force epsilon to be O(1). So the bounds in Theorem 4.2 are vacuous at the experimental settings. The paper itself concedes that a humble N works, but then Figure 1 is described as substantiating Proposition 4.1, which is exactly the overreach the stress-test flags. The only in-regime experiment (Section 6.3) uses indicator-function targets, which are not Lipschitz and fail the paper's own assumptions. There are also secondary issues: the constrained set in Eq. (9) involves constants (||sigma||_inf, R, |K|) that the learner does not know, while the implemented objective is the unconstrained nonconvex problem in Eq. (33); and the checklist claims code and training details that are not in the text. None of this refutes the theorems, but it splits the paper into two parts: a valid theoretical contribution and an unexplained empirical effect.

What the empirical gains actually come from is not isolated. The improvements are equally consistent with the RBF-mixture feature class, the implicit bias of the (||a||^2 - ||v||^2)^2 regularizer, or asymmetric baseline tuning. The paper does not claim more than 'consistently outperforms', and that claim is supported by the tables; the interpretation that learnable activation is the cause is not established.

My bottom line: the theory is a solid contribution to the random feature and kernel approximation literature and deserved a serious referee. The experimental section needs major revision: publish code, match compute, and either give in-regime experiments or explicitly state that the empirical gains are outside the theory's coverage. I would not cite it in my own work yet, but I would bring it to a reading group to discuss the kernel formula and the bounds.

Referee Report

5 major / 5 minor

Summary. The paper introduces Random Feature models with Learnable Activation Functions (RFLAF), where the activation is a weighted sum of basis functions (RBFs in the theory). It derives an analytic kernel for a single RBF activation, gives approximation bounds for multiple RBFs via the Gaussian universal approximation theorem, and proves excess-risk and sample-complexity guarantees showing that M = Theta(1/epsilon^2) random features and n scaling as eTheta(1/(epsilon^2 h^2)) suffice (with 1/h = eTheta(1/epsilon)). Experiments on seven datasets compare RFLAF with RBF, B-spline, and polynomial bases against fixed-activation random feature models, and also consider unfreezing the first layer for two-layer networks. The paper claims consistent empirical improvements and validates the learnable-activation mechanism.

Significance. The theoretical framework is a meaningful step: it provides a closed-form kernel for a single RBF activation (Theorem 3.1), a universal-approximation-based path from activation approximation to function approximation (Proposition 4.1 and Theorem 4.2), and Rademacher-complexity-based excess-risk bounds (Theorem 5.1). The proofs are detailed and the central derivation chain appears internally coherent. If the theory held for the demonstrated regime, the result would extend random feature methodology to learnable activations with quantitatively stated costs. The main weakness is that the experimental regime lies far outside the theory's validity conditions, and the implemented optimization problem is not the one analyzed in the generalization theorem, so the empirical claims are not currently backed by the paper's theoretical guarantees.

major comments (5)

[Section 6 vs. Proposition 4.1 (Appendix C.1, Eq. 29)] The experimental settings in Section 6 (grid range |K|=4, N=16, h=4/N=0.25, M=1000-3000) are far outside the regime required by Proposition 4.1. Substituting these values into the conditions of Eq. 29 forces epsilon to be O(1) (from the h-condition) and at least about 0.3 (from the grid-size condition), so Theorem 4.2's error bound is vacuous at those hyperparameters. Consequently, the statement in Section 6.2 that Figure 1 'substantiates Proposition 4.1' overreaches: in the tested regime the proposition's bound does not apply. The theoretical and empirical parts of the paper should be either reconciled by running in-regime experiments or explicitly separated, with claims of empirical support removed.
[Section 5 / Theorem 5.1 vs. Appendix E.2 (Eq. 33)] Theorem 5.1 analyzes the constrained ERM over the feasible set V defined in Eq. 9, which depends on target-related constants (||sigma||_inf, R, |K|) and epsilon that are unknown to the learner. The implemented objective in Eq. 33 is an unconstrained, nonconvex problem with the balancing regularizer lambda1(||a||_2^2 - ||v||_2^2)^2 and an L1 penalty on a. The paper provides no result connecting the solution of Eq. 33 to the solution of the constrained ERM of Eq. 10, so the sample-complexity guarantee of Theorem 5.1 is not established for the actual algorithm used in the experiments.
[Section 6.3 and Appendix E.1] The synthetic recovery experiments use target activations sigma1(x)=sin(pi x)1[-1,1], sigma2(x)=sin(pi x)1[0,1], and sigma3(x)=-sin(pi(x+0.5))1[-1.5,-0.5]+sin(pi(x-0.5))1[0.5,1.5]. These functions are discontinuous and are not in the class F_K of Eq. 1, which requires continuous, compactly supported, Lipschitz activations. Since Proposition 4.1 and Theorem 4.2 explicitly assume this target class, the experiments in Section 6.3 lie outside the assumptions of the theory and therefore cannot serve as a validation of those results. A smooth, compactly supported, Lipschitz activation should be used if the experiment is meant to substantiate the theory.
[Section 6.1 / 6.2 and Table 1] The empirical gains in Table 1 are presented as demonstrating the advantage of learnable activations, but the experimental design does not isolate that mechanism. In the tested regime (N=16, h=0.25), the theory does not apply, so the observed improvements could equally be caused by the RBF-mixture feature class, by the implicit bias of the regularizer (||a||_2^2 - ||v||_2^2)^2 in Eq. 33, or by differences in the optimization of the baseline models. A controlled ablation that fixes the feature class and regularizer while toggling only the learnability of the activation coefficients would be needed to support the causal claim; otherwise the paper should state that the gains are empirical observations without theoretical coverage.
[Checklist and Appendix E] The checklist states that code, training details, and infrastructure are provided, but the manuscript and appendix do not include code, explicit optimizer hyperparameters (learning rate, epochs, batch size), data split details, or computing infrastructure. This makes the main empirical results hard to reproduce. The authors should either provide these materials or revise the checklist claims accordingly.

minor comments (5)

[Section 1 and 6.1] There are typos in the text: 'outperfom' in the abstract/contributions, 'empirial' risk, 'continous', 'techinique', and 'dicrete'. In Section 6.1, Observation (2) says 'RBF shows 2~4 times faster computational efficiency than RBF'; the second mention should clearly be 'BS' (B-spline).
[Section 6.1] The sentence 'All models are compared within the same width M' is imprecise for RFLAF, which has N additional activation coefficients and different basis function evaluations. Please state explicitly whether the comparison matches width M only, or total parameter count, and clarify the effect on the time measurements in Table 2.
[Figure 1 / Section 6.2] Figure 1 plots test loss and inference/training time against grid number N. The statement that the figure 'substantiates Proposition 4.1' conflates test loss with the approximation error of the activation; the figure shows a performance trend, not the epsilon-dependent bound of Proposition 4.1. The wording should be adjusted to say the figure illustrates a trend consistent in direction, but not a quantitative validation.
[Section 4] The paper states that 'the number of grid points N should scale with approximately the same order of M' and then notes that N=16 suffices in practice. This distinction is useful, but the notation eTheta(1/(epsilon h)) in the sentence following Theorem 4.2 is not defined locally; please define it clearly at the first use.
[Appendix E.2] The phrase 'The second regularizer is the common L1 regularizer and is not compellent' appears to contain a typo; 'not compellent' should probably be 'not compulsory' or 'not essential'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the RFLAF approximation and generalization bounds are derived from external universal-approximation, direct integral evaluation, and Rademacher-complexity arguments, not from their own conclusions.

full rationale

The paper's derivation chain is self-contained and non-circular. Theorem 3.1 is a direct evaluation of the kernel integral E[B(w^T x)B(w^T x')], and the subsequent representation results are consequences of the resulting Taylor expansion. The central expressivity claim rests on Proposition 4.1, whose proof constructs the RBF coefficients explicitly via a Gaussian-convolution and Riemann-sum approximation of the target activation sigma; it does not assume the conclusion and does not depend on any self-citation. Theorem 4.2 then combines that constructive approximation with a concentration bound for random features, and Theorem 5.1 derives excess risk from a standard Rademacher-complexity estimate over the constrained set in Eq. (9). No fitted parameter is renamed as a prediction, no load-bearing self-citation appears (the bibliography contains no overlapping author self-citations), and no external uniqueness or ansatz is imported to force the model choice. The real weaknesses are scope gaps rather than circularity: the feasible set in Eq. (9) depends on target-dependent constants unknown to the learner, making the excess-risk bound an oracle bound, and the experiments (N=16, h=4/N=0.25, M=1000-3000) lie far outside the regime required by Proposition 4.1, so the empirical gains are not covered by the theory. These are correctness/rigor concerns, not reductions of the paper's predictions to its inputs by construction.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The model's learnable weights a and v are the intended fitting mechanism and are not free parameters in the ledger sense. The ledger lists the manually chosen experimental hyperparameters and the theoretical assumptions the bounds rely on. No new physical or mathematical entities are introduced; the RBF, spline, and polynomial bases are standard.

free parameters (4)

grid number N = 16
Chosen by hand in experiments; the theory requires N to scale polylogarithmically with M, so N=16 is far below the theoretical regime.
RBF width h = 4/N = 0.25
Set by hand as h = 4/N in experiments; the theory sets h depending on the target Lipschitz constant and desired accuracy.
grid range K = [-2,2]
Assumed support of the target activation in experiments; not derived from data or theory.
regularization coefficients lambda1, lambda2 = not reported
Used in Eq. (33) for training RFLAF; values are not provided, affecting reproducibility and the empirical claims.

assumptions (5)

standard math Gaussian universal approximation: any continuous sigma on compact K can be uniformly approximated by weighted sums of Gaussian RBFs
Invoked in Section 4 before Proposition 4.1 to justify the basis expansion of the activation.
domain assumption Target class F_K: sigma in C_c(K) with Lipschitz constant L, and v Lipschitz
Defines the function class in Eq. (1); all the approximation and generalization theory is confined to this class.
domain assumption Loss function ell is rho-Lipschitz in the prediction and |ell(0,y)| <= rho
Assumed in Section 5 to apply Talagrand's contraction principle and the Rademacher complexity bound.
domain assumption The constrained set V can be chosen using the target's ||sigma||_infty, |K|, and R
The excess-risk bound in Theorem 5.1 applies to a learner that knows target regularity; this is an oracle-type assumption not satisfied by a fixed model class.
domain assumption Inputs are normalized to unit norm for the rotation-invariant kernel analysis
Theorem 3.2, Corollary 3.3, and the feature map derivation assume ||x|| = ||x'|| = 1; this is not stated for the rest of the theory.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Learning Expressive Random Feature Models via Parametrized Activations." pith.science (2026). https://pith.science/paper/ZI7C2EBE

@misc{pith2026241119468,
  author       = {Pith},
  title        = {Pith review of: Learning Expressive Random Feature Models via Parametrized Activations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZI7C2EBE}},
  note         = {Machine review of arXiv:2411.19468}
}

read the original abstract

The random feature (RF) method is a powerful kernel approximation technique, but it typically uses fixed activation functions, limiting its adaptability across diverse tasks. To overcome this limitation, we introduce the Random Feature Model with Learnable Activation Functions (RFLAF), a novel statistical model that parameterizes activation functions as weighted sums of basis functions within the random feature framework. Examples of basis functions include radial basis functions (RBFs), spline functions, polynomials, and so forth. For theoretical results, we consider RBFs as representative basis functions. We start with a single RBF as the activation, and then extend the results to multiple RBFs, demonstrating that RF models with a learnable activation component substantially expand the represented function space. We provide estimates on the required number of samples and random features to achieve low excess risk. In our experiments, we test RFLAF with three types of bases: radial basis functions, spline functions and polynomials. Experimental results show that RFLAFs with RBFs and splines consistently outperform other RF models, where RBFs are three times more computationally efficient than splines. We then unfreeze the first-layer parameters and retrain the models, validating the expressivity advantage of learnable activation components on regular two-layer neural networks. Our work provides a deeper understanding of learnable activation components within modern neural network architectures.

Figures

Figures reproduced from arXiv: 2411.19468 by the authors.

**Figure 2.** The Activation Function Learned in RFLAF. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** The Activation Functions Learned in RFLAF. [PITH_FULL_IMAGE:figures/full_fig_p043_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

SchoenbAt: Rethinking Attention with Polynomial basis
cs.LG 2025-05 reject novelty 5.0 of 10

SchoenbAt approximates dot-product kernelized attention with random Maclaurin features under Schoenberg's theorem, adding a batch-normalization step that keeps inputs within the theorem's domain.

Reference graph

Works this paper leans on

13 extracted references · 11 canonical work pages · cited by 1 Pith paper

[1]

[Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm

For all models and algorithms presented, check if you include: (a) A clear description of the mathematical set- ting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] (c) (Optional) Anonymized source code, with specification of all dependencies, including extern...
[2]

[Yes] (b) Complete proofs of all theoretical results

For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results. [Yes] (c) Clear explanations of any assumptions. [Yes]
[3]

[Yes] (b) All the training details (e.g., data splits, hy- perparameters, how they were chosen)

For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to re- produce the main experimental results (either in the supplemental material or as a URL). [Yes] (b) All the training details (e.g., data splits, hy- perparameters, how they were chosen). [Yes] (c) A clear definition of the spe...

work page
[4]

[Not Applicable] (b) The license information of the assets, if appli- cable

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Not Applicable] (b) The license information of the assets, if appli- cable. [Not Applicable] (c) Newassetseitherinthesupplementalmaterial or as a URL, if applicable. [Not Appli...

work page
[5]

[Not Applicable] (b) Descriptions of potential participant risks, withlinkstoInstitutionalReviewBoard(IRB) approvals if applicable

If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to partici- pants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, withlinkstoInstitutionalReviewBoard(IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to part...

work page 2018
[6]

IfYis a sub-gaussian random variable, thenP(|Y| ≥ϵ)≤2 exp −ϵ2/∥Y∥ 2 ψ2

work page
[7]

Lemma A.5SupposeYis a random variable

IfP(|Y| ≥ϵ)≤2 exp −ϵ2/K 2 , then∥Y∥ ψ2 ≤ √ 2K. Lemma A.5SupposeYis a random variable

work page
[8]

If there existK0 > 0such that Eeλ2Y 2 ≤e K2 0 λ2 for all λ2 ≤ 1/K 2 0, then Y is a sub-gaussian random variable with sub-gaussian norm∥Y∥ ψ2 ≤K 0/√log 2≤ √ 2K0

work page

Show all 13 references

[9]

Lemma A.6SupposeYis a random variable andEY= 0

IfYis a sub-gaussian random variable, thenK 0 = 2∥Y∥ ψ2 such thatEe λ2Y 2 ≤e K2 0 λ2 for allλ 2 ≤1/K 2 0. Lemma A.6SupposeYis a random variable andEY= 0
[10]

IfEe λ2Y 2 ≤e K2 0 λ2 for allλ 2 ≤1/K 2 0, thenEe λY ≤e K2 0 λ2 for allλ∈R
[11]

IfEe λY ≤e K2 0 λ2 for allλ∈R, thenEe λ2Y 2 ≤e 16K 2 0 λ2 for allλ 2 ≤1/16K 2 0. For sums of independent sub-gaussian random variables, the Proposition 2.6.1 in (Vershynin, 2018) states that Lemma A.7LetX 1, ..., XM be independent copies of a sub-gaussian random variableXandEX...

2018
[12]

Forn= 2k,R n(p) =P 2 k (p), whereP k(p)is a polynomial of degreek
[13]

σ(w⊤x)− NX i=1 aiBi(w⊤x) ! v(w) # ∞ ≤E w∼N(0,1)

Forn= 2k+ 1,R n(p) =p·Q 2 k(p), whereQ k(p)is a polynomial of degreek. The correctness of the first observation is easily proved by induction. In the next step, we give a formal proof of the correctness of the second and third observations. Learning Expressive Random F eature ...

2018

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

[Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm

For all models and algorithms presented, check if you include: (a) A clear description of the mathematical set- ting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] (c) (Optional) Anonymized source code, with specification of all dependencies, including extern...

[2] [2]

[Yes] (b) Complete proofs of all theoretical results

For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results. [Yes] (c) Clear explanations of any assumptions. [Yes]

[3] [3]

[Yes] (b) All the training details (e.g., data splits, hy- perparameters, how they were chosen)

For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to re- produce the main experimental results (either in the supplemental material or as a URL). [Yes] (b) All the training details (e.g., data splits, hy- perparameters, how they were chosen). [Yes] (c) A clear definition of the spe...

work page

[4] [4]

[Not Applicable] (b) The license information of the assets, if appli- cable

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Not Applicable] (b) The license information of the assets, if appli- cable. [Not Applicable] (c) Newassetseitherinthesupplementalmaterial or as a URL, if applicable. [Not Appli...

work page

[5] [5]

[Not Applicable] (b) Descriptions of potential participant risks, withlinkstoInstitutionalReviewBoard(IRB) approvals if applicable

If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to partici- pants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, withlinkstoInstitutionalReviewBoard(IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to part...

work page 2018

[6] [6]

IfYis a sub-gaussian random variable, thenP(|Y| ≥ϵ)≤2 exp −ϵ2/∥Y∥ 2 ψ2

work page

[7] [7]

Lemma A.5SupposeYis a random variable

IfP(|Y| ≥ϵ)≤2 exp −ϵ2/K 2 , then∥Y∥ ψ2 ≤ √ 2K. Lemma A.5SupposeYis a random variable

work page

[8] [8]

If there existK0 > 0such that Eeλ2Y 2 ≤e K2 0 λ2 for all λ2 ≤ 1/K 2 0, then Y is a sub-gaussian random variable with sub-gaussian norm∥Y∥ ψ2 ≤K 0/√log 2≤ √ 2K0

work page