OpenRaiser/Intern-Atlas huggingface dataset:
Probability flow solution of the Fokker-Planck equation
Venue: arXiv cs.LG 2023
Year: 2023

The method of choice for integrating the time-dependent Fokker-Planck equation in high-dimension is to generate samples from the solution via integration of the associated stochastic differential equation. Here, we study an alternative scheme based on integrating an ordinary differential equation that describes the flow of probability. Acting as a transport map, this equation deterministically pushes samples from the initial density onto samples from the solution at any later time. Unlike integration of the stochastic dynamics, the method has the advantage of giving direct access to quantities that are challenging to estimate from trajectories alone, such as the probability current, the density itself, and its entropy. The probability flow equation depends on the gradient of the logarithm of the solution (its "score"), and so is a-priori unknown. To resolve this dependence, we model the score with a deep neural network that is learned on-the-fly by propagating a set of samples according to the instantaneous probability current. We show theoretically that the proposed approach controls the KL divergence from the learned solution to the target, while learning on external samples from the stochastic differential equation does not control either direction of the KL divergence. Empirically, we consider several high-dimensional Fokker-Planck equations from the physics of interacting particle systems. We find that the method accurately matches analytical solutions when they are available as well as moments computed via Monte-Carlo when they are not. Moreover, the method offers compelling predictions for the global entropy production rate that out-perform those obtained from learning on stochastic trajectories, and can effectively capture non-equilibrium steady-state probability currents over long time intervals.
Memory-efficient model-based deep learning with convergence and robustness guarantees
Venue: arXiv cs.CV 2023
Year: 2023

Computational imaging has been revolutionized by compressed sensing algorithms, which offer guaranteed uniqueness, convergence, and stability properties. Model-based deep learning methods that combine imaging physics with learned regularization priors have emerged as more powerful alternatives for image recovery. The main focus of this paper is to introduce a memory efficient model-based algorithm with similar theoretical guarantees as CS methods. The proposed iterative algorithm alternates between a gradient descent involving the score function and a conjugate gradient algorithm to encourage data consistency. The score function is modeled as a monotone convolutional neural network. Our analysis shows that the monotone constraint is necessary and sufficient to enforce the uniqueness of the fixed point in arbitrary inverse problems. In addition, it also guarantees the convergence to a fixed point, which is robust to input perturbations. We introduce two implementations of the proposed MOL framework, which differ in the way the monotone property is imposed. The first approach enforces a strict monotone constraint, while the second one relies on an approximation. The guarantees are not valid for the second approach in the strict sense. However, our empirical studies show that the convergence and robustness of both approaches are comparable, while the less constrained approximate implementation offers better performance. The proposed deep equilibrium formulation is significantly more memory efficient than unrolled methods, which allows us to apply it to 3D or 2D+time problems that current unrolled algorithms cannot handle.
Persistent Homology for Resource Coverage: A Case Study of Access to Polling Sites
Venue: arXiv cs.CG 2023
Year: 2023

It is important to choose the geographical distributions of public resources in a fair and equitable manner. However, it is complicated to quantify the equity of such a distribution; important factors include distances to resource sites, availability of transportation, and ease of travel. We use persistent homology, which is a tool from topological data analysis, to study the effective availability and coverage of polling sites. The information from persistent homology allows us to infer holes in the distribution of polling sites. We analyze and compare the coverage of polling sites in Los Angeles County and five cities (Atlanta, Chicago, Jacksonville, New York City, and Salt Lake City), and we conclude that computation of persistent homology appears to be a reasonable approach to analyzing resource coverage.
On the Complexity of Sampling Redistricting Plans
Venue: arXiv cs.DS 2023
Year: 2023

A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination [DeFord-Duchin-Solomon'21]-a popular Markov chain to sample redistricting plans-is exponentially slow mixing on simple subgraph of $\mathbb{Z}_2.$ We show an alternative way to sample balance, compact and contiguous redistricting plans using a "relaxed" version of ReCom and rejection sampling.
Several constructions of optimal LCD codes over small finite fields
Venue: arXiv cs.IT 2023
Year: 2023

Linear complementary dual (LCD) codes are linear codes which intersect their dual codes trivially, which have been of interest and extensively studied due to their practical applications in computational complexity and information protection. In this paper, we give some methods for constructing LCD codes over small finite fields by modifying some typical methods for constructing linear codes. We show that all odd-like binary LCD codes, ternary LCD codes and quaternary Hermitian LCD codes can be constructed using the modified methods. Our results improve the known lower bounds on the largest minimum distances of LCD codes. Furthermore, we give two counterexamples to disprove the conjecture proposed by Bouyuklieva (Des. Codes Cryptogr. 89(11): 2445-2461, 2021).
Learning to Estimate Shapley Values with Vision Transformers
Venue: arXiv cs.CV 2023
Year: 2023

Transformers have become a default architecture in computer vision, but understanding what drives their predictions remains a challenging problem. Current explanation approaches rely on attention values or input gradients, but these provide a limited view of a model's dependencies. Shapley values offer a theoretically sound alternative, but their computational cost makes them impractical for large, high-dimensional models. In this work, we aim to make Shapley values practical for vision transformers (ViTs). To do so, we first leverage an attention masking approach to evaluate ViTs with partial information, and we then develop a procedure to generate Shapley value explanations via a separate, learned explainer model. Our experiments compare Shapley values to many baseline methods (e.g., attention rollout, GradCAM, LRP), and we find that our approach provides more accurate explanations than existing methods for ViTs.
Intrinsic dimensionality and generalization properties of the $\mathcal{R}$-norm inductive bias
Venue: arXiv cs.LG 2023
Year: 2023

We study the structural and statistical properties of $\mathcal{R}$-norm minimizing interpolants of datasets labeled by specific target functions. The $\mathcal{R}$-norm is the basis of an inductive bias for two-layer neural networks, recently introduced to capture the functional effect of controlling the size of network weights, independently of the network width. We find that these interpolants are intrinsically multivariate functions, even when there are ridge functions that fit the data, and also that the $\mathcal{R}$-norm inductive bias is not sufficient for achieving statistically optimal generalization for certain learning problems. Altogether, these results shed new light on an inductive bias that is connected to practical neural network training.
Blades: A Unified Benchmark Suite for Byzantine Attacks and Defenses in Federated Learning
Venue: arXiv cs.CR 2023
Year: 2023

Federated learning (FL) facilitates distributed training across different IoT and edge devices, safeguarding the privacy of their data. The inherent distributed structure of FL introduces vulnerabilities, especially from adversarial devices aiming to skew local updates to their advantage. Despite the plethora of research focusing on Byzantine-resilient FL, the academic community has yet to establish a comprehensive benchmark suite, pivotal for impartial assessment and comparison of different techniques. This paper presents Blades, a scalable, extensible, and easily configurable benchmark suite that supports researchers and developers in efficiently implementing and validating novel strategies against baseline algorithms in Byzantine-resilient FL. Blades contains built-in implementations of representative attack and defense strategies and offers a user-friendly interface that seamlessly integrates new ideas. Using Blades, we re-evaluate representative attacks and defenses on wide-ranging experimental configurations (approximately 1,500 trials in total). Through our extensive experiments, we gained new insights into FL robustness and highlighted previously overlooked limitations due to the absence of thorough evaluations and comparisons of baselines under various attack settings.
Object as a Service (OaaS): Enabling Object Abstraction in Serverless Clouds
Venue: arXiv cs.DC 2023
Year: 2023

Function as a Service (FaaS) paradigm is becoming widespread and is envisioned as the next generation of cloud systems that mitigate the burden for programmers and cloud solution architects. However, the FaaS abstraction only makes the cloud resource management aspects transparent but does not deal with the application data aspects. As such, developers have to undergo the burden of managing the application data, often via separate cloud services (e.g., AWS S3). Similarly, the FaaS abstraction does not natively support function workflow, hence, the developers often have to work with workflow orchestration services (e.g., AWS Step Functions) to build workflows. Moreover, they have to explicitly navigate the data throughout the workflow. To overcome these problems of FaaS, we design a higher-level cloud programming abstraction that hides the complexities and mitigate the burden of developing cloud-native application development. We borrow the notion of object from object-oriented programming and propose a new abstraction level atop the function abstraction, known as Object as a Service (OaaS). OaaS encapsulates the application data and function into the object abstraction and relieves the developers from resource and data management burdens. It also unlocks opportunities for built-in optimization features, such as software reusability, data locality, and caching. OaaS natively supports dataflow programming such that developers define a workflow of functions transparently without getting involved in data navigation, synchronization, and parallelism aspects. We implemented a prototype of the OaaS platform and evaluated it under real-world settings against state-of-the-art platforms regarding the imposed overhead, scalability, and ease of use. The results demonstrate that OaaS streamlines cloud programming and offers scalability with an insignificant overhead to the underlying cloud system.
Memorization-Dilation: Modeling Neural Collapse Under Label Noise
Venue: arXiv cs.LG 2023
Year: 2023

The notion of neural collapse refers to several emergent phenomena that have been empirically observed across various canonical classification problems. During the terminal phase of training a deep neural network, the feature embedding of all examples of the same class tend to collapse to a single representation, and the features of different classes tend to separate as much as possible. Neural collapse is often studied through a simplified model, called the unconstrained feature representation, in which the model is assumed to have "infinite expressivity" and can map each data point to any arbitrary representation. In this work, we propose a more realistic variant of the unconstrained feature representation that takes the limited expressivity of the network into account. Empirical evidence suggests that the memorization of noisy data points leads to a degradation (dilation) of the neural collapse. Using a model of the memorization-dilation (M-D) phenomenon, we show one mechanism by which different losses lead to different performances of the trained network on noisy data. Our proofs reveal why label smoothing, a modification of cross-entropy empirically observed to produce a regularization effect, leads to improved generalization in classification tasks.
Exploring the Intersection between Neural Architecture Search and Continual Learning
Venue: arXiv cs.AI 2023
Year: 2023

Despite the significant advances achieved in Artificial Neural Networks (ANNs), their design process remains notoriously tedious, depending primarily on intuition, experience and trial-and-error. This human-dependent process is often time-consuming and prone to errors. Furthermore, the models are generally bound to their training contexts, with no considerations to their surrounding environments. Continual adaptiveness and automation of neural networks is of paramount importance to several domains where model accessibility is limited after deployment (e.g IoT devices, self-driving vehicles, etc.). Additionally, even accessible models require frequent maintenance post-deployment to overcome issues such as Concept/Data Drift, which can be cumbersome and restrictive. By leveraging and combining approaches from Neural Architecture Search (NAS) and Continual Learning (CL), more robust and adaptive agents can be developed. This study conducts the first extensive review on the intersection between NAS and CL, formalizing the prospective Continually-Adaptive Neural Networks (CANNs) paradigm and outlining research directions for lifelong autonomous ANNs.
GPU-parallelisation of wavelet-based grid adaptation for fast finite volume modelling: application to shallow water flows
Venue: arXiv cs.CE 2023
Year: 2023

Wavelet-based grid adaptation driven by the "multiresolution analysis" (MRA) of the Haar wavelet (HW) allows to devise an adaptive first-order finite volume (FV1) model (HWFV1) that can readily preserve the modelling fidelity of its reference uniform-grid FV1 counterpart. However, the MRA incurs a high computational cost as it involves "encoding" (coarsening), "decoding" (refining), analysing and traversing modelled data across a deep hierarchy of nested, uniform grids. GPU-parallelisation of the MRA is needed to reduce its computational cost, but its algorithmic structure (1) hinders coalesced memory access on the GPU, and (2) involves an inherently sequential tree traversal problem. This work redesigns the algorithmic structure of the MRA in order to parallelise it on the GPU, addressing (1) by applying Z-order space-filling curves and addressing (2) by adopting a parallel tree traversal algorithm. This results in a GPU-parallelised HWFV1 model (GPU-HWFV1). GPU-HWFV1 is verified against its CPU predecessor (CPU-HWFV1) and its GPU-parallelised reference uniform-grid counterpart (GPU-FV1) over five shallow water flow test cases. GPU-HWFV1 preserves the modelling fidelity of GPU-FV1 while being up to 30 times faster. Compared to CPU-HWFV1, it is up to 200 times faster, suggesting the GPU-parallelised MRA could be used to speed up other FV1 models.
Mining Multi-Label Samples from Single Positive Labels
Venue: arXiv cs.LG 2023
Year: 2023

Conditional generative adversarial networks (cGANs) have shown superior results in class-conditional generation tasks. To simultaneously control multiple conditions, cGANs require multi-label training datasets, where multiple labels can be assigned to each data instance. Nevertheless, the tremendous annotation cost limits the accessibility of multi-label datasets in real-world scenarios. Therefore, in this study we explore the practical setting called the single positive setting, where each data instance is annotated by only one positive label with no explicit negative labels. To generate multi-label data in the single positive setting, we propose a novel sampling approach called single-to-multi-label (S2M) sampling, based on the Markov chain Monte Carlo method. As a widely applicable "add-on" method, our proposed S2M sampling method enables existing unconditional and conditional GANs to draw high-quality multi-label data with a minimal annotation cost. Extensive experiments on real image datasets verify the effectiveness and correctness of our method, even when compared to a model trained with fully annotated datasets.
ChordMixer: A Scalable Neural Attention Model for Sequences with Different Lengths
Venue: arXiv cs.LG 2023
Year: 2023

Sequential data naturally have different lengths in many domains, with some very long sequences. As an important modeling tool, neural attention should capture long-range interaction in such sequences. However, most existing neural attention models admit only short sequences, or they have to employ chunking or padding to enforce a constant input length. Here we propose a simple neural network building block called ChordMixer which can model the attention for long sequences with variable lengths. Each ChordMixer block consists of a position-wise rotation layer without learnable parameters and an element-wise MLP layer. Repeatedly applying such blocks forms an effective network backbone that mixes the input signals towards the learning targets. We have tested ChordMixer on the synthetic adding problem, long document classification, and DNA sequence-based taxonomy classification. The experiment results show that our method substantially outperforms other neural attention models.
Coordinating Monetary Contributions in Participatory Budgeting
Venue: arXiv cs.GT 2023
Year: 2023

We formalize a framework for coordinating funding and selecting projects, the costs of which are shared among agents with quasi-linear utility functions and individual budgets. Our model contains the classical discrete participatory budgeting model as a special case, while capturing other useful scenarios. We propose several important axioms and objectives and study how well they can be simultaneously satisfied. We show that whereas welfare maximization admits an FPTAS, welfare maximization subject to a natural and very weak participation requirement leads to a strong inapproximability. This result is bypassed if we consider some natural restricted valuations, namely laminar single-minded valuations and symmetric valuations. Our analysis for the former restriction leads to the discovery of a new class of tractable instances for the Set Union Knapsack problem, a classical problem in combinatorial optimization.
Graph Neural Networks Intersect Probabilistic Graphical Models: A Survey
Venue: arXiv cs.AI 2023
Year: 2023

Graphs are a powerful data structure to represent relational data and are widely used to describe complex real-world data structures. Probabilistic Graphical Models (PGMs) have been well-developed in the past years to mathematically model real-world scenarios in compact graphical representations of distributions of variables. Graph Neural Networks (GNNs) are new inference methods developed in recent years and are attracting growing attention due to their effectiveness and flexibility in solving inference and learning problems over graph-structured data. These two powerful approaches have different advantages in capturing relations from observations and how they conduct message passing, and they can benefit each other in various tasks. In this survey, we broadly study the intersection of GNNs and PGMs. Specifically, we first discuss how GNNs can benefit from learning structured representations in PGMs, generate explainable predictions by PGMs, and how PGMs can infer object relationships. Then we discuss how GNNs are implemented in PGMs for more efficient inference and structure learning. In the end, we summarize the benchmark datasets used in recent studies and discuss promising future directions.
Satellite-based high-resolution maps of cocoa planted area for Côte d'Ivoire and Ghana
Venue: arXiv cs.CV 2023
Year: 2023

Côte d'Ivoire and Ghana, the world's largest producers of cocoa, account for two thirds of the global cocoa production. In both countries, cocoa is the primary perennial crop, providing income to almost two million farmers. Yet precise maps of cocoa planted area are missing, hindering accurate quantification of expansion in protected areas, production and yields, and limiting information available for improved sustainability governance. Here, we combine cocoa plantation data with publicly available satellite imagery in a deep learning framework and create high-resolution maps of cocoa plantations for both countries, validated in situ. Our results suggest that cocoa cultivation is an underlying driver of over 37% and 13% of forest loss in protected areas in Côte d'Ivoire and Ghana, respectively, and that official reports substantially underestimate the planted area, up to 40% in Ghana. These maps serve as a crucial building block to advance understanding of conservation and economic development in cocoa producing regions.
Image-based Treatment Effect Heterogeneity
Venue: arXiv cs.LG 2023
Year: 2023

Randomized controlled trials (RCTs) are considered the gold standard for estimating the average treatment effect (ATE) of interventions. One use of RCTs is to study the causes of global poverty -- a subject explicitly cited in the 2019 Nobel Memorial Prize awarded to Duflo, Banerjee, and Kremer "for their experimental approach to alleviating global poverty." Because the ATE is a population summary, anti-poverty experiments often seek to unpack the effect variation around the ATE by conditioning (CATE) on tabular variables such as age and ethnicity that were measured during the RCT data collection. Although such variables are key to unpacking CATE, using only such variables may fail to capture historical, geographical, or neighborhood-specific contributors to effect variation, as tabular RCT data are often only observed near the time of the experiment. In global poverty research, when the location of the experiment units is approximately known, satellite imagery can provide a window into such factors important for understanding heterogeneity. However, there is no method that specifically enables applied researchers to analyze CATE from images. In this paper, using a deep probabilistic modeling framework, we develop such a method that estimates latent clusters of images by identifying images with similar treatment effects distributions. Our interpretable image CATE model also includes a sensitivity factor that quantifies the importance of image segments contributing to the effect cluster prediction. We compare the proposed methods against alternatives in simulation; also, we show how the model works in an actual RCT, estimating the effects of an anti-poverty intervention in northern Uganda and obtaining a posterior predictive distribution over effects for the rest of the country where no experimental data was collected. We make all models available in open-source software.