More Like this

1. More efficient approximation of smoothing splines via space-filling basis selection

   https://doi.org/10.1093/biomet/asaa019  

   Meng, Cheng; Zhang, Xinlian; Zhang, Jingyi; Zhong, Wenxuan; Ma, Ping (May 2020, Biometrika)

   null (Ed.)

   Summary We consider the problem of approximating smoothing spline estimators in a nonparametric regression model. When applied to a sample of size $$n$$, the smoothing spline estimator can be expressed as a linear combination of $$n$$ basis functions, requiring $O(n^3)$ computational time when the number $$d$$ of predictors is two or more. Such a sizeable computational cost hinders the broad applicability of smoothing splines. In practice, the full-sample smoothing spline estimator can be approximated by an estimator based on $$q$$ randomly selected basis functions, resulting in a computational cost of $O(nq^2)$. It is known that these two estimators converge at the same rate when $$q$$ is of order $$O\{n^{2/(pr+1)}\}$$, where $$p\in [1,2]$$ depends on the true function and $r > 1$ depends on the type of spline. Such a $$q$$ is called the essential number of basis functions. In this article, we develop a more efficient basis selection method. By selecting basis functions corresponding to approximately equally spaced observations, the proposed method chooses a set of basis functions with great diversity. The asymptotic analysis shows that the proposed smoothing spline estimator can decrease $$q$$ to around $$O\{n^{1/(pr+1)}\}$$ when $$d\leq pr+1$$. Applications to synthetic and real-world datasets show that the proposed method leads to a smaller prediction error than other basis selection methods. 

   more » « less
2. Factorization problems in complex reflection groups

   Lewis, J. B.; Morales, A. H. (July 2019, Séminaire lotharingien de combinatoire)

   We enumerate factorizations of a Coxeter element into arbitrary factors in the complex reflection groups G(d, 1, n) (the wreath product of the symmetric group with a cyclic group) and its subgroup G(d, d, n), applying combinatorial and algebraic methods, respectively. After a change of basis, the coefficients that appear are the same as those that appear in the corresponding enumeration in the symmetric group. 

   more » « less
3. A New Connection Between Node and Edge Depth Robust Graphs

   https://doi.org/10.4230/LIPIcs.ITCS.2021.64  

   Blocki, J; Cinkoske, M. (January 2021, ITCS 2021)

   Given a directed acyclic graph (DAG) G=(V,E), we say that G is (e,d)-depth-robust (resp. (e,d)-edge-depth-robust) if for any set S⊆V (resp. S⊆E) of at most |S|≤e nodes (resp. edges) the graph G−S contains a directed path of length d. While edge-depth-robust graphs are potentially easier to construct, many applications in cryptography require node depth-robust graphs with small indegree. We create a graph reduction that transforms an (e,d)-edge-depth-robust graph with m edges into a (e/2,d)-depth-robust graph with O(m) nodes and constant indegree. One immediate consequence of this result is the first construction of a provably (nloglognlogn,nlogn(logn)loglogn)-depth-robust graph with constant indegree. Our reduction crucially relies on ST-robust graphs, a new graph property we introduce which may be of independent interest. We say that a directed, acyclic graph with n inputs and n outputs is (k1,k2)-ST-robust if we can remove any k1 nodes and there exists a subgraph containing at least k2 inputs and k2 outputs such that each of the k2 inputs is connected to all of the k2 outputs. If the graph if (k1,n−k1)-ST-robust for all k1≤n we say that the graph is maximally ST-robust. We show how to construct maximally ST-robust graphs with constant indegree and O(n) nodes. Given a family M of ST-robust graphs and an arbitrary (e,d)-edge-depth-robust graph G we construct a new constant-indegree graph Reduce(G,M) by replacing each node in G with an ST-robust graph from M. We also show that ST-robust graphs can be used to construct (tight) proofs-of-space and (asymptotically) improved wide-block labeling functions. 

   more » « less
4. Tractability of approximation by general shallow networks

   https://doi.org/10.1142/S0219530524400013  

   Mhaskar, Hrushikesh N; Mao, Tong (April 2024, Analysis and Applications)

   In this paper, we present a sharper version of the results in the paper Dimension independent bounds for general shallow networks; Neural Networks, \textbf{123} (2020), 142-152. Let $$\mathbb{X}$$ and $$\mathbb{Y}$$ be compact metric spaces. We consider approximation of functions of the form $$ x\mapsto\int_{\mathbb{Y}} G( x, y)d\tau( y)$$, $$ x\in\mathbb{X}$$, by $$G$$-networks of the form $$ x\mapsto \sum_{k=1}^n a_kG( x, y_k)$$, $$ y_1,\cdots, y_n\in\mathbb{Y}$$, $$a_1,\cdots, a_n\in\mathbb{R}$$. Defining the dimensions of $$\mathbb{X}$$ and $$\mathbb{Y}$$ in terms of covering numbers, we obtain dimension independent bounds on the degree of approximation in terms of $$n$$, where also the constants involved are all dependent at most polynomially on the dimensions. Applications include approximation by power rectified linear unit networks, zonal function networks, certain radial basis function networks as well as the important problem of function extension to higher dimensional spaces. 

   more » « less
5. On the Cryptographic Hardness of Learning Single Periodic Neurons

   Min Jae Song; Ilias Zadik; Joan Bruna (December 2021, Advances in neural information processing systems)

   We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the pres- ence of noise. More precisely, our reduction shows that any polynomial-time algorithm (not necessarily gradient-based) for learning such functions under small noise implies a polynomial-time quantum algorithm for solving worst-case lattice problems, whose hardness form the foundation of lattice-based cryptography. Our core hard family of functions, which are well-approximated by one-layer neural networks, take the general form of a univariate periodic function applied to an affine projection of the data. These functions have appeared in previous seminal works which demonstrate their hardness against gradient-based (Shamir’18), and Statisti- cal Query (SQ) algorithms (Song et al.’17). We show that if (polynomially) small noise is added to the labels, the intractability of learning these functions applies to all polynomial-time algorithms, beyond gradient-based and SQ algorithms, under the aforementioned cryptographic assumptions. Moreover, we demonstrate the necessity of noise in the hardness result by designing a polynomial-time algorithm for learning certain families of such functions under exponentially small adversarial noise. Our proposed algorithm is not a gradient-based or an SQ algorithm, but is rather based on the celebrated Lenstra-Lenstra-Lovász (LLL) lattice basis reduction algorithm. Furthermore, in the absence of noise, this algorithm can be directly applied to solve CLWE detection (Bruna et al.’21) and phase retrieval with an optimal sample complexity of d + 1 samples. In the former case, this improves upon the quadratic-in-d sample complexity required in (Bruna et al.’21). 

   more » « less