OpenRaiser/Intern-Atlas huggingface dataset:
Universal Approximation Power of Deep Residual Neural Networks via Nonlinear Control Theory
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we explain the universal approximation capabilities of deep residual neural networks through geometric nonlinear control. Inspired by recent work establishing links between residual networks and control systems, we provide a general sufficient condition for a residual network to have the power of universal approximation by asking the activation function, or one of its derivatives, to satisfy a quadratic differential equation. Many activation functions used in practice satisfy this assumption, exactly or approximately, and we show this property to be sufficient for an adequately deep neural network with $n+1$ neurons per layer to approximate arbitrarily well, on a compact set and with respect to the supremum norm, any continuous function from $\mathbb{R}^n$ to $\mathbb{R}^n$. We further show this result to hold for very simple architectures for which the weights only need to assume two values. The first key technical contribution consists of relating the universal approximation problem to controllability of an ensemble of control systems corresponding to a residual network and to leverage classical Lie algebraic techniques to characterize controllability. The second technical contribution is to identify monotonicity as the bridge between controllability of finite ensembles and uniform approximability on compact sets.
On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs
Venue: arXiv cs.DM 2024
Year: 2024

We introduce efficient algorithms for approximate sampling from symmetric Gibbs distributions on the sparse random (hyper)graph. The examples we consider include (but are not restricted to) important distributions on spin systems and spin-glasses such as the q state antiferromagnetic Potts model for $q\geq 2$, including the colourings, the uniform distributions over the Not-All-Equal solutions of random k-CNF formulas. Finally, we present an algorithm for sampling from the spin-glass distribution called the k-spin model. To our knowledge this is the first, rigorously analysed, efficient algorithm for spin-glasses which operates in a non trivial range of the parameters. Our approach builds on the one that was introduced in [Efthymiou: SODA 2012]. For a symmetric Gibbs distribution $μ$ on a random (hyper)graph whose parameters are within an certain range, our algorithm has the following properties: with probability $1-o(1)$ over the input instances, it generates a configuration which is distributed within total variation distance $n^{-Ω(1)}$ from $μ$. The time complexity is $O((n\log n)^2)$. The algorithm requires a range of the parameters which, for the graph case, coincide with the tree-uniqueness region, parametrised w.r.t. the expected degree d. For the hypergraph case, where uniqueness is less restrictive, we go beyond uniqueness. Our approach utilises in a novel way the notion of contiguity between Gibbs distributions and the so-called teacher-student model.
String Sanitization Under Edit Distance: Improved and Generalized
Venue: arXiv cs.DS 2024
Year: 2024

Let $W$ be a string of length $n$ over an alphabet $Σ$, $k$ be a positive integer, and $\mathcal{S}$ be a set of length-$k$ substrings of $W$. The ETFS problem asks us to construct a string $X_{\mathrm{ED}}$ such that: (i) no string of $\mathcal{S}$ occurs in $X_{\mathrm{ED}}$; (ii) the order of all other length-$k$ substrings over $Σ$ (and thus the frequency) is the same in $W$ and in $X_{\mathrm{ED}}$; and (iii) $X_{\mathrm{ED}}$ has minimal edit distance to $W$. When $W$ represents an individual's data and $\mathcal{S}$ represents a set of confidential patterns, the ETFS problem asks for transforming $W$ to preserve its privacy and its utility [Bernardini et al., ECML PKDD 2019]. ETFS can be solved in $\mathcal{O}(n^2k)$ time [Bernardini et al., CPM 2020]. The same paper shows that ETFS cannot be solved in $\mathcal{O}(n^{2-δ})$ time, for any $δ>0$, unless the Strong Exponential Time Hypothesis (SETH) is false. Our main results can be summarized as follows: (i) an $\mathcal{O}(n^2\log^2k)$-time algorithm to solve ETFS; and (ii) an $\mathcal{O}(n^2\log^2n)$-time algorithm to solve AETFS, a generalization of ETFS in which the elements of $\mathcal{S}$ can have arbitrary lengths. Our algorithms are thus optimal up to polylogarithmic factors, unless SETH fails. Beyond string sanitization, our techniques may inspire solutions to other problems related to regular expressions or context-free grammars.
Optimal Algorithm for the Planar Two-Center Problem
Venue: arXiv cs.CG 2024
Year: 2024

We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set $S$ of $n$ points in the plane and the goal is to find two smallest congruent disks whose union contains all points of $S$. A longstanding open problem has been to obtain an $O(n\log n)$-time algorithm for planar two-center, matching the $Ω(n\log n)$ lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in $O(n\log^2 n)$ time. In this paper, we present an $O(n\log n)$-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.
A Deep Ordinal Distortion Estimation Approach for Distortion Rectification
Venue: arXiv cs.CV 2024
Year: 2024

Distortion is widely existed in the images captured by popular wide-angle cameras and fisheye cameras. Despite the long history of distortion rectification, accurately estimating the distortion parameters from a single distorted image is still challenging. The main reason is these parameters are implicit to image features, influencing the networks to fully learn the distortion information. In this work, we propose a novel distortion rectification approach that can obtain more accurate parameters with higher efficiency. Our key insight is that distortion rectification can be cast as a problem of learning an ordinal distortion from a single distorted image. To solve this problem, we design a local-global associated estimation network that learns the ordinal distortion to approximate the realistic distortion distribution. In contrast to the implicit distortion parameters, the proposed ordinal distortion have more explicit relationship with image features, and thus significantly boosts the distortion perception of neural networks. Considering the redundancy of distortion information, our approach only uses a part of distorted image for the ordinal distortion estimation, showing promising applications in the efficient distortion rectification. To our knowledge, we first unify the heterogeneous distortion parameters into a learning-friendly intermediate representation through ordinal distortion, bridging the gap between image feature and distortion rectification. The experimental results demonstrate that our approach outperforms the state-of-the-art methods by a significant margin, with approximately 23% improvement on the quantitative evaluation while displaying the best performance on visual appearance. The code is available at https://github.com/KangLiao929/OrdinalDistortion.
Competitive Demand Learning: A Non-cooperative Pricing Algorithm with Coordinated Price Experimentation
Venue: arXiv cs.GT 2024
Year: 2024

We consider a periodical equilibrium pricing problem for multiple firms over a planning horizon of T periods. At each period, firms set their selling prices and receive stochastic demand from consumers. Firms do not know their underlying demand curve, but they wish to determine the selling prices to maximize total revenue under competition. Hence, they have to do some price experiments such that the observed demand data are informative to make price decisions. However, uncoordinated price updating can render the demand information gathered by price experimentation less informative or inaccurate. We design a nonparametric learning algorithm to facilitate coordinated dynamic pricing, in which competitive firms estimate their demand functions based on observations and adjust their pricing strategies in a prescribed manner. We show that the pricing decisions, determined by estimated demand functions, converge to underlying equilibrium as time progresses. We obtain a bound of the revenue difference that has an order of O(F^2 T^3/4) and a regret bound that has an order of O(F T^1/2) with respect to the number of the competitive firms F and T . We also develop a modified algorithm to handle the situation where some firms may have the knowledge of the demand curve.
Deep Domain Adaptation for Ordinal Regression of Pain Intensity Estimation Using Weakly-Labelled Videos
Venue: arXiv cs.CV 2024
Year: 2024

Estimation of pain intensity from facial expressions captured in videos has an immense potential for health care applications. Given the challenges related to subjective variations of facial expressions, and operational capture conditions, the accuracy of state-of-the-art DL models for recognizing facial expressions may decline. Domain adaptation has been widely explored to alleviate the problem of domain shifts that typically occur between video data captured across various source and target domains. Moreover, given the laborious task of collecting and annotating videos, and subjective bias due to ambiguity among adjacent intensity levels, weakly-supervised learning is gaining attention in such applications. State-of-the-art WSL models are typically formulated as regression problems, and do not leverage the ordinal relationship among pain intensity levels, nor temporal coherence of multiple consecutive frames. This paper introduces a new DL model for weakly-supervised DA with ordinal regression that can be adapted using target domain videos with coarse labels provided on a periodic basis. The WSDA-OR model enforces ordinal relationships among intensity levels assigned to target sequences, and associates multiple relevant frames to sequence-level labels. In particular, it learns discriminant and domain-invariant feature representations by integrating multiple instance learning with deep adversarial DA, where soft Gaussian labels are used to efficiently represent the weak ordinal sequence-level labels from target domain. The proposed approach was validated using RECOLA video dataset as fully-labeled source domain data, and UNBC-McMaster shoulder pain video dataset as weakly-labeled target domain data. We have also validated WSDA-OR on BIOVID and Fatigue datasets for sequence level estimation.
A VCG-based Fair Incentive Mechanism for Federated Learning
Venue: arXiv cs.GT 2024
Year: 2024

The enduring value of the Vickrey-Clarke-Groves (VCG) mechanism has been highlighted due to its adoption by Facebook ad auctions. Our research delves into its utility in the collaborative virtual goods production (CVGP) game, which finds application in realms like federated learning and crowdsourcing, in which bidders take on the roles of suppliers rather than consumers. We introduce the Procurement-VCG (PVCG) sharing rule into existing VCG mechanisms such that they can handle capacity limits and the continuous strategy space characteristic of the reverse auction setting in CVGP games. Our main theoretical contribution provides mathematical proofs to show that PVCG is the first in the CVGP game context to simultaneously achieve truthfulness, Pareto efficiency, individual rationality, and weak budget balance. These properties suggest the potential for Pareto-efficient production in the digital planned economy. Moreover, to compute the PVCG payments in a noisy economic environment, we propose the Report-Interpolation-Maximization (RIM) method. RIM facilitates the learning of the optimal procurement level and PVCG payments through iterative interactions with suppliers.
Institutional Grammar 2.0 Codebook
Venue: arXiv cs.MA 2024
Year: 2024

The Grammar of Institutions, or Institutional Grammar, is an established approach to encode policy information in terms of institutional statements based on a set of pre-defined syntactic components. This codebook provides coding guidelines for a revised version of the Institutional Grammar, the Institutional Grammar 2.0 (IG 2.0). IG 2.0 is a specification that aims at facilitating the encoding of policy to meet varying analytical objectives. To this end, it revises the grammar with respect to comprehensiveness, flexibility, and specificity by offering multiple levels of expressiveness (IG Core, IG Extended, IG Logico). In addition to the encoding of regulative statements, it further introduces the encoding of constitutive institutional statements, as well as statements that exhibit both constitutive and regulative characteristics. Introducing those aspects, the codebook initially covers fundamental concepts of IG 2.0, before providing an overview of pre-coding steps relevant for document preparation. Detailed coding guidelines are provided for both regulative and constitutive statements across all levels of expressiveness, along with the encoding guidelines for statements of mixed form -- hybrid and polymorphic institutional statements. The document further provides an overview of taxonomies used in the encoding process and referred to throughout the codebook. The codebook concludes with a summary and discussion of relevant considerations to facilitate the coding process. An initial Reader's Guide helps the reader tailor the content to her interest. Note that this codebook specifically focuses on operational aspects of IG 2.0 in the context of policy coding. Links to additional resources such as the underlying scientific literature (that offers a comprehensive treatment of the underlying theoretical concepts) are referred to in the DOI and the concluding section of the codebook.
Flip Paths Between Lattice Triangulations
Venue: arXiv cs.CG 2024
Year: 2024

We present a $O(n^{\frac{3}{2}})$-time algorithm for the \emph{shortest (diagonal) flip path problem} for \emph{lattice} triangulations with $n$ points, improving over previous $O(n^2)$-time algorithms. For a large, natural class of inputs, our bound is tight in the sense that our algorithm runs in time linear in the number of flips in the output flip path. Our results rely on an independently interesting structural elucidation of shortest flip paths as the linear orderings of a unique partially ordered set, called a \emph{minimum flip plan}, constructed by a novel use of Farey sequences from elementary number theory. Flip paths between general (not necessarily lattice) triangulations have been studied in the combinatorial setting for nearly a century. In the Euclidean geometric setting, finding a shortest flip path between two triangulations is NP-complete. However, for lattice triangulations, which are studied as spin systems, there are known $O\left(n^2\right)$-time algorithms to find shortest flip paths. These algorithms, as well as ours, apply to \emph{constrained} flip paths that ensure a set of \emph{constraint} edges are present in every triangulation along the path. Implications for determining simultaneously flippable edges, i.e. finding optimal simultaneous flip paths between lattice triangulations, and for counting lattice triangulations are discussed.
Embedded Blockchains: A Synthesis of Blockchains, Spread Spectrum Watermarking, Perceptual Hashing & Digital Signatures
Venue: arXiv cs.IT 2024
Year: 2024

In this paper we introduce a scheme for detecting manipulated audio and video. The scheme is a synthesis of blockchains, encrypted spread spectrum watermarks, perceptual hashing and digital signatures, which we call an Embedded Blockchain. Within this scheme, we use the blockchain for its data structure of a cryptographically linked list, cryptographic hashing for absolute comparisons, perceptual hashing for flexible comparisons, digital signatures for proof of ownership, and encrypted spread spectrum watermarking to embed the blockchain into the background noise of the media. So each media recording has its own unique blockchain, with each block holding information describing the media segment. The problem of verifying the integrity of the media is recast to traversing the blockchain, block-by-block, and segment-by-segment of the media. If any chain is broken, the difference in the computed and extracted perceptual hash is used to estimate the level of manipulation.
Self-Adaptive Physics-Informed Neural Networks using a Soft Attention Mechanism
Venue: arXiv cs.LG 2024
Year: 2024

Physics-Informed Neural Networks (PINNs) have emerged recently as a promising application of deep neural networks to the numerical solution of nonlinear partial differential equations (PDEs). However, it has been recognized that adaptive procedures are needed to force the neural network to fit accurately the stubborn spots in the solution of "stiff" PDEs. In this paper, we propose a fundamentally new way to train PINNs adaptively, where the adaptation weights are fully trainable and applied to each training point individually, so the neural network learns autonomously which regions of the solution are difficult and is forced to focus on them. The self-adaptation weights specify a soft multiplicative soft attention mask, which is reminiscent of similar mechanisms used in computer vision. The basic idea behind these SA-PINNs is to make the weights increase as the corresponding losses increase, which is accomplished by training the network to simultaneously minimize the losses and maximize the weights. In addition, we show how to build a continuous map of self-adaptive weights using Gaussian Process regression, which allows the use of stochastic gradient descent in problems where conventional gradient descent is not enough to produce accurate solutions. Finally, we derive the Neural Tangent Kernel matrix for SA-PINNs and use it to obtain a heuristic understanding of the effect of the self-adaptive weights on the dynamics of training in the limiting case of infinitely-wide PINNs, which suggests that SA-PINNs work by producing a smooth equalization of the eigenvalues of the NTK matrix corresponding to the different loss terms. In numerical experiments with several linear and nonlinear benchmark problems, the SA-PINN outperformed other state-of-the-art PINN algorithm in L2 error, while using a smaller number of training epochs.
Threshold rates for properties of random codes
Venue: arXiv cs.IT 2024
Year: 2024

Suppose that $P$ is a property that may be satisfied by a random code $C \subset Σ^n$. For example, for some $p \in (0,1)$, ${P}$ might be the property that there exist three elements of $C$ that lie in some Hamming ball of radius $pn$. We say that $R^*$ is the threshold rate for ${P}$ if a random code of rate $R^* + ε$ is very likely to satisfy ${P}$, while a random code of rate $R^* - ε$ is very unlikely to satisfy ${P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably "symmetric". For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property ${P}$ above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.
Transition-Oriented Programming: Developing Provably Correct Systems
Venue: arXiv cs.PL 2024
Year: 2024

Correctness is a necessary condition for systems to be effective in meeting human demands, thus playing a critical role in system development. However, correctness often manifests as a nebulous concept in practice, leading to challenges in accurately creating specifications, effectively proving correctness satisfiability, and efficiently implementing correct systems. Motivated by tackling these challenges, this paper introduces Transition-Oriented Programming (TOP), a programming paradigm to facilitate the development of provably correct systems by intertwining correctness specification, verification, and implementation within a unified theoretical framework.
Adversarial Exposure Attack on Diabetic Retinopathy Imagery Grading
Venue: arXiv cs.CV 2024
Year: 2024

Diabetic Retinopathy (DR) is a leading cause of vision loss around the world. To help diagnose it, numerous cutting-edge works have built powerful deep neural networks (DNNs) to automatically grade DR via retinal fundus images (RFIs). However, RFIs are commonly affected by camera exposure issues that may lead to incorrect grades. The mis-graded results can potentially pose high risks to an aggravation of the condition. In this paper, we study this problem from the viewpoint of adversarial attacks. We identify and introduce a novel solution to an entirely new task, termed as adversarial exposure attack, which is able to produce natural exposure images and mislead the state-of-the-art DNNs. We validate our proposed method on a real-world public DR dataset with three DNNs, e.g., ResNet50, MobileNet, and EfficientNet, demonstrating that our method achieves high image quality and success rate in transferring the attacks. Our method reveals the potential threats to DNN-based automatic DR grading and would benefit the development of exposure-robust DR grading methods in the future.
Proving Highly-Concurrent Traversals Correct
Venue: arXiv cs.DC 2024
Year: 2024

Modern highly-concurrent search data structures, such as search trees, obtain multi-core scalability and performance by having operations traverse the data structure without any synchronization. As a result, however, these algorithms are notoriously difficult to prove linearizable, which requires identifying a point in time in which the traversal's result is correct. The problem is that traversing the data structure as it undergoes modifications leads to complex behaviors, necessitating intricate reasoning about all interleavings of reads by traversals and writes mutating the data structure. In this paper, we present a general proof technique for proving unsynchronized traversals correct in a significantly simpler manner, compared to typical concurrent reasoning and prior proof techniques. Our framework relies only on sequential properties} of traversals and on a conceptually simple and widely-applicable condition about the ways an algorithm's writes mutate the data structure. Establishing that a target data structure satisfies our condition requires only simple concurrent reasoning, without considering interactions of writes and reads. This reasoning can be further simplified by using our framework. To demonstrate our technique, we apply it to prove several interesting and challenging concurrent binary search trees: the logical-ordering AVL tree, the Citrus tree, and the full contention-friendly tree. Both the logical-ordering tree and the full contention-friendly tree are beyond the reach of previous approaches targeted at simplifying linearizability proofs.