Search

The introduction of geometry has proven instrumental in the efforts towards more realistic models for real-world networks. In Geometric Inhomogeneous Random Graphs (GIRGs), Euclidean Geometry induces clustering of the vertices, which is widely observed in networks in the wild. Euclidean Geometry in multiple dimensions however restricts proximity of vertices to those cases where vertices are close in each coordinate. We introduce a large class of GIRG extensions, called BDF-GIRGs, which capture arbitrary hierarchies of the coordinates within the distance function of the vertex feature space. These distance functions have the potential to allow more realistic modeling of the complex formation of social ties in real-world networks, where similarities between people lead to connections. Here, similarity with respect to certain features, such as familial kinship or a shared workplace, suffices for the formation of ties. It is known that - while many key properties of GIRGs, such as log-log average distance and sparsity, are independent of the distance function - the Euclidean metric induces small separators, i.e. sublinear cuts of the unique giant component in GIRGs, whereas no such sublinear separators exist under the component-wise minimum distance. Building on work of Lengler and Todorovi\'{c}, we give a complete classification for the existence of small separators in BDF-GIRGs. We further show that BDF-GIRGs all fulfill a stochastic triangle inequality and thus also exhibit clustering.

Message passing on hypergraphs has been a standard framework for learning higher-order correlations between hypernodes. Recently-proposed hypergraph neural networks (HGNNs) can be categorized into spatial and spectral methods based on their design choices. In this work, we analyze the impact of change in hypergraph topology on the suboptimal performance of HGNNs and propose DPHGNN, a novel dual-perspective HGNN that introduces equivariant operator learning to capture lower-order semantics by inducing topology-aware spatial and spectral inductive biases. DPHGNN employs a unified framework to dynamically fuse lower-order explicit feature representations from the underlying graph into the super-imposed hypergraph structure. We benchmark DPHGNN over eight benchmark hypergraph datasets for the semi-supervised hypernode classification task and obtain superior performance compared to seven state-of-the-art baselines. We also provide a theoretical framework and a synthetic hypergraph isomorphism test to express the power of spatial HGNNs and quantify the expressivity of DPHGNN beyond the Generalized Weisfeiler Leman (1-GWL) test. Finally, DPHGNN was deployed by our partner e-commerce company for the Return-to-Origin (RTO) prediction task, which shows ~7% higher macro F1-Score than the best baseline., Comment: Accepted in SIGKDD'24 -- Research Track

End-to-end Task-Oriented Dialog (TOD) systems typically require extensive training datasets to perform well. In contrast, large language model (LLM) based TOD systems can excel even with limited data due to their ability to learn tasks through in-context exemplars. However, these models lack alignment with the style of responses in training data and often generate comprehensive responses, making it difficult for users to grasp the information quickly. In response, we propose SyncTOD that synergizes LLMs with task-specific hints to improve alignment in low-data settings. SyncTOD employs small auxiliary models to provide hints and select exemplars for in-context prompts. With ChatGPT, SyncTOD achieves superior performance compared to LLM-based baselines and SoTA models in low-data settings, while retaining competitive performance in full-data settings., Comment: EMNLP2024 Camera-Ready Version

We prove a new asymptotic equipartition property for the perplexity of long texts generated by a language model and present supporting experimental evidence from open-source models. Specifically we show that the logarithmic perplexity of any large text generated by a language model must asymptotically converge to the average entropy of its token distributions. This defines a "typical set" that all long synthetic texts generated by a language model must belong to. We show that this typical set is a vanishingly small subset of all possible grammatically correct outputs. These results suggest possible applications to important practical problems such as (a) detecting synthetic AI-generated text, and (b) testing whether a text was used to train a language model. We make no simplifying assumptions (such as stationarity) about the statistics of language model outputs, and therefore our results are directly applicable to practical real-world models without any approximations.

Monolithic large language models (LLMs) like GPT-4 have paved the way for modern generative AI applications. Training, serving, and maintaining monolithic LLMs at scale, however, remains prohibitively expensive and challenging. The disproportionate increase in compute-to-memory ratio of modern AI accelerators have created a memory wall, necessitating new methods to deploy AI. Composition of Experts (CoE) is an alternative modular approach that lowers the cost and complexity of training and serving. However, this approach presents two key challenges when using conventional hardware: (1) without fused operations, smaller models have lower operational intensity, which makes high utilization more challenging to achieve; and (2) hosting a large number of models can be either prohibitively expensive or slow when dynamically switching between them. In this paper, we describe how combining CoE, streaming dataflow, and a three-tier memory system scales the AI memory wall. We describe Samba-CoE, a CoE system with 150 experts and a trillion total parameters. We deploy Samba-CoE on the SambaNova SN40L Reconfigurable Dataflow Unit (RDU) - a commercial dataflow accelerator architecture that has been co-designed for enterprise inference and training applications. The chip introduces a new three-tier memory system with on-chip distributed SRAM, on-package HBM, and off-package DDR DRAM. A dedicated inter-RDU network enables scaling up and out over multiple sockets. We demonstrate speedups ranging from 2$\times$ to 13$\times$ on various benchmarks running on eight RDU sockets compared with an unfused baseline. We show that for CoE inference deployments, the 8-socket RDU Node reduces machine footprint by up to 19$\times$, speeds up model switching time by 15$\times$ to 31$\times$, and achieves an overall speedup of 3.7$\times$ over a DGX H100 and 6.6$\times$ over a DGX A100., Comment: 2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO)

Age-related language patterns play a crucial role in understanding linguistic differences and developing age-appropriate communication strategies. However, the lack of comprehensive and diverse datasets has hindered the progress of research in this area. To address this issue, we present TextAge, a curated text dataset that maps sentences to the age and age group of the producer, as well as an underage (under 13) label. TextAge covers a wide range of ages and includes both spoken and written data from various sources such as CHILDES, Meta, Poki Poems-by-kids, JUSThink, and the TV show "Survivor." The dataset undergoes extensive cleaning and preprocessing to ensure data quality and consistency. We demonstrate the utility of TextAge through two applications: Underage Detection and Generational Classification. For Underage Detection, we train a Naive Bayes classifier, fine-tuned RoBERTa, and XLNet models to differentiate between language patterns of minors and young-adults and over. For Generational Classification, the models classify language patterns into different age groups (kids, teens, twenties, etc.). The models excel at classifying the "kids" group but struggle with older age groups, particularly "fifties," "sixties," and "seventies," likely due to limited data samples and less pronounced linguistic differences. TextAge offers a valuable resource for studying age-related language patterns and developing age-sensitive language models. The dataset's diverse composition and the promising results of the classification tasks highlight its potential for various applications, such as content moderation, targeted advertising, and age-appropriate communication. Future work aims to expand the dataset further and explore advanced modeling techniques to improve performance on older age groups.

Modern cloud has turned data services into easily accessible commodities. With just a few clicks, users are now able to access a catalog of data processing systems for a wide range of tasks. However, the cloud brings in both complexity and opportunity. While cloud users can quickly start an application by using various data services, it can be difficult to configure and optimize these services to gain the most value from them. For cloud providers, managing every aspect of an ever-increasing set of data services, while meeting customer SLAs and minimizing operational cost is becoming more challenging. Cloud technology enables the collection of significant amounts of workload traces and system telemetry. With the progress in data science (DS) and machine learning (ML), it is feasible and desirable to utilize a data-driven, ML-based approach to automate various aspects of data services, resulting in the creation of autonomous data services. This paper presents our perspectives and insights on creating autonomous data services on Azure. It also covers the future endeavors we plan to undertake and unresolved issues that still need attention., Comment: SIGMOD Companion of the 2023 International Conference on Management of Data. 2023

This technical report describes the design and training of novel speculative decoding draft models, for accelerating the inference speeds of large language models in a production environment. By conditioning draft predictions on both context vectors and sampled tokens, we can train our speculators to efficiently predict high-quality n-grams, which the base model then accepts or rejects. This allows us to effectively predict multiple tokens per inference forward pass, accelerating wall-clock inference speeds of highly optimized base model implementations by a factor of 2-3x. We explore these initial results and describe next steps for further improvements., Comment: Original upload 4/29/24, updated 6/6/24 with additional references to concurrent work

In this paper, we present a novel derivative-free optimization framework for solving unconstrained stochastic optimization problems. Many problems in fields ranging from simulation optimization to reinforcement learning involve settings where only stochastic function values are obtained via an oracle with no available gradient information, necessitating the usage of derivative-free optimization methodologies. Our approach includes estimating gradients using stochastic function evaluations and integrating adaptive sampling techniques to control the accuracy in these stochastic approximations. We consider various gradient estimation techniques including standard finite difference, Gaussian smoothing, sphere smoothing, randomized coordinate finite difference, and randomized subspace finite difference methods. We provide theoretical convergence guarantees for our framework and analyze the worst-case iteration and sample complexities associated with each gradient estimation method. Finally, we demonstrate the empirical performance of the methods on logistic regression and nonlinear least squares problems.

Current electromyography (EMG) pattern recognition (PR) models have been shown to generalize poorly in unconstrained environments, setting back their adoption in applications such as hand gesture control. This problem is often due to limited training data, exacerbated by the use of supervised classification frameworks that are known to be suboptimal in such settings. In this work, we propose a shift to deep metric-based meta-learning in EMG PR to supervise the creation of meaningful and interpretable representations. We use a Siamese Deep Convolutional Neural Network (SDCNN) and contrastive triplet loss to learn an EMG feature embedding space that captures the distribution of the different classes. A nearest-centroid approach is subsequently employed for inference, relying on how closely a test sample aligns with the established data distributions. We derive a robust class proximity-based confidence estimator that leads to a better rejection of incorrect decisions, i.e. false positives, especially when operating beyond the training data domain. We show our approach's efficacy by testing the trained SDCNN's predictions and confidence estimations on unseen data, both in and out of the training domain. The evaluation metrics include the accuracy-rejection curve and the Kullback-Leibler divergence between the confidence distributions of accurate and inaccurate predictions. Outperforming comparable models on both metrics, our results demonstrate that the proposed meta-learning approach improves the classifier's precision in active decisions (after rejection), thus leading to better generalization and applicability., Comment: 11 pages, 9 figures, submitted to IEEE Transactions on Neural Networks and Learning Systems

Motivated by a number of applications in signal processing, we study the following question. Given samples of a multidimensional signal of the form \begin{align*} f(\bs\ell)=\sum_{k=1}^K a_k\exp(-i\langle \bs\ell, \w_k\rangle), \\ \w_1,\cdots,\w_k\in\mathbb{R}^q, \ \bs\ell\in \ZZ^q, \ |\bs\ell|

The transformative impact of machine learning, particularly Deep Learning (DL), on scientific and engineering domains is evident. In the context of computational fluid dynamics (CFD), Physics-Informed Neural Networks (PINNs) represent a significant innovation, enabling data-driven fluid simulations while incorporating physics-based laws described by partial differential equations (PDEs). While PINNs have demonstrated efficacy in various fluid flow scenarios, a noticeable gap exists in their application to simulate jet flows - an essential category in engineering. Jets, crucial for downburst outflow, ventilation, and heat transfer, lack comprehensive exploration through PINNs in existing literature. This study addresses this gap by focusing on the application of PINNs to simulate steady jet flows, specifically 2D planar turbulent jet flow scenarios. The novelty lies not only in adapting PINNs for simulating jet flows but also in overcoming challenges such as poor convergence during training, attributed to imbalances in loss terms. We propose a novel PINN architecture for Reynolds-Averaged Navier-Stokes (RANS) simulation of steady turbulent jet flows, without the need for turbulence models and simulation data. Additionally, an extended dynamic weighting strategy is introduced to enhance the balance of loss term contributions in the PINN, resulting in improved convergence and more accurate predictions., Comment: 17 pages

Let $G\leqslant\mathrm{Sym}(\Omega)$ be transitive, and let $S$ be an intersecting subset, namely, the ratio $xy^{-1}$ of any elements $x,y\in S$ fixes some point. An EKR-type problem is to characterize transitive groups $G\leqslant\mathrm{Sym}(\Omega)$ such that any intersecting set is upper bounded by $|G_\omega|$, where $\omega\in\Omega$. A nice result of Meagher-Spiga-Tiep (2016) tells us that if $G$ is 2-transitive, then indeed $|S|\leqslant|G_\omega|$. A natural next step would be to explore intersecting subsets for primitive groups and quasiprimitive groups. Our study in this paper shows that for quasiprimitive permutation groups, the size $|S|$ can be arbitrarily larger than $|G_\omega|$. We conjecture that for quasiprimitve groups, the upperbound for $|S|$ is $O(|G_\omega||\Omega|^{1\over2})$. As a starting point, we prove that ${|S|/(|G_\omega||\Omega|^{1\over2}})\leqslant{\sqrt2/2}$ for all quasiprimitive actions of the Suzuki groups $G=\mathrm{Sz}(q)$. To show that our conjectured upper bound is tight, we provide examples of groups for which ${|S|/(|G_\omega||\Omega|^{1\over2}})$ is arbitrarily close to ${\sqrt2/2}$. As far as general transitive groups concerned, infinity families of examples produced show that the ratio ${|S|/(|G_\omega||\Omega|^{1\over2}})$ can be arbitrarily large., Comment: 26 pages, 2 figures 1.Replace the Theorem 1.5 from 'intersecting subgroups of Suzuki groups' to '$\rho(G/\Omega)<1/\sqrt{2}$ when G is a Suzuki group'. 2.Remove Proposition 2.4 3. Add Examples2.5-2.6, Lemma 2.7-2.8

Zero-shot generalization (ZSG) to unseen dynamics is a major challenge for creating generally capable embodied agents. To address the broader challenge, we start with the simpler setting of contextual reinforcement learning (cRL), assuming observability of the context values that parameterize the variation in the system's dynamics, such as the mass or dimensions of a robot, without making further simplifying assumptions about the observability of the Markovian state. Toward the goal of ZSG to unseen variation in context, we propose the contextual recurrent state-space model (cRSSM), which introduces changes to the world model of Dreamer (v3) (Hafner et al., 2023). This allows the world model to incorporate context for inferring latent Markovian states from the observations and modeling the latent dynamics. Our approach is evaluated on two tasks from the CARL benchmark suite, which is tailored to study contextual RL. Our experiments show that such systematic incorporation of the context improves the ZSG of the policies trained on the "dreams" of the world model. We further find qualitatively that our approach allows Dreamer to disentangle the latent state from context, allowing it to extrapolate its dreams to the many worlds of unseen contexts. The code for all our experiments is available at https://github.com/sai-prasanna/dreaming_of_many_worlds., Comment: In Reinforcement Learning Conference, 2024. 33 pages

In this paper, we propose a modified version of the MedQA-USMLE dataset, named MEDQA-OPEN, which contains open-ended medical questions without options to mimic clinical scenarios, along with clinician-approved reasoned answers. Additionally, we implement a prompt driven by Chain of Thought (CoT) reasoning, CLINICR, to mirror the prospective process of incremental reasoning, reaching a correct response to medical questions. We empirically demonstrate how CLINICR outperforms the state-of-the-art 5-shot CoT-based prompt (Li\'evin et al., 2022). We also present an approach that mirrors real-life clinical practice by first exploring multiple differential diagnoses through MCQ-CLINICR and subsequently narrowing down to a final diagnosis using MCQ-ELIMINATIVE. Finally, emphasizing the importance of response verification in medical settings, we utilize a reward model mechanism, replacing the elimination process performed by MCQ-ELIMINATIVE., Comment: The paper is accepted in EMNLP 2024 Findings

This paper is an attempt to mitigate the beam squint happening due to frequency-dependent phase shifts in the wideband beamforming scenario, specifically in radar applications. The estimation of the direction of arrival is significant for precise target detection in radars. The undesirable beam squint effect due to the phase shift-only mechanism in conventional phased array systems, which becomes exacerbated when dealing with wide bandwidth signals, is analyzed for a large set of steering angles in this paper. An optimum baseband delay combined with the phase shift technique is proposed for wideband radar beamforming to mitigate beam squint effectively. This technique has been demonstrated to function properly with 1-GHz carrier frequency for signals with wide bandwidths of up to +/-250MHz and for steering angles ranging from 0 to 90 degrees., Comment: 6 pages, 5 figures, submitted and accepted for presentation at IEEE Radar Conference 2024

This paper introduces a new stochastic optimization method based on the regularized Fisher information matrix (FIM), named SOFIM, which can efficiently utilize the FIM to approximate the Hessian matrix for finding Newton's gradient update in large-scale stochastic optimization of machine learning models. It can be viewed as a variant of natural gradient descent, where the challenge of storing and calculating the full FIM is addressed through making use of the regularized FIM and directly finding the gradient update direction via Sherman-Morrison matrix inversion. Additionally, like the popular Adam method, SOFIM uses the first moment of the gradient to address the issue of non-stationary objectives across mini-batches due to heterogeneous data. The utilization of the regularized FIM and Sherman-Morrison matrix inversion leads to the improved convergence rate with the same space and time complexities as stochastic gradient descent (SGD) with momentum. The extensive experiments on training deep learning models using several benchmark image classification datasets demonstrate that the proposed SOFIM outperforms SGD with momentum and several state-of-the-art Newton optimization methods in term of the convergence speed for achieving the pre-specified objectives of training and test losses as well as test accuracy.

The use of emerging technologies like Virtual Reality (VR) in therapeutic settings has increased in the past few years. By incorporating VR, a mental health condition like depression can be assessed effectively, while also providing personalized motivation and meaningful engagement for treatment purposes. The integration of external sensors further enhances the engagement of the subjects with the VR scenes. This paper presents a comprehensive review of existing literature on the detection and treatment of depression using VR. It explores various types of VR scenes, external hardware, innovative metrics, and targeted user studies conducted by researchers and professionals in the field. The paper also discusses potential requirements for designing VR scenes specifically tailored for depression assessment and treatment, with the aim of guiding future practitioners in this area., Comment: 8 pages, 2 figures, 3 tables, Conference full paper

An indispensable ingredient for pair density wave (PDW) superconductivity is the presence of an attractive pairing interaction at finite momentum. Here, we show how this condition can be met with straightforward electron-density interactions in multiband systems. The electron-density interaction, when projected to the band basis, acquires form factors with nontrivial momentum dependence and thereby exhibits a potential tendency to a finite-momentum pairing instability. By applying a mean-field analysis to two simple multiband models, the checkerboard lattice and three-band Hubbard model, we find that PDW order can indeed become the leading instability if a strong nearest-neighbour attraction is present. Moreover, the condition for the transition from a uniform superconductor to a PDW superconductor is shown via a simple quantum geometric argument., Comment: 7 pages, 5 figures

It is well-known that the statistical performance of Lasso can suffer significantly when the covariates of interest have strong correlations. In particular, the prediction error of Lasso becomes much worse than computationally inefficient alternatives like Best Subset Selection. Due to a large conjectured computational-statistical tradeoff in the problem of sparse linear regression, it may be impossible to close this gap in general. In this work, we propose a natural sparse linear regression setting where strong correlations between covariates arise from unobserved latent variables. In this setting, we analyze the problem caused by strong correlations and design a surprisingly simple fix. While Lasso with standard normalization of covariates fails, there exists a heterogeneous scaling of the covariates with which Lasso will suddenly obtain strong provable guarantees for estimation. Moreover, we design a simple, efficient procedure for computing such a "smart scaling." The sample complexity of the resulting "rescaled Lasso" algorithm incurs (in the worst case) quadratic dependence on the sparsity of the underlying signal. While this dependence is not information-theoretically necessary, we give evidence that it is optimal among the class of polynomial-time algorithms, via the method of low-degree polynomials. This argument reveals a new connection between sparse linear regression and a special version of sparse PCA with a near-critical negative spike. The latter problem can be thought of as a real-valued analogue of learning a sparse parity. Using it, we also establish the first computational-statistical gap for the closely related problem of learning a Gaussian Graphical Model.

Algorithm unfolding or unrolling is the technique of constructing a deep neural network (DNN) from an iterative algorithm. Unrolled DNNs often provide better interpretability and superior empirical performance over standard DNNs in signal estimation tasks. An important theoretical question, which has only recently received attention, is the development of generalization error bounds for unrolled DNNs. These bounds deliver theoretical and practical insights into the performance of a DNN on empirical datasets that are distinct from, but sampled from, the probability density generating the DNN training data. In this paper, we develop novel generalization error bounds for a class of unrolled DNNs that are informed by a compound Gaussian prior. These compound Gaussian networks have been shown to outperform comparative standard and unfolded deep neural networks in compressive sensing and tomographic imaging problems. The generalization error bound is formulated by bounding the Rademacher complexity of the class of compound Gaussian network estimates with Dudley's integral. Under realistic conditions, we show that, at worst, the generalization error scales $\mathcal{O}(n\sqrt{\ln(n)})$ in the signal dimension and $\mathcal{O}(($Network Size$)^{3/2})$ in network size., Comment: 14 pages, 1 figure

Progress in the study of infinite-layer nickelates has always been highly linked to materials advances. In particular, the recent development of superconductivity via hole-doping was predicated on the controlled synthesis of Ni in a very high oxidation state, and subsequent topotactic reduction to a very low oxidation state, currently limited to epitaxial thin films. Here we demonstrate a process to combine these steps with a heterostructure which includes an epitaxial soluble buffer layer, enabling the release of freestanding membranes of (Nd,Sr)NiO2 encapsulated in SrTiO3, which serves as a protective layer. The membranes have comparable structural and electronic properties to that of optimized thin films, and range in lateral dimensions from millimeters to ~100 micron fragments, depending on the degree of strain released with respect to the initial substrate. The changes in the superconducting transition temperature associated with membrane release are quite similar to those reported for substrate and pressure variations, suggestive of a common underlying mechanism. These membranes structures should provide a versatile platform for a range of experimental studies and devices free from substrate constraints.

Distribution matching methods for language model alignment such as Generation with Distributional Control (GDC) and Distributional Policy Gradient (DPG) have not received the same level of attention in reinforcement learning from human feedback (RLHF) as contrastive methods such as Sequence Likelihood Calibration (SLiC), Direct Preference Optimization (DPO) and its variants. We identify high variance of the gradient estimate as the primary reason for the lack of success of these methods and propose a self-normalized baseline to reduce the variance. We further generalize the target distribution in DPG, GDC and DPO by using Bayes' rule to define the reward-conditioned posterior. The resulting approach, referred to as BRAIn - Bayesian Reward-conditioned Amortized Inference acts as a bridge between distribution matching methods and DPO and significantly outperforms prior art in summarization and Antropic HH tasks., Comment: Accepted at ICML 2024 (main conference)