OpenRaiser/Intern-Atlas huggingface dataset:
Fourier Analysis of Iterative Algorithms
Venue: arXiv cs.CC 2024
Year: 2024

We study a general class of nonlinear iterative algorithms which includes power iteration, belief propagation and approximate message passing, and many forms of gradient descent. When the input is a random matrix with i.i.d. entries, we use Boolean Fourier analysis to analyze these algorithms as low-degree polynomials in the entries of the input matrix. Each symmetrized Fourier character represents all monomials with a certain shape as specified by a small graph, which we call a Fourier diagram. We prove fundamental asymptotic properties of the Fourier diagrams: over the randomness of the input, all diagrams with cycles are negligible; the tree-shaped diagrams form a basis of asymptotically independent Gaussian vectors; and, when restricted to the trees, iterative algorithms exactly follow an idealized Gaussian dynamic. We use this to prove a state evolution formula, giving a "complete" asymptotic description of the algorithm's trajectory. The restriction to tree-shaped monomials mirrors the assumption of the cavity method, a 40-year-old non-rigorous technique in statistical physics which has served as one of the most important techniques in the field. We demonstrate how to implement cavity method derivations by 1) restricting the iteration to its tree approximation, and 2) observing that heuristic cavity method-type arguments hold rigorously on the simplified iteration. Our proofs use combinatorial arguments similar to the trace method from random matrix theory. Finally, we push the diagram analysis to a number of iterations that scales with the dimension $n$ of the input matrix, proving that the tree approximation still holds for a simple variant of power iteration all the way up to $n^{Ω(1)}$ iterations.
Anomaly Detection in Power Grids via Context-Agnostic Learning
Venue: arXiv cs.LG 2024
Year: 2024

An important tool grid operators use to safeguard against failures, whether naturally occurring or malicious, involves detecting anomalies in the power system SCADA data. In this paper, we aim to solve a real-time anomaly detection problem. Given time-series measurement values coming from a fixed set of sensors on the grid, can we identify anomalies in the network topology or measurement data? Existing methods, primarily optimization-based, mostly use only a single snapshot of the measurement values and do not scale well with the network size. Recent data-driven ML techniques have shown promise by using a combination of current and historical data for anomaly detection but generally do not consider physical attributes like the impact of topology or load/generation changes on sensor measurements and thus cannot accommodate regular context-variability in the historical data. To address this gap, we propose a novel context-aware anomaly detection algorithm, GridCAL, that considers the effect of regular topology and load/generation changes. This algorithm converts the real-time power flow measurements to context-agnostic values, which allows us to analyze measurement coming from different grid contexts in an aggregate fashion, enabling us to derive a unified statistical model that becomes the basis of anomaly detection. Through numerical simulations on networks up to 2383 nodes, we show that our approach is accurate, outperforming state-of-the-art approaches, and is computationally efficient.
A Novel Optimization-Based Collision Avoidance For Autonomous On-Orbit Assembly
Venue: arXiv cs.RO 2024
Year: 2024

The collision avoidance constraints are prominent as non-convex, non-differentiable, and challenging when defined in optimization-based motion planning problems. To overcome these issues, this paper presents a novel non-conservative collision avoidance technique using the notion of convex optimization to establish the distance between robotic spacecraft and space structures for autonomous on-orbit assembly operations. The proposed technique defines each ellipsoidal- and polyhedral-shaped object as the union of convex compact sets, each represented non-conservatively by a real-valued convex function. Then, the functions are introduced as a set of constraints to a convex optimization problem to produce a new set of differentiable constraints resulting from the optimality conditions. These new constraints are later fed into an optimal control problem to enforce collision avoidance where the motion planning for the autonomous on-orbit assembly takes place. Numerical experiments for two assembly scenarios in tight environments are presented to demonstrate the capability and effectiveness of the proposed technique. The results show that this framework leads to optimal non-conservative trajectories for robotic spacecraft in tight environments. Although developed for autonomous on-orbit assembly, this technique could be used for any generic motion planning problem where collision avoidance is crucial.
Goal Recognition via Linear Programming
Venue: arXiv cs.AI 2024
Year: 2024

Goal Recognition is the task by which an observer aims to discern the goals that correspond to plans that comply with the perceived behavior of subject agents given as a sequence of observations. Research on Goal Recognition as Planning encompasses reasoning about the model of a planning task, the observations, and the goals using planning techniques, resulting in very efficient recognition approaches. In this article, we design novel recognition approaches that rely on the Operator-Counting framework, proposing new constraints, and analyze their constraints' properties both theoretically and empirically. The Operator-Counting framework is a technique that efficiently computes heuristic estimates of cost-to-goal using Integer/Linear Programming (IP/LP). In the realm of theory, we prove that the new constraints provide lower bounds on the cost of plans that comply with observations. We also provide an extensive empirical evaluation to assess how the new constraints improve the quality of the solution, and we found that they are especially informed in deciding which goals are unlikely to be part of the solution. Our novel recognition approaches have two pivotal advantages: first, they employ new IP/LP constraints for efficiently recognizing goals; second, we show how the new IP/LP constraints can improve the recognition of goals under both partial and noisy observability.
Self-supervised Dataset Distillation: A Good Compression Is All You Need
Venue: arXiv cs.CV 2024
Year: 2024

Dataset distillation aims to compress information from a large-scale original dataset to a new compact dataset while striving to preserve the utmost degree of the original data informational essence. Previous studies have predominantly concentrated on aligning the intermediate statistics between the original and distilled data, such as weight trajectory, features, gradient, BatchNorm, etc. In this work, we consider addressing this task through the new lens of model informativeness in the compression stage on the original dataset pretraining. We observe that with the prior state-of-the-art SRe$^2$L, as model sizes increase, it becomes increasingly challenging for supervised pretrained models to recover learned information during data synthesis, as the channel-wise mean and variance inside the model are flatting and less informative. We further notice that larger variances in BN statistics from self-supervised models enable larger loss signals to update the recovered data by gradients, enjoying more informativeness during synthesis. Building on this observation, we introduce SC-DD, a simple yet effective Self-supervised Compression framework for Dataset Distillation that facilitates diverse information compression and recovery compared to traditional supervised learning schemes, further reaps the potential of large pretrained models with enhanced capabilities. Extensive experiments are conducted on CIFAR-100, Tiny-ImageNet and ImageNet-1K datasets to demonstrate the superiority of our proposed approach. The proposed SC-DD outperforms all previous state-of-the-art supervised dataset distillation methods when employing larger models, such as SRe$^2$L, MTT, TESLA, DC, CAFE, etc., by large margins under the same recovery and post-training budgets. Code is available at https://github.com/VILA-Lab/SRe2L/tree/main/SCDD/.
Manipulating Large Language Models to Increase Product Visibility
Venue: arXiv cs.IR 2024
Year: 2024

Large language models (LLMs) are increasingly being integrated into search engines to provide natural language responses tailored to user queries. Customers and end-users are also becoming more dependent on these models for quick and easy purchase decisions. In this work, we investigate whether recommendations from LLMs can be manipulated to enhance a product's visibility. We demonstrate that adding a strategic text sequence (STS) -- a carefully crafted message -- to a product's information page can significantly increase its likelihood of being listed as the LLM's top recommendation. To understand the impact of STS, we use a catalog of fictitious coffee machines and analyze its effect on two target products: one that seldom appears in the LLM's recommendations and another that usually ranks second. We observe that the strategic text sequence significantly enhances the visibility of both products by increasing their chances of appearing as the top recommendation. This ability to manipulate LLM-generated search responses provides vendors with a considerable competitive advantage and has the potential to disrupt fair market competition. Just as search engine optimization (SEO) revolutionized how webpages are customized to rank higher in search engine results, influencing LLM recommendations could profoundly impact content optimization for AI-driven search services. Code for our experiments is available at https://github.com/aounon/llm-rank-optimizer.
Trading Determinism for Noncommutativity in Edmonds' Problem
Venue: arXiv cs.CC 2024
Year: 2024

Let $X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k$ be a partitioned set of variables such that the variables in each part $X_i$ are noncommuting but for any $i\neq j$, the variables $x\in X_i$ commute with the variables $x'\in X_j$. Given as input a square matrix $T$ whose entries are linear forms over $\mathbb{Q}\langle{X}\rangle$, we consider the problem of checking if $T$ is invertible or not over the universal skew field of fractions of the partially commutative polynomial ring $\mathbb{Q}\langle{X}\rangle$ [Klep-Vinnikov-Volcic (2020)]. In this paper, we design a deterministic polynomial-time algorithm for this problem for constant $k$. The special case $k=1$ is the noncommutative Edmonds' problem (NSINGULAR) which has a deterministic polynomial-time algorithm by recent results [Garg-Gurvits-Oliveira-Wigderson (2016), Ivanyos-Qiao-Subrahmanyam (2018), Hamada-Hirai (2021)]. En-route, we obtain the first deterministic polynomial-time algorithm for the equivalence testing problem of $k$-tape \emph{weighted} automata (for constant $k$) resolving a long-standing open problem [Harju and Karhum"{a}ki(1991), Worrell (2013)]. Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set $X$ is zero or not [Worrell (2013)]. Decidability of this problem was established by Harju and Karhumäki (1991). Prior to this work, a \emph{randomized} polynomial-time algorithm for this problem was given by Worrell (2013) and, subsequently, a deterministic quasipolynomial-time algorithm was also developed [Arvind et al. (2021)].
ApproxDARTS: Differentiable Neural Architecture Search with Approximate Multipliers
Venue: arXiv cs.LG 2024
Year: 2024

Integrating the principles of approximate computing into the design of hardware-aware deep neural networks (DNN) has led to DNNs implementations showing good output quality and highly optimized hardware parameters such as low latency or inference energy. In this work, we present ApproxDARTS, a neural architecture search (NAS) method enabling the popular differentiable neural architecture search method called DARTS to exploit approximate multipliers and thus reduce the power consumption of generated neural networks. We showed on the CIFAR-10 data set that the ApproxDARTS is able to perform a complete architecture search within less than $10$ GPU hours and produce competitive convolutional neural networks (CNN) containing approximate multipliers in convolutional layers. For example, ApproxDARTS created a CNN showing an energy consumption reduction of (a) $53.84\%$ in the arithmetic operations of the inference phase compared to the CNN utilizing the native $32$-bit floating-point multipliers and (b) $5.97\%$ compared to the CNN utilizing the exact $8$-bit fixed-point multipliers, in both cases with a negligible accuracy drop. Moreover, the ApproxDARTS is $2.3\times$ faster than a similar but evolutionary algorithm-based method called EvoApproxNAS.
Accel-NASBench: Sustainable Benchmarking for Accelerator-Aware NAS
Venue: arXiv cs.LG 2024
Year: 2024

One of the primary challenges impeding the progress of Neural Architecture Search (NAS) is its extensive reliance on exorbitant computational resources. NAS benchmarks aim to simulate runs of NAS experiments at zero cost, remediating the need for extensive compute. However, existing NAS benchmarks use synthetic datasets and model proxies that make simplified assumptions about the characteristics of these datasets and models, leading to unrealistic evaluations. We present a technique that allows searching for training proxies that reduce the cost of benchmark construction by significant margins, making it possible to construct realistic NAS benchmarks for large-scale datasets. Using this technique, we construct an open-source bi-objective NAS benchmark for the ImageNet2012 dataset combined with the on-device performance of accelerators, including GPUs, TPUs, and FPGAs. Through extensive experimentation with various NAS optimizers and hardware platforms, we show that the benchmark is accurate and allows searching for state-of-the-art hardware-aware models at zero cost.
Learning Efficient and Fair Policies for Uncertainty-Aware Collaborative Human-Robot Order Picking
Venue: arXiv cs.RO 2024
Year: 2024

In collaborative human-robot order picking systems, human pickers and Autonomous Mobile Robots (AMRs) travel independently through a warehouse and meet at pick locations where pickers load items onto the AMRs. In this paper, we consider an optimization problem in such systems where we allocate pickers to AMRs in a stochastic environment. We propose a novel multi-objective Deep Reinforcement Learning (DRL) approach to learn effective allocation policies to maximize pick efficiency while also aiming to improve workload fairness amongst human pickers. In our approach, we model the warehouse states using a graph, and define a neural network architecture that captures regional information and effectively extracts representations related to efficiency and workload. We develop a discrete-event simulation model, which we use to train and evaluate the proposed DRL approach. In the experiments, we demonstrate that our approach can find non-dominated policy sets that outline good trade-offs between fairness and efficiency objectives. The trained policies outperform the benchmarks in terms of both efficiency and fairness. Moreover, they show good transferability properties when tested on scenarios with different warehouse sizes. The implementation of the simulation model, proposed approach, and experiments are published.
SurvMamba: State Space Model with Multi-grained Multi-modal Interaction for Survival Prediction
Venue: arXiv cs.CV 2024
Year: 2024

Multi-modal learning that combines pathological images with genomic data has significantly enhanced the accuracy of survival prediction. Nevertheless, existing methods have not fully utilized the inherent hierarchical structure within both whole slide images (WSIs) and transcriptomic data, from which better intra-modal representations and inter-modal integration could be derived. Moreover, many existing studies attempt to improve multi-modal representations through attention mechanisms, which inevitably lead to high complexity when processing high-dimensional WSIs and transcriptomic data. Recently, a structured state space model named Mamba emerged as a promising approach for its superior performance in modeling long sequences with low complexity. In this study, we propose Mamba with multi-grained multi-modal interaction (SurvMamba) for survival prediction. SurvMamba is implemented with a Hierarchical Interaction Mamba (HIM) module that facilitates efficient intra-modal interactions at different granularities, thereby capturing more detailed local features as well as rich global representations. In addition, an Interaction Fusion Mamba (IFM) module is used for cascaded inter-modal interactive fusion, yielding more comprehensive features for survival prediction. Comprehensive evaluations on five TCGA datasets demonstrate that SurvMamba outperforms other existing methods in terms of performance and computational cost.
FedAuxHMTL: Federated Auxiliary Hard-Parameter Sharing Multi-Task Learning for Network Edge Traffic Classification
Venue: arXiv cs.LG 2024
Year: 2024

Federated Learning (FL) has garnered significant interest recently due to its potential as an effective solution for tackling many challenges in diverse application scenarios, for example, data privacy in network edge traffic classification. Despite its recognized advantages, FL encounters obstacles linked to statistical data heterogeneity and labeled data scarcity during the training of single-task models for machine learning-based traffic classification, leading to hindered learning performance. In response to these challenges, adopting a hard-parameter sharing multi-task learning model with auxiliary tasks proves to be a suitable approach. Such a model has the capability to reduce communication and computation costs, navigate statistical complexities inherent in FL contexts, and overcome labeled data scarcity by leveraging knowledge derived from interconnected auxiliary tasks. This paper introduces a new framework for federated auxiliary hard-parameter sharing multi-task learning, namely, FedAuxHMTL. The introduced framework incorporates model parameter exchanges between edge server and base stations, enabling base stations from distributed areas to participate in the FedAuxHMTL process and enhance the learning performance of the main task-network edge traffic classification. Empirical experiments are conducted to validate and demonstrate the FedAuxHMTL's effectiveness in terms of accuracy, total global loss, communication costs, computing time, and energy consumption compared to its counterparts.
Persistent Classification: A New Approach to Stability of Data and Adversarial Examples
Venue: arXiv cs.LG 2024
Year: 2024

There are a number of hypotheses underlying the existence of adversarial examples for classification problems. These include the high-dimensionality of the data, high codimension in the ambient space of the data manifolds of interest, and that the structure of machine learning models may encourage classifiers to develop decision boundaries close to data points. This article proposes a new framework for studying adversarial examples that does not depend directly on the distance to the decision boundary. Similarly to the smoothed classifier literature, we define a (natural or adversarial) data point to be $(γ,σ)$-stable if the probability of the same classification is at least $γ$ for points sampled in a Gaussian neighborhood of the point with a given standard deviation $σ$. We focus on studying the differences between persistence metrics along interpolants of natural and adversarial points. We show that adversarial examples have significantly lower persistence than natural examples for large neural networks in the context of the MNIST and ImageNet datasets. We connect this lack of persistence with decision boundary geometry by measuring angles of interpolants with respect to decision boundaries. Finally, we connect this approach with robustness by developing a manifold alignment gradient metric and demonstrating the increase in robustness that can be achieved when training with the addition of this metric.
Towards a Robust Soft Baby Robot With Rich Interaction Ability for Advanced Machine Learning Algorithms
Venue: arXiv cs.RO 2024
Year: 2024

Advanced machine learning algorithms require platforms that are extremely robust and equipped with rich sensory feedback to handle extensive trial-and-error learning without relying on strong inductive biases. Traditional robotic designs, while well-suited for their specific use cases, are often fragile when used with these algorithms. To address this gap -- and inspired by the vision of enabling curiosity-driven baby robots -- we present a novel robotic limb designed from scratch. Our design has a hybrid soft-hard structure, high redundancy with rich non-contact sensors (exclusively cameras), and easily replaceable failure points. Proof-of-concept experiments using two contemporary reinforcement learning algorithms on a physical prototype demonstrate that our design is able to succeed in a simple target-finding task even under simulated sensor failures, all with minimal human oversight during extended learning periods. We believe this design represents a concrete step toward more tailored robotic designs for achieving general-purpose, generally intelligent robots.
The Impact of School and Family Networks on COVID-19 Infections Among Dutch Students: A Study Using Population-Level Registry Data
Venue: arXiv cs.SI 2024
Year: 2024

Understanding the impact of different social interactions is key to improving epidemic models. Here, we use extensive registry data -- including PCR test results and population-level networks -- to investigate the impact of school, family, and other social contacts on SARS-CoV-2 transmission in the Netherlands (June 2020--October 2021). We isolate and compare different contexts of potential SARS-CoV-2 transmission by matching pairs of students based on their attendance at the same or different primary school (in 2020) and secondary school (in 2021) and their geographic proximity. We then calculated the probability of temporally associated infections -- i.e. the probability of both students testing positive within a 14-day period. Our results highlight the relative importance of household and family transmission in the spread of SARS-CoV-2 compared to school settings. The probability of temporally associated infections for siblings and parent-child pairs living in the same household was 22.6--23.2\%, and 4.7--7.9\% for family members living in different household. In contrast, the probability of temporally associated infections was 0.52\% for pairs of students living nearby but not attending the same primary or secondary school, 0.66\% for pairs attending different secondary schools but having attended the same primary school, and 1.65\% for pairs attending the same secondary school. Finally, we used multilevel regression analyses to examine how individual, school, and geographic factors contribute to transmission risk. We found that the largest differences in transmission probabilities were due to unobserved individual (60\%) and school-level (35\%) factors. Only a small proportion (3\%) could be attributed to geographic proximity of students or to school size, denomination, or the median income of the school area.