检索结果-内蒙古大学图书馆

Differentially Private Kernel Density Estimation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Liu, Erzhi Hu, Jerry Yao-Chieh Reneau, Alex Song, Zhao Liu, Han Center for Foundation Models and Generative AI Department of Computer Science Northwestern University EvanstonIL60208 United States Ensemble AI San FranciscoCA94133 United States Simons Institute for the Theory of Computing UC Berkeley BerkeleyCA94720 United States Center for Foundation Models and Generative AI Department of Computer Science Department of Statistics and Data Science Northwestern University EvanstonIL60208 United States

We introduce a refined differentially private (DP) data structure for kernel density estimation (KDE) with 1, 2 and pp kernels. This new DP data structure offers not only improved privacy-utility tradeoff but also better query efficiency over prior results. Specifically, we study the mathematical problem: given a similarity function f (or DP KDE) and a private dataset X ⊂ d, our goal is to preprocess X so that for any query y ∈ d, we approximate ∑ x∈X f(x, y) in a differentially private fashion. The best previous algorithm for f(x, y) = x − y1 is the node-contaminated balanced binary tree by [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. Their algorithm requires O(nd) space and time for preprocessing with n = |X|. For any query point, the query time is α−1dlog2 n, with an error guarantee of (1 + α)-approximation and ϵ−1α−0.5d1.5Rlog1.5 n. In this paper, we use the same space and pre-processing time, improve the best previous result [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] in three aspects • We reduce query time by α−1 log n factor • We improve the approximation ratio from α to 1 • We reduce the error dependence by a factor of α−0.5 From a technical perspective, our method of constructing the search tree differs from previous work [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]. In prior work, for each query, the answer is split into α−1 log n numbers, each derived from the summation of log n values in interval tree countings. In contrast, we construct the tree differently, splitting the answer into log n numbers, where each is a smart combination of two distance values, two counting values, and y itself. We believe our tree structure may be of independent interest. © 2024, CC BY-NC-SA.

关键词： Differential privacy

Provably Optimal Memory Capacity for Modern Hopfield models: Transformer-Compatible Dense Associative Memories as Spherical Codes

学校读者我要写书评

暂无评论

arXiv 2024年

We study the optimal memorization capacity of modern Hopfield models and Kernelized Hopfield models (KHMs), a transformer-compatible class of Dense Associative Memories. We present a tight analysis by establishing a connection between the memory configuration of KHMs and spherical codes from information theory. Specifically, we treat the stored memory set as a specialized spherical code. This enables us to cast the memorization problem in KHMs into a point arrangement problem on a hypersphere. We show that the optimal capacity of KHMs occurs when the feature space allows memories to form an optimal spherical code. This unique perspective leads to: (i) An analysis of how KHMs achieve optimal memory capacity, and identify corresponding necessary conditions. Importantly, we establish an upper capacity bound that matches the well-known exponential lower bound in the literature. This provides the first tight and optimal asymptotic memory capacity for modern Hopfield models. (ii) A sub-linear time algorithm U-Hop+ to reach KHMs’ optimal capacity. (iii) An analysis of the scaling behavior of the required feature dimension relative to the number of stored memories. These efforts improve both the retrieval capability of KHMs and the representation learning of corresponding transformers. Experimentally, we provide thorough numerical results to back up theoretical findings. © 2024, CC BY-NC-SA.

关键词： Associative storage

On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs) 38

学校读者我要写书评

暂无评论

On Statistical Rates and Provably Efficient Criteria of Late...

38th Conference on Neural Information Processing Systems, NeurIPS 2024

作者： Hu, Jerry Yao-Chieh Wu, Weimin Li, Zhuoru Pi, Sophia Song, Zhao Liu, Han Center for Foundation Models and Generative AI Northwestern University EvanstonIL60208 United States Department of Computer Science Northwestern University EvanstonIL60208 United States Department of Statistics and Data Science Northwestern University EvanstonIL60208 United States Simons Institute for the Theory of Computing UC Berkeley BerkeleyCA94720 United States

We investigate the statistical and computational limits of latent Diffusion Transformers (DiTs) under the low-dimensional linear latent space assumption. Statistically, we study the universal approximation and sample complexity of the DiTs score function, as well as the distribution recovery property of the initial data. Specifically, under mild data assumptions, we derive an approximation error bound for the score network of latent DiTs, which is sub-linear in the latent space dimension. Additionally, we derive the corresponding sample complexity bound and show that the data distribution generated from the estimated score function converges toward a proximate area of the original one. Computationally, we characterize the hardness of both forward inference and backward computation of latent DiTs, assuming the Strong Exponential Time Hypothesis (SETH). For forward inference, we identify efficient criteria for all possible latent DiTs inference algorithms and showcase our theory by pushing the efficiency toward almost-linear time inference. For backward computation, we leverage the low-rank structure within the gradient computation of DiTs training for possible algorithmic speedup. Specifically, we show that such speedup achieves almost-linear time latent DiTs training by casting the DiTs gradient as a series of chained low-rank approximations with bounded error. Under the low-dimensional assumption, we show that the statistical rates and the computational efficiency are all dominated by the dimension of the subspace, suggesting that latent DiTs have the potential to bypass the challenges associated with the high dimensionality of initial data. © 2024 Neural information processing systems foundation. All rights reserved.

关键词：

On Differentially Private String Distances

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hu, Jerry Yao-Chieh Liu, Erzhi Liu, Han Song, Zhao Zhang, Lichen Ensemble AI San FranciscoCA United States Center for Foundation Models and Generative AI Department of Computer Science Northwestern University EvanstonIL United States Center for Foundation Models and Generative AI Department of Computer Science Department of Statistics and Data Science Northwestern University EvanstonIL United States Simons Institute for the Theory of Computing UC Berkeley BerkeleyCA United States Department of Mathematics & Computer Science and Artificial Intelligence Laboratory MIT CambridgeMA United States

Given a database of bit strings A1, . . ., Am ∈ {0, 1}n, a fundamental data structure task is to estimate the distances between a given query B ∈ {0, 1}n with all the strings in the database. In addition, one might further want to ensure the integrity of the database by releasing these distance statistics in a secure manner. In this work, we propose differentially private (DP) data structures for this type of tasks, with a focus on Hamming and edit distance. On top of the strong privacy guarantees, our data structures are also time- and space-efficient. In particular, our data structure is ǫ-DP against any sequence of queries of arbitrary length, and for any query B such that the maximum distance to any string in the database is at most k, we output m distance estimates. Moreover, • For Hamming distance, our data structure answers any query in Oe(mk + n) time and each estimate deviates from the true distance by at most Oe(k/eǫ/ log k);• For edit distance, our data structure answers any query in Oe(mk2 + n) time and each estimate deviates from the true distance by at most Oe(k/eǫ/(log k log n)). For moderate k, both data structures support sublinear query operations. We obtain these results via a novel adaptation of the randomized response technique as a bit flipping procedure, applied to the sketched strings. © 2024, CC BY-NC-SA.

关键词： Structured Query Language

On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hu, Jerry Yao-Chieh Wu, Weimin Song, Zhao Liu, Han Center for Foundation Models Generative AI Department of Computer Science Department of Statistics and Data Science Northwestern University EvanstonIL60208 United States Simons Institute for the Theory of Computing UC Berkeley BerkeleyCA94720 United States

关键词： Distribution transformers

AlignAb: Pareto-Optimal Energy Alignment for Designing Nature-Like Antibodies

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wen, Yibo Xu, Chenwei Hu, Jerry Yao-Chieh Liu, Han Center for Foundation Models and Generative AI Northwestern University EvanstonIL60208 United States Department of Computer Science Northwestern University EvanstonIL60208 United States Department of Statistics and Data Science Northwestern University EvanstonIL60208 United States

We present a three-stage framework for training deep learning models specializing in antibody sequence-structure co-design. We first pre-train a language model using millions of antibody sequence data. Then, we employ the learned representations to guide the training of a diffusion model for joint optimization over both sequence and structure of antibodies. During the final alignment stage, we optimize the model to favor antibodies with low repulsion and high attraction to the antigen binding site, enhancing the rationality and functionality of the designs. To mitigate conflicting energy preferences, we extend AbDPO (Antibody Direct Preference Optimization) to guide the model towards Pareto optimality under multiple energy-based alignment objectives. Furthermore, we adopt an iterative learning paradigm with temperature scaling, enabling the model to benefit from diverse online datasets without requiring additional data. In practice, our proposed methods achieve high stability and efficiency in producing a better Pareto front of antibody designs compared to top samples generated by baselines and previous alignment techniques. Through extensive experiments, we showcase the superior performance of our methods in generating nature-like antibodies with high binding affinity consistently. © 2024, CC BY-NC-ND.

关键词： Antibodies

Universal Approximation with Softmax Attention

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hu, Jerry Yao-Chieh Liu, Hude Chen, Hong-Yu Wu, Weimin Liu, Han Center for Foundation Models and Generative AI Northwestern University EvanstonIL60208 United States Department of Computer Science Northwestern University EvanstonIL60208 United States School of Mathematical Sciences Fudan University Shanghai200433 China Department of Statistics and Data Science Northwestern University EvanstonIL60208 United States

We prove that with linear transformations, both (i) two-layer self-attention and (ii) one-layer self-attention followed by a softmax function are universal approximators for continuous sequence-to-sequence functions on compact domains. Our main technique is a new interpolation-based method for analyzing attention’s internal mechanism. This leads to our key insight: self-attention is able to approximate a generalized version of ReLU to arbitrary precision, and hence subsumes many known universal approximators. Building on these, we show that two-layer multi-head attention alone suffices as a sequence-to-sequence universal approximator. In contrast, prior works rely on feed-forward networks to establish universal approximation in Transformers. Furthermore, we extend our techniques to show that, (softmax-)attention-only layers are capable of approximating various statistical models in-context. We believe these techniques hold independent interest. © 2025, CC BY-SA.

关键词： Linear transformations

Transformers are Deep Optimizers: Provable In-Context Learning for Deep Model Training

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wu, Weimin Su, Maojiang Hu, Jerry Yao-Chieh Song, Zhao Liu, Han Center for Foundation Models and Generative AI Northwestern University EvanstonIL60208 United States Department of Computer Science Northwestern University EvanstonIL60208 United States Department of Information and Computing Science USTC Anhui Hefei230026 China Simons Institute for the Theory of Computing UC Berkeley BerkeleyCA94720 United States Department of Statistics and Data Science Northwestern University EvanstonIL60208 United States

We investigate the transformer’s capability for in-context learning (ICL) to simulate the training process of deep models. Our key contribution is providing a positive example of using a transformer to train a deep neural network by gradient descent in an implicit fashion via ICL. Specifically, we provide an explicit construction of a (2N + 4)L-layer transformer capable of simulating L gradient descent steps of an N-layer ReLU network through ICL. We also give the theoretical guarantees for the approximation within any given error and the convergence of the ICL gradient descent. Additionally, we extend our analysis to the more practical setting using Softmax-based transformers. We validate our findings on synthetic datasets for 3-layer, 4-layer, and 6-layer neural networks. The results show that ICL performance matches that of direct training. © 2024, CC BY-NC-SA.

关键词： Deep reinforcement learning

On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimality

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hu, Jerry Yao-Chieh Wu, Weimin Lee, Yi-Chen Huang, Yu-Chao Chen, Minshuo Liu, Han Center for Foundation Models and Generative AI Northwestern University EvanstonIL60208 United States Department of Computer Science Northwestern University EvanstonIL60208 United States Department of Physics National Taiwan University Taipei106319 Taiwan Physics Division National Center for Theoretical Sciences Taipei106319 Taiwan Department of Industrial Engineering & Management Sciences Northwestern University EvanstonIL60208 United States Department of Statistics and Data Science Northwestern University EvanstonIL60208 United States

We investigate the approximation and estimation rates of conditional diffusion transformers (DiTs) with classifier-free guidance. We present a comprehensive analysis for "in-context" conditional DiTs under four common data assumptions. We show that both conditional DiTs and their latent variants lead to the minimax optimality of unconditional DiTs under identified settings. Specifically, we discretize the input domains into infinitesimal grids and then perform a term-by-term Taylor expansion on the conditional diffusion score function under Hölder smooth data assumption. This enables fine-grained use of transformers’ universal approximation through a more detailed piecewise constant approximation and hence obtains tighter bounds. Additionally, we extend our analysis to the latent setting under the linear latent subspace assumption. We not only show that latent conditional DiTs achieve lower bounds than conditional DiTs both in approximation and estimation, but also show the minimax optimality of latent unconditional DiTs. Our findings establish statistical limits for conditional and unconditional DiTs, and offer practical guidance toward developing more efficient and accurate DiT models. © 2024, CC BY-NC-SA.

关键词：