Deep learning has been widely used in many fields, but the model training process usually consumes massive computational resources and time. Therefore, designing an efficient neural network training method with a provable convergence guarantee is a fundamental and important research question. In this paper, we present a static half-space report data structure that consists of a fully connected two-layer neural network for shifted ReLU activation to enable activated neuron identification in sublinear time via geometric search. We also prove that our algorithm can converge in O(M2/ϵ2) time with network size quadratic in the coefficient norm upper bound M and error term ϵ.

In this paper, we consider a heavy inner product identification problem, which generalizes the Light Bulb problem ([1]): Given two sets $A \subset\{-1,+1\}^{d}$ and $B \subset\{-1,+1\}^{d}$ with $|A|=|B|=n$, if there are exact k pairs whose inner product passes a certain threshold, i.e., $\{\left(a_{1}, b_{1}\right), \cdots,\left(a_{k}, b_{k}\right)\} \subset A \times B$ such that $\forall i \in[k],\left\langle a_{i}, b_{i}\right\rangle \geq \rho \cdot d$, for a threshold $\rho \in(0,1)$, the goal is to identify those k heavy inner products. We provide an algorithm that runs in $O(n^{2 \omega / 3+o(1)})$ time to find the k inner product pairs that surpass $\rho \cdot d$ threshold with high probability, where $\omega$ is the current matrix multiplication exponent. By solving this problem, our method speed up the training of neural networks with ReLU activation function.

Mahalanobis metrics are widely used in machine learning in conjunction with methods like k-nearest neighbors, k-means clustering, and k-medians clustering. Despite their importance, there has not been any prior work on applying sketching techniques to speed up algorithms for Mahalanobis metrics. In this paper, we initiate the study of dimension reduction for Mahalanobis metrics. In particular, we provide efficient data structures for solving the Approximate Distance Estimation (ADE) problem for Mahalanobis distances. We first provide a randomized Monte Carlo data structure. Then, we show how we can adapt it to provide our main data structure which can handle sequences of adaptive queries and also online updates to both the Mahalanobis metric matrix and the data points, making it amenable to be used in conjunction with prior algorithms for online learning of Mahalanobis metrics.

In this paper, we propose Adam-Hash: an adaptive and dynamic multi-resolution hashing data-structure for fast pairwise summation estimation. Given a data-set X ⊂ ℝd, a binary function f : ℝd× ℝd→ ℝ, and a point y ∈ ℝd, the Pairwise Summation Estimate $PS{E_X}(y): = \frac{1}{{\left| X \right|}}\sum\nolimits_{x \in X} {f(x,y)} $. For any given data-set X, we need to design a data-structure such that given any query point y ∈ ℝd, the data-structure approximately estimates PSEX(y) in time that is sub-linear in |X|. Prior works on this problem have focused exclusively on the case where the data-set is static, and the queries are independent. In this paper, we design a hashing-based PSE data-structure which works for the more practical dynamic setting in which insertions, deletions, and replacements of points are allowed. Moreover, our proposed Adam-Hash is also robust to adaptive PSE queries, where an adversary can choose query qj∈ ℝddepending on the output from previous queries q1, q2, …, qj–1.

There has been a recent effort in applying differential privacy on memory access patterns to enhance data privacy. This is called differential obliviousness. Differential obliviousness is a promising direction because it provides a principled trade-off between performance and desired level of privacy. To date, it is still an open question whether differential obliviousness can speed up database processing with respect to full obliviousness. In this paper, we present the design and implementation of Adore: A set of D ifferentially O blivious RE lational database operators. Adore includes selection with projection, grouping with aggregation, and foreign key join. We prove that they satisfy the notion of differential obliviousness. Our differentially oblivious operators have reduced cache complexity, runtime complexity, and output size compared to their state-of-the-art fully oblivious counterparts. We also demonstrate that our implementation of these differentially oblivious operators can outperform their state-of-the-art fully oblivious counterparts by up to 7.4X.