OpenRaiser/Intern-Atlas huggingface dataset:
Spatial-Aware GAN for Unsupervised Person Re-identification
Venue: arXiv cs.CV 2022
Year: 2022

The recent person re-identification research has achieved great success by learning from a large number of labeled person images. On the other hand, the learned models often experience significant performance drops when applied to images collected in a different environment. Unsupervised domain adaptation (UDA) has been investigated to mitigate this constraint, but most existing systems adapt images at pixel level only and ignore obvious discrepancies at spatial level. This paper presents an innovative UDA-based person re-identification network that is capable of adapting images at both spatial and pixel levels simultaneously. A novel disentangled cycle-consistency loss is designed which guides the learning of spatial-level and pixel-level adaptation in a collaborative manner. In addition, a novel multi-modal mechanism is incorporated which is capable of generating images of different geometry views and augmenting training images effectively. Extensive experiments over a number of public datasets show that the proposed UDA network achieves superior person re-identification performance as compared with the state-of-the-art.
The Classes PPA-$k$: Existence from Arguments Modulo $k$
Venue: arXiv cs.CC 2022
Year: 2022

The complexity classes PPA-$k$, $k \geq 2$, have recently emerged as the main candidates for capturing the complexity of important problems in fair division, in particular Alon's Necklace-Splitting problem with $k$ thieves. Indeed, the problem with two thieves has been shown complete for PPA = PPA-2. In this work, we present structural results which provide a solid foundation for the further study of these classes. Namely, we investigate the classes PPA-$k$ in terms of (i) equivalent definitions, (ii) inner structure, (iii) relationship to each other and to other TFNP classes, and (iv) closure under Turing reductions.
A Logic that Captures $β$P on Ordered Structures
Venue: arXiv cs.LO 2022
Year: 2022

We extend the inflationary fixed-point logic, IFP, with a new kind of second-order quantifiers which have (poly-)logarithmic bounds. We prove that on ordered structures the new logic $\exists^{\log^ω}\text{IFP}$ captures the limited nondeterminism class $β\text{P}$. In order to study its expressive power, we also design a new version of Ehrenfeucht-Fraïssé game for this logic and show that our capturing result will not hold on the general case, i.e. on all the finite structures.
Approximate Strategyproofness in Large, Two-Sided Matching Markets
Venue: arXiv cs.MA 2022
Year: 2022

An approximation of strategyproofness in large, two-sided matching markets is highly evident. Through simulations, one can observe that the percentage of agents with useful deviations decreases as the market size grows. Furthermore, there seems to be a strong connection between the length of preference order lists, the correlation of agent preferences, and the approximation of strategyproofness. Interestingly, approximate strategyproofness is reached easier with a shorter length of preference orders and higher preference correlation. These findings justify the use of the deferred acceptance algorithm in large two-sided matching markets despite it not being strategy-proof.
Front-Running Protection for Distributed Exchanges using Tamper-Resistant Round Trip Time Measurements
Venue: arXiv cs.DC 2022
Year: 2022

In this paper we present ODIN, a front-running protection system that uses a novel algorithm to measure Round-Trip-Time (RTT) to untrusted servers. ODIN is the decentralized equivalent of THOR, a RTT-aware front-running protection system for trading on centralized exchanges. Unlike centralized exchanges, P2P exchanges have potentially malicious peers which makes reliable direct RTT measurement impossible. In order to prevent tampering by an arbitrarily malicious peer, ODIN performs an indirect RTT measurement that never interacts directly with the target machine. The RTT to the target is estimated by measuring the RTT to a randomized IP address that is known to be close to the target's IP address in the global routing network. We find that ODIN's RTT estimation algorithm provides an accurate, practical, and generic solution for collecting network latency data in a hostile network environment.
secml: A Python Library for Secure and Explainable Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

We present \texttt{secml}, an open-source Python library for secure and explainable machine learning. It implements the most popular attacks against machine learning, including test-time evasion attacks to generate adversarial examples against deep neural networks and training-time poisoning attacks against support vector machines and many other algorithms. These attacks enable evaluating the security of learning algorithms and the corresponding defenses under both white-box and black-box threat models. To this end, \texttt{secml} provides built-in functions to compute security evaluation curves, showing how quickly classification performance decreases against increasing adversarial perturbations of the input data. \texttt{secml} also includes explainability methods to help understand why adversarial attacks succeed against a given model, by visualizing the most influential features and training prototypes contributing to each decision. It is distributed under the Apache License 2.0 and hosted at \url{https://github.com/pralab/secml}.
Performance Analysis of TLS for Quantum Robust Cryptography on a Constrained Device
Venue: arXiv cs.CR 2022
Year: 2022

Advances in quantum computing make Shor's algorithm for factorising numbers ever more tractable. This threatens the security of any cryptographic system which often relies on the difficulty of factorisation. It also threatens methods based on discrete logarithms, such as with the Diffie-Hellman key exchange method. For a cryptographic system to remain secure against a quantum adversary, we need to build methods based on a hard mathematical problem, which are not susceptible to Shor's algorithm and which create Post Quantum Cryptography (PQC). While high-powered computing devices may be able to run these new methods, we need to investigate how well these methods run on limited powered devices. This paper outlines an evaluation framework for PQC within constrained devices, and contributes to the area by providing benchmarks of the front-running algorithms on a popular single-board low-power device.
Improving Few-shot Learning by Spatially-aware Matching and CrossTransformer
Venue: arXiv cs.CV 2022
Year: 2022

Current few-shot learning models capture visual object relations in the so-called meta-learning setting under a fixed-resolution input. However, such models have a limited generalization ability under the scale and location mismatch between objects, as only few samples from target classes are provided. Therefore, the lack of a mechanism to match the scale and location between pairs of compared images leads to the performance degradation. The importance of image contents varies across coarse-to-fine scales depending on the object and its class label, e.g., generic objects and scenes rely on their global appearance while fine-grained objects rely more on their localized visual patterns. In this paper, we study the impact of scale and location mismatch in the few-shot learning scenario, and propose a novel Spatially-aware Matching (SM) scheme to effectively perform matching across multiple scales and locations, and learn image relations by giving the highest weights to the best matching pairs. The SM is trained to activate the most related locations and scales between support and query data. We apply and evaluate SM on various few-shot learning models and backbones for comprehensive evaluations. Furthermore, we leverage an auxiliary self-supervisory discriminator to train/predict the spatial- and scale-level index of feature vectors we use. Finally, we develop a novel transformer-based pipeline to exploit self- and cross-attention in a spatially-aware matching process. Our proposed design is orthogonal to the choice of backbone and/or comparator.
Compressibility Measures for Affinely Singular Random Vectors
Venue: arXiv cs.IT 2022
Year: 2022

There are several ways to measure the compressibility of a random measure; they include general approaches such as using the rate-distortion curve, as well as more specific notions, such as the Renyi information dimension (RID). The RID parameter indicates the concentration of the measure around lower-dimensional subsets of the space. While the evaluation of such compressibility parameters is well-studied for continuous and discrete measures, the case of discrete-continuous measures is quite subtle. In this paper, we focus on a class of multi-dimensional random measures that have singularities on affine lower-dimensional subsets. This class of distributions naturally arises when considering linear transformation of component-wise independent discrete-continuous random variables. To measure the compressibility of such distributions, we introduce the new notion of dimensional-rate bias (DRB) which is closely related to the entropy and differential entropy in discrete and continuous cases, respectively. Similar to entropy and differential entropy, DRB is useful in evaluating the mutual information between distributions of the aforementioned type. Besides the DRB, we also evaluate the the RID of these distributions. We further provide an upper-bound for the RID of multi-dimensional random measures that are obtained by Lipschitz functions of component-wise independent discrete-continuous random variables ($\mathbf{X}$). The upper-bound is shown to be achievable when the Lipschitz function is $A \mathbf{X}$, where $A$ satisfies {\changed$\spark({A_{m\times n}}) = m+1$} (e.g., Vandermonde matrices). When considering discrete-domain moving-average processes with non-Gaussian excitation noise, the above results allow us to evaluate the block-average RID and DRB, as well as to determine a relationship between these parameters and other existing compressibility measures.
Cycles in synchronous iterative voting: general robustness and examples in Approval Voting
Venue: arXiv cs.GT 2022
Year: 2022

We consider synchronous iterative voting, where voters are given the opportunity to strategically choose their ballots depending on the outcome deduced from the previous collective choices.We propose two settings for synchronous iterative voting, one of classical flavor with a discrete space of states, and a more general continuous-space setting extending the first one. We give a general robustness result for cycles not relying on a tie-breaking rule, showing that they persist under small enough perturbations of the behavior of voters. Then we give examples in Approval Voting of electorates applying simple, sincere and consistent heuristics (namely Laslier's Leader Rule or a modification of it) leading to cycles with bad outcomes, either not electing an existing Condorcet winner, or possibly electing a candidate ranked last by a majority of voters. Using the robustness result, it follows that those "bad cycles" persist even if only a (large enough) fraction of the electorate updates its choice of ballot at each iteration.We complete these results with examples in other voting methods, including ranking methods satisfying the Condorcet criterion; an in silico experimental study of the rarity of preference profiles exhibiting bad cycles; and an example exhibiting chaotic behavior.
A Categorical Framework for Learning Generalised Tree Automata
Venue: arXiv cs.FL 2022
Year: 2022

Automata learning is a popular technique used to automatically construct an automaton model from queries. Much research went into devising ad hoc adaptations of algorithms for different types of automata. The CALF project seeks to unify these using category theory in order to ease correctness proofs and guide the design of new algorithms. In this paper, we extend CALF to cover learning of algebraic structures that may not have a coalgebraic presentation. Furthermore, we provide a detailed algorithmic account of an abstract version of the popular L* algorithm, which was missing from CALF. We instantiate the abstract theory to a large class of Set functors, by which we recover for the first time practical tree automata learning algorithms from an abstract framework and at the same time obtain new algorithms to learn algebras of quotiented polynomial functors.
The Risk to Population Health Equity Posed by Automated Decision Systems: A Narrative Review
Venue: arXiv cs.CY 2022
Year: 2022

Artificial intelligence is already ubiquitous, and is increasingly being used to autonomously make ever more consequential decisions. However, there has been relatively little research into the existing and possible consequences for population health equity. A narrative review was undertaken using a hermeneutic approach to explore current and future uses of narrow AI and automated decision systems (ADS) in medicine and public health, issues that have emerged, and implications for equity. Accounts reveal a tremendous expectation on AI to transform medical and public health practices. Prominent demonstrations of AI capability - particularly in diagnostic decision making, risk prediction, and surveillance - are stimulating rapid adoption, spurred by COVID-19. Automated decisions being made have significant consequences for individual and population health and wellbeing. Meanwhile, it is evident that hazards including bias, incontestability, and privacy erosion have emerged in sensitive domains such as criminal justice where narrow AI and ADS are in common use. Reports of issues arising from their use in health are already appearing. As the use of ADS in health expands, it is probable that these hazards will manifest more widely. Bias, incontestability, and privacy erosion give rise to mechanisms by which existing social, economic and health disparities are perpetuated and amplified. Consequently, there is a significant risk that use of ADS in health will exacerbate existing population health inequities. The industrial scale and rapidity with which ADS can be applied heightens the risk to population health equity. It is incumbent on health practitioners and policy makers therefore to explore the potential implications of using ADS, to ensure the use of artificial intelligence promotes population health and equity.
PDE-based Group Equivariant Convolutional Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

We present a PDE-based framework that generalizes Group equivariant Convolutional Neural Networks (G-CNNs). In this framework, a network layer is seen as a set of PDE-solvers where geometrically meaningful PDE-coefficients become the layer's trainable weights. Formulating our PDEs on homogeneous spaces allows these networks to be designed with built-in symmetries such as rotation in addition to the standard translation equivariance of CNNs. Having all the desired symmetries included in the design obviates the need to include them by means of costly techniques such as data augmentation. We will discuss our PDE-based G-CNNs (PDE-G-CNNs) in a general homogeneous space setting while also going into the specifics of our primary case of interest: roto-translation equivariance. We solve the PDE of interest by a combination of linear group convolutions and non-linear morphological group convolutions with analytic kernel approximations that we underpin with formal theorems. Our kernel approximations allow for fast GPU-implementation of the PDE-solvers, we release our implementation with this article in the form of the LieTorch extension to PyTorch, available at https://gitlab.com/bsmetsjr/lietorch . Just like for linear convolution a morphological convolution is specified by a kernel that we train in our PDE-G-CNNs. In PDE-G-CNNs we do not use non-linearities such as max/min-pooling and ReLUs as they are already subsumed by morphological convolutions. We present a set of experiments to demonstrate the strength of the proposed PDE-G-CNNs in increasing the performance of deep learning based imaging applications with far fewer parameters than traditional CNNs.
Tight Regret Bounds for Noisy Optimization of a Brownian Motion
Venue: arXiv cs.LG 2022
Year: 2022

We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the $T$ adaptively chosen observations are corrupted by Gaussian noise. We show that as the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $Ω(σ\sqrt{T / \log (T)}) \cap \mathcal{O}(σ\sqrt{T} \cdot \log T)$ and $Ω(σ/ \sqrt{T \log (T)}) \cap \mathcal{O}(σ\log T / \sqrt{T})$ respectively, where $σ^2$ is the noise variance. Thus, our upper and lower bounds are tight up to a factor of $\mathcal{O}( (\log T)^{1.5} )$. The upper bound uses an algorithm based on confidence bounds and the Markov property of Brownian motion (among other useful properties), and the lower bound is based on a reduction to binary hypothesis testing.
Stochastic Extensible Bin Packing
Venue: arXiv cs.DS 2022
Year: 2022

We consider the stochastic extensible bin packing problem (SEBP) in which $n$ items of stochastic size are packed into $m$ bins of unit capacity. In contrast to the classical bin packing problem, the number of bins is fixed and they can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of $2$. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of $(1+e^{-1}) \approx 1.368$. Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for. We also provide a lower bound on the performance of this policy comparing against an optimal fixed assignment policy. Finally, we obtain improved bounds for the case where the processing times are drawn from a particular family of distributions, with either a bounded Pietra index or when the familly is stochastically dominated at the second order.
Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
Venue: arXiv cs.LG 2022
Year: 2022

We consider an adversarial variant of the classic $K$-armed linear contextual bandit problem where the sequence of loss functions associated with each arm are allowed to change without restriction over time. Under the assumption that the $d$-dimensional contexts are generated i.i.d.~at random from a known distributions, we develop computationally efficient algorithms based on the classic Exp3 algorithm. Our first algorithm, RealLinExp3, is shown to achieve a regret guarantee of $\widetilde{O}(\sqrt{KdT})$ over $T$ rounds, which matches the best available bound for this problem. Our second algorithm, RobustLinExp3, is shown to be robust to misspecification, in that it achieves a regret bound of $\widetilde{O}((Kd)^{1/3}T^{2/3}) + \varepsilon \sqrt{d} T$ if the true reward function is linear up to an additive nonlinear error uniformly bounded in absolute value by $\varepsilon$. To our knowledge, our performance guarantees constitute the very first results on this problem setting.
The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
Venue: arXiv cs.GT 2022
Year: 2022

We consider incentivized exploration: a version of multi-armed bandits where the choice of arms is controlled by self-interested agents, and the algorithm can only issue recommendations. The algorithm controls the flow of information, and the information asymmetry can incentivize the agents to explore. Prior work achieves optimal regret rates up to multiplicative factors that become arbitrarily large depending on the Bayesian priors, and scale exponentially in the number of arms. A more basic problem of sampling each arm once runs into similar factors. We focus on the price of incentives: the loss in performance, broadly construed, incurred for the sake of incentive-compatibility. We prove that Thompson Sampling, a standard bandit algorithm, is incentive-compatible if initialized with sufficiently many data points. The performance loss due to incentives is therefore limited to the initial rounds when these data points are collected. The problem is largely reduced to that of sample complexity: how many rounds are needed? We address this question, providing matching upper and lower bounds and instantiating them in various corollaries. Typically, the optimal sample complexity is polynomial in the number of arms and exponential in the "strength of beliefs".
L6DNet: Light 6 DoF Network for Robust and Precise Object Pose Estimation with Small Datasets
Venue: arXiv cs.CV 2022
Year: 2022

Estimating the 3D pose of an object is a challenging task that can be considered within augmented reality or robotic applications. In this paper, we propose a novel approach to perform 6 DoF object pose estimation from a single RGB-D image. We adopt a hybrid pipeline in two stages: data-driven and geometric respectively. The data-driven step consists of a classification CNN to estimate the object 2D location in the image from local patches, followed by a regression CNN trained to predict the 3D location of a set of keypoints in the camera coordinate system. To extract the pose information, the geometric step consists in aligning the 3D points in the camera coordinate system with the corresponding 3D points in world coordinate system by minimizing a registration error, thus computing the pose. Our experiments on the standard dataset LineMod show that our approach is more robust and accurate than state-of-the-art methods. The approach is also validated to achieve a 6 DoF positioning task by visual servoing.
Learning spatio-temporal representations with temporal squeeze pooling
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we propose a new video representation learning method, named Temporal Squeeze (TS) pooling, which can extract the essential movement information from a long sequence of video frames and map it into a set of few images, named Squeezed Images. By embedding the Temporal Squeeze pooling as a layer into off-the-shelf Convolution Neural Networks (CNN), we design a new video classification model, named Temporal Squeeze Network (TeSNet). The resulting Squeezed Images contain the essential movement information from the video frames, corresponding to the optimization of the video classification task. We evaluate our architecture on two video classification benchmarks, and the results achieved are compared to the state-of-the-art.