Given an arbitrary set of high dimensional points in $\ell_1$, there are known negative results that preclude the possibility of mapping them to a low dimensional $\ell_1$ space while preserving distances with small multiplicative distortion. This is in stark contrast with dimension reduction in Euclidean space ($\ell_2$) where such mappings are always possible. While the first non-trivial lower bounds for $\ell_1$ dimension reduction were established almost 20 years ago, there has been minimal progress in understanding what sets of points in $\ell_1$ are conducive to a low-dimensional mapping. In this work, we shift the focus from the worst-case setting and initiate the study of a characterization of $\ell_1$ metrics that are conducive to dimension reduction in $\ell_1$. Our characterization focuses on metrics that are defined by the disagreement of binary variables over a probability distribution -- any $\ell_1$ metric can be represented in this form. We show that, for configurations of $n$ points in $\ell_1$ obtained from tree Ising models, we can reduce dimension to $\mathrm{polylog}(n)$ with constant distortion. In doing so, we develop technical tools for embedding capped metrics (also known as truncated metrics) which have been studied because of their applications in computer vision, and are objects of independent interest in metric geometry.
相關內容
We propose a novel approach to nonlinear functional regression, called the Mapping-to-Parameter function model, which addresses complex and nonlinear functional regression problems in parameter space by employing any supervised learning technique. Central to this model is the mapping of function data from an infinite-dimensional function space to a finite-dimensional parameter space. This is accomplished by concurrently approximating multiple functions with a common set of B-spline basis functions by any chosen order, with their knot distribution determined by the Iterative Local Placement Algorithm, a newly proposed free knot placement algorithm. In contrast to the conventional equidistant knot placement strategy that uniformly distributes knot locations based on a predefined number of knots, our proposed algorithms determine knot location according to the local complexity of the input or output functions. The performance of our knot placement algorithms is shown to be robust in both single-function approximation and multiple-function approximation contexts. Furthermore, the effectiveness and advantage of the proposed prediction model in handling both function-on-scalar regression and function-on-function regression problems are demonstrated through several real data applications, in comparison with four groups of state-of-the-art methods.
The $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-additive codes are subgroups of $\mathbb{Z}_2^{\alpha_1} \times \mathbb{Z}_4^{\alpha_2} \times \mathbb{Z}_8^{\alpha_3}$. A $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard code is a Hadamard code which is the Gray map image of a $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-additive code. A recursive construction of $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-additive Hadamard codes of type $(\alpha_1,\alpha_2, \alpha_3;t_1,t_2, t_3)$ with $\alpha_1 \neq 0$, $\alpha_2 \neq 0$, $\alpha_3 \neq 0$, $t_1\geq 1$, $t_2 \geq 0$, and $t_3\geq 1$ is known. In this paper, we generalize some known results for $\mathbb{Z}_2\mathbb{Z}_4$-linear Hadamard codes to $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes with $\alpha_1 \neq 0$, $\alpha_2 \neq 0$, and $\alpha_3 \neq 0$. First, we show for which types the corresponding $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes of length $2^t$ are nonlinear. For these codes, we compute the kernel and its dimension, which allows us to give a partial classification of these codes. Moreover, for $3 \leq t \leq 11$, we give a complete classification by providing the exact amount of nonequivalent such codes. We also prove the existence of several families of infinite such nonlinear $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes, which are not equivalent to any other constructed $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard code, nor to any $\mathbb{Z}_2\mathbb{Z}_4$-linear Hadamard code, nor to any previously constructed $\mathbb{Z}_{2^s}$-linear Hadamard code with $s\geq 2$, with the same length $2^t$.
We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times.
The random walk $d$-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk $d$-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every $d\ge 3$ hashes, let $c_d^*$ be the sharp threshold for the load factor at which a valid assignment of $cm$ objects to a hash table of size $m$ likely exists. We show that for any $d\ge 4$ hashes and load factor $c<c_d^*$, the expectation of the random walk insertion time is $O(1)$, that is, a constant depending only on $d$ and $c$ but not $m$.
Given a metric space $(V, d)$ along with an integer $k$, the $k$-Median problem asks to open $k$ centers $C \subseteq V$ to minimize $\sum_{v \in V} d(v, C)$, where $d(v, C) := \min_{c \in C} d(v, c)$. While the best-known approximation ratio of $2.613$ holds for the more general supplier version where an additional set $F \subseteq V$ is given with the restriction $C \subseteq F$, the best known hardness for these two versions are $1+1/e \approx 1.36$ and $1+2/e \approx 1.73$ respectively, using the same reduction from Max $k$-Coverage. We prove the following two results separating them. First, we show a $1.546$-parameterized approximation algorithm that runs in time $f(k) n^{O(1)}$. Since $1+2/e$ is proved to be the optimal approximation ratio for the supplier version in the parameterized setting, this result separates the original $k$-Median from the supplier version. Next, we prove a $1.416$-hardness for polynomial-time algorithms assuming the Unique Games Conjecture. This is achieved via a new fine-grained hardness of Max-$k$-Coverage for small set sizes. Our upper bound and lower bound are derived from almost the same expression, with the only difference coming from the well-known separation between the powers of LP and SDP on (hypergraph) vertex cover.
We present the library \texttt{lymph} for the finite element numerical discretization of coupled multi-physics problems. \texttt{lymph} is a Matlab library for the discretization of partial differential equations based on high-order discontinuous Galerkin methods on polytopal grids (PolyDG) for spatial discretization coupled with suitable finite-difference time marching schemes. The objective of the paper is to introduce the library by describing it in terms of installation, input/output data, and code structure, highlighting -- when necessary -- key implementation aspects related to the method. A user guide, proceeding step-by-step in the implementation and solution of a Poisson problem, is also provided. In the last part of the paper, we show the results obtained for several differential problems, namely the Poisson problem, the heat equation, and the elastodynamics system. Through these examples, we show the convergence properties and highlight some of the main features of the proposed method, i.e. geometric flexibility, high-order accuracy, and robustness with respect to heterogeneous physical parameters.
This paper describes $\pi2\text{vec}$, a method for representing behaviors of black box policies as feature vectors. The policy representations capture how the statistics of foundation model features change in response to the policy behavior in a task agnostic way, and can be trained from offline data, allowing them to be used in offline policy selection. This work provides a key piece of a recipe for fusing together three modern lines of research: Offline policy evaluation as a counterpart to offline RL, foundation models as generic and powerful state representations, and efficient policy selection in resource constrained environments.
Uplift modeling is a technique used to predict the effect of a treatment (e.g., discounts) on an individual's response. Although several methods have been proposed for multi-valued treatment, they are extended from binary treatment methods. There are still some limitations. Firstly, existing methods calculate uplift based on predicted responses, which may not guarantee a consistent uplift distribution between treatment and control groups. Moreover, this may cause cumulative errors for multi-valued treatment. Secondly, the model parameters become numerous with many prediction heads, leading to reduced efficiency. To address these issues, we propose a novel \underline{M}ulti-gate \underline{M}ixture-of-Experts based \underline{M}ulti-valued \underline{T}reatment \underline{N}etwork (M$^3$TN). M$^3$TN consists of two components: 1) a feature representation module with Multi-gate Mixture-of-Experts to improve the efficiency; 2) a reparameterization module by modeling uplift explicitly to improve the effectiveness. We also conduct extensive experiments to demonstrate the effectiveness and efficiency of our M$^3$TN.
We obtain all possible parameters of Plotkin-optimal two-Lee weight projective codes over $\mathbb{Z}_4,$ together with their weight distributions. We show the existence of codes with these parameters as well as their weight distributions by constructing an infinite family of two-weight codes. Previously known codes constructed by Shi et al. (\emph{Des Codes Cryptogr.} {\bf 88}(3):1-13, 2020) can be derived as a special case of our results. We also prove that the Gray image of any Plotkin-optimal two-Lee weight projective codes over $\mathbb{Z}_4$ has the same parameters and weight distribution as some two-weight binary projective codes of type SU1 in the sense of Calderbank and Kantor (\emph{Bull. Lond. Math. Soc.} {\bf 18}:97-122, 1986).
Cross-validation is a widely used technique for assessing the performance of predictive models on unseen data. Many predictive models, such as Kernel-Based Partial Least-Squares (PLS) models, require the computation of $\mathbf{X}^{\mathbf{T}}\mathbf{X}$ and $\mathbf{X}^{\mathbf{T}}\mathbf{Y}$ using only training set samples from the input and output matrices, $\mathbf{X}$ and $\mathbf{Y}$, respectively. In this work, we present three algorithms that efficiently compute these matrices. The first one allows no column-wise preprocessing. The second one allows column-wise centering around the training set means. The third one allows column-wise centering and column-wise scaling around the training set means and standard deviations. Demonstrating correctness and superior computational complexity, they offer significant cross-validation speedup compared with straight-forward cross-validation and previous work on fast cross-validation - all without data leakage. Their suitability for parallelization is highlighted with an open-source Python implementation combining our algorithms with Improved Kernel PLS.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191