OpenRaiser/Intern-Atlas huggingface dataset:
Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
Venue: arXiv cs.LG 2024
Year: 2024

Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon tabular reinforcement learning to multi-armed bandits, where, specifically, an independent bandit learner is placed in each state. We show that, under ergodicity and fast mixing assumptions, any slowly changing adversarial bandit algorithm achieving optimal regret in the adversarial bandit setting can also attain optimal expected regret in infinite-horizon discounted Markov decision processes, with respect to the number of rounds $T$. Furthermore, we examine our reduction using a specific instance of the exponential-weight algorithm.
Estimation of binary time-frequency masks from ambient noise
Venue: arXiv cs.SD 2024
Year: 2024

We investigate the retrieval of a binary time-frequency mask from a few observations of filtered white ambient noise. Confirming household wisdom in acoustic modeling, we show that this is possible by inspecting the average spectrogram of ambient noise. Specifically, we show that the lower quantile of the average of $\mathcal{O}(\log(|Ω|/\varepsilon))$ masked spectrograms is enough to identify a rather general mask $Ω$ with confidence at least $\varepsilon$, up to shape details concentrated near the boundary of $Ω$. As an application, the expected measure of the estimation error is dominated by the perimeter of the time-frequency mask. The estimator requires no knowledge of the noise variance, and only a very qualitative profile of the filtering window, but no exact knowledge of it.
Policy-based Primal-Dual Methods for Concave CMDP with Variance Reduction
Venue: arXiv cs.LG 2024
Year: 2024

We study Concave Constrained Markov Decision Processes (Concave CMDPs) where both the objective and constraints are defined as concave functions of the state-action occupancy measure. We propose the Variance-Reduced Primal-Dual Policy Gradient Algorithm (VR-PDPG), which updates the primal variable via policy gradient ascent and the dual variable via projected sub-gradient descent. Despite the challenges posed by the loss of additivity structure and the nonconcave nature of the problem, we establish the global convergence of VR-PDPG by exploiting a form of hidden concavity. In the exact setting, we prove an $O(T^{-1/3})$ convergence rate for both the average optimality gap and constraint violation, which further improves to $O(T^{-1/2})$ under strong concavity of the objective in the occupancy measure. In the sample-based setting, we demonstrate that VR-PDPG achieves an $\widetilde{O}(ε^{-4})$ sample complexity for $ε$-global optimality. Moreover, by incorporating a diminishing pessimistic term into the constraint, we show that VR-PDPG can attain a zero constraint violation without compromising the convergence rate of the optimality gap. Finally, we validate the effectiveness of our methods through numerical experiments.
Recent Advances in Embedding Methods for Multi-Object Tracking: A Survey
Venue: arXiv cs.CV 2024
Year: 2024

Multi-object tracking (MOT) aims to associate target objects across video frames in order to obtain entire moving trajectories. With the advancement of deep neural networks and the increasing demand for intelligent video analysis, MOT has gained significantly increased interest in the computer vision community. Embedding methods play an essential role in object location estimation and temporal identity association in MOT. Unlike other computer vision tasks, such as image classification, object detection, re-identification, and segmentation, embedding methods in MOT have large variations, and they have never been systematically analyzed and summarized. In this survey, we first conduct a comprehensive overview with in-depth analysis for embedding methods in MOT from seven different perspectives, including patch-level embedding, single-frame embedding, cross-frame joint embedding, correlation embedding, sequential embedding, tracklet embedding, and cross-track relational embedding. We further summarize the existing widely used MOT datasets and analyze the advantages of existing state-of-the-art methods according to their embedding strategies. Finally, some critical yet under-investigated areas and future research directions are discussed.
Heterogeneous Semantic Transfer for Multi-label Recognition with Partial Labels
Venue: arXiv cs.CV 2024
Year: 2024

Multi-label image recognition with partial labels (MLR-PL), in which some labels are known while others are unknown for each image, may greatly reduce the cost of annotation and thus facilitate large-scale MLR. We find that strong semantic correlations exist within each image and across different images, and these correlations can help transfer the knowledge possessed by the known labels to retrieve the unknown labels and thus improve the performance of the MLR-PL task (see Figure 1). In this work, we propose a novel heterogeneous semantic transfer (HST) framework that consists of two complementary transfer modules that explore both within-image and cross-image semantic correlations to transfer the knowledge possessed by known labels to generate pseudo labels for the unknown labels. Specifically, an intra-image semantic transfer (IST) module learns an image-specific label co-occurrence matrix for each image and maps the known labels to complement the unknown labels based on these matrices. Additionally, a cross-image transfer (CST) module learns category-specific feature-prototype similarities and then helps complement the unknown labels that have high degrees of similarity with the corresponding prototypes. Finally, both the known and generated pseudo labels are used to train MLR models. Extensive experiments conducted on the Microsoft COCO, Visual Genome, and Pascal VOC 2007 datasets show that the proposed HST framework achieves superior performance to that of current state-of-the-art algorithms. Specifically, it obtains mean average precision (mAP) improvements of 1.4%, 3.3%, and 0.4% on the three datasets over the results of the best-performing previously developed algorithm.
LIA: Privacy-Preserving Data Quality Evaluation in Federated Learning Using a Lazy Influence Approximation
Venue: arXiv cs.CR 2024
Year: 2024

In Federated Learning, it is crucial to handle low-quality, corrupted, or malicious data. However, traditional data valuation methods are not suitable due to privacy concerns. To address this, we propose a simple yet effective approach that utilizes a new influence approximation called "lazy influence" to filter and score data while preserving privacy. To do this, each participant uses their own data to estimate the influence of another participant's batch and sends a differentially private obfuscated score to the central coordinator. Our method has been shown to successfully filter out biased and corrupted data in various simulated and real-world settings, achieving a recall rate of over $>90\%$ (sometimes up to $100\%$) while maintaining strong differential privacy guarantees with $\varepsilon \leq 1$.
Compressing the chronology of a temporal network with graph commutators
Venue: arXiv cs.SI 2024
Year: 2024

Studies of dynamics on temporal networks often represent the network as a series of "snapshots," static networks active for short durations of time. We argue that successive snapshots can be aggregated if doing so has little effect on the overlying dynamics. We propose a method to compress network chronologies by progressively combining pairs of snapshots whose matrix commutators have the smallest dynamical effect. We apply this method to epidemic modeling on real contact tracing data and find that it allows for significant compression while remaining faithful to the epidemic dynamics.
Holonomic equations and efficient random generation of binary trees
Venue: arXiv cs.DS 2024
Year: 2024

Holonomic equations are recursive equations which allow computing efficiently numbers of combinatoric objects. R{é}my showed that the holonomic equation associated with binary trees yields an efficient linear random generator of binary trees. I extend this paradigm to Motzkin trees and Schr{ö}der trees and show that despite slight differences my algorithm that generates random Schr{ö}der trees has linear expected complexity and my algorithm that generates Motzkin trees is in O(n) expected complexity, only if we can implement a specific oracle with a O(1) complexity. For Motzkin trees, I propose a solution which works well for realistic values (up to size ten millions) and yields an efficient algorithm.
Neuro-Symbolic Learning of Answer Set Programs from Raw Data
Venue: arXiv cs.AI 2024
Year: 2024

One of the ultimate goals of Artificial Intelligence is to assist humans in complex decision making. A promising direction for achieving this goal is Neuro-Symbolic AI, which aims to combine the interpretability of symbolic techniques with the ability of deep learning to learn from raw data. However, most current approaches require manually engineered symbolic knowledge, and where end-to-end training is considered, such approaches are either restricted to learning definite programs, or are restricted to training binary neural networks. In this paper, we introduce Neuro-Symbolic Inductive Learner (NSIL), an approach that trains a general neural network to extract latent concepts from raw data, whilst learning symbolic knowledge that maps latent concepts to target labels. The novelty of our approach is a method for biasing the learning of symbolic knowledge, based on the in-training performance of both neural and symbolic components. We evaluate NSIL on three problem domains of different complexity, including an NP-complete problem. Our results demonstrate that NSIL learns expressive knowledge, solves computationally complex problems, and achieves state-of-the-art performance in terms of accuracy and data efficiency. Code and technical appendix: https://github.com/DanCunnington/NSIL
Differentiable solver for time-dependent deformation problems with contact
Venue: arXiv cs.GR 2024
Year: 2024

We introduce a general differentiable solver for time-dependent deformation problems with contact and friction. Our approach uses a finite element discretization with a high-order time integrator coupled with the recently proposed incremental potential contact method for handling contact and friction forces to solve ODE- and PDE-constrained optimization problems on scenes with complex geometry. It supports static and dynamic problems and differentiation with respect to all physical parameters involved in the physical problem description, which include shape, material parameters, friction parameters, and initial conditions. Our analytically derived adjoint formulation is efficient, with a small overhead (typically less than 10% for nonlinear problems) over the forward simulation, and shares many similarities with the forward problem, allowing the reuse of large parts of existing forward simulator code. We implement our approach on top of the open-source PolyFEM library and demonstrate the applicability of our solver to shape design, initial condition optimization, and material estimation on both simulated results and physical validations.
RIAV-MVS: Recurrent-Indexing an Asymmetric Volume for Multi-View Stereo
Venue: arXiv cs.CV 2024
Year: 2024

This paper presents a learning-based method for multi-view depth estimation from posed images. Our core idea is a "learning-to-optimize" paradigm that iteratively indexes a plane-sweeping cost volume and regresses the depth map via a convolutional Gated Recurrent Unit (GRU). Since the cost volume plays a paramount role in encoding the multi-view geometry, we aim to improve its construction both at pixel- and frame- levels. At the pixel level, we propose to break the symmetry of the Siamese network (which is typically used in MVS to extract image features) by introducing a transformer block to the reference image (but not to the source images). Such an asymmetric volume allows the network to extract global features from the reference image to predict its depth map. Given potential inaccuracies in the poses between reference and source images, we propose to incorporate a residual pose network to correct the relative poses. This essentially rectifies the cost volume at the frame level. We conduct extensive experiments on real-world MVS datasets and show that our method achieves state-of-the-art performance in terms of both within-dataset evaluation and cross-dataset generalization. Code available: https://github.com/oppo-us-research/riav-mvs.
Functional Linear Regression of Cumulative Distribution Functions
Venue: arXiv cs.LG 2024
Year: 2024

The estimation of cumulative distribution functions (CDF) is an important learning task with a great variety of downstream applications, such as risk assessments in predictions and decision making. In this paper, we study functional regression of contextual CDFs where each data point is sampled from a linear combination of context dependent CDF basis functions. We propose functional ridge-regression-based estimation methods that estimate CDFs accurately everywhere. In particular, given $n$ samples with $d$ basis functions, we show estimation error upper bounds of $\widetilde O(\sqrt{d/n})$ for fixed design, random design, and adversarial context cases. We also derive matching information theoretic lower bounds, establishing minimax optimality for CDF functional regression. Furthermore, we remove the burn-in time in the random design setting using an alternative penalized estimator. Then, we consider agnostic settings where there is a mismatch in the data generation process. We characterize the error of the proposed estimators in terms of the mismatched error, and show that the estimators are well-behaved under model mismatch. Moreover, to complete our study, we formalize infinite dimensional models where the parameter space is an infinite dimensional Hilbert space, and establish a self-normalized estimation error upper bound for this setting. Notably, the upper bound reduces to the $\widetilde O(\sqrt{d/n})$ bound when the parameter space is constrained to be $d$-dimensional. Our comprehensive numerical experiments validate the efficacy of our estimation methods in both synthetic and practical settings.
Variational Transfer Learning using Cross-Domain Latent Modulation
Venue: arXiv cs.LG 2024
Year: 2024

To successfully apply trained neural network models to new domains, powerful transfer learning solutions are essential. We propose to introduce a novel cross-domain latent modulation mechanism to a variational autoencoder framework so as to achieve effective transfer learning. Our key idea is to procure deep representations from one data domain and use it to influence the reparameterization of the latent variable of another domain. Specifically, deep representations of the source and target domains are first extracted by a unified inference model and aligned by employing gradient reversal. The learned deep representations are then cross-modulated to the latent encoding of the alternative domain, where consistency constraints are also applied. In the empirical validation that includes a number of transfer learning benchmark tasks for unsupervised domain adaptation and image-to-image translation, our model demonstrates competitive performance, which is also supported by evidence obtained from visualization.
EMS: Efficient and Effective Massively Multilingual Sentence Embedding Learning
Venue: arXiv cs.CL 2024
Year: 2024

Massively multilingual sentence representation models, e.g., LASER, SBERT-distill, and LaBSE, help significantly improve cross-lingual downstream tasks. However, the use of a large amount of data or inefficient model architectures results in heavy computation to train a new model according to our preferred languages and domains. To resolve this issue, we introduce efficient and effective massively multilingual sentence embedding (EMS), using cross-lingual token-level reconstruction (XTR) and sentence-level contrastive learning as training objectives. Compared with related studies, the proposed model can be efficiently trained using significantly fewer parallel sentences and GPU computation resources. Empirical results showed that the proposed model significantly yields better or comparable results with regard to cross-lingual sentence retrieval, zero-shot cross-lingual genre classification, and sentiment classification. Ablative analyses demonstrated the efficiency and effectiveness of each component of the proposed model. We release the codes for model training and the EMS pre-trained sentence embedding model, which supports 62 languages ( https://github.com/Mao-KU/EMS ).
Interpretability Guarantees with Merlin-Arthur Classifiers
Venue: arXiv cs.LG 2024
Year: 2024

We propose an interactive multi-agent classifier that provides provable interpretability guarantees even for complex agents such as neural networks. These guarantees consist of lower bounds on the mutual information between selected features and the classification decision. Our results are inspired by the Merlin-Arthur protocol from Interactive Proof Systems and express these bounds in terms of measurable metrics such as soundness and completeness. Compared to existing interactive setups, we rely neither on optimal agents nor on the assumption that features are distributed independently. Instead, we use the relative strength of the agents as well as the new concept of Asymmetric Feature Correlation which captures the precise kind of correlations that make interpretability guarantees difficult. We evaluate our results on two small-scale datasets where high mutual information can be verified explicitly.
Load Balancing Using Sparse Communication
Venue: arXiv cs.DC 2024
Year: 2024

Load balancing across parallel servers is an important class of congestion control problems that arises in service systems. An effective load balancer relies heavily on accurate, real-time congestion information to make routing decisions. However, obtaining such information can impose significant communication overheads, especially in demanding applications like those found in modern data centers. We introduce a framework for communication-aware load balancing and design new load balancing algorithms that perform exceptionally well even in scenarios with sparse communication patterns. Central to our approach is state approximation, where the load balancer first estimates server states through a communication protocol. Subsequently, it utilizes these approximate states within a load balancing algorithm to determine routing decisions. We demonstrate that by using a novel communication protocol, one can achieve accurate queue length approximation with sparse communication: for a maximal approximation error of x, the communication frequency only needs to be O(1/x^2). We further show, via a diffusion analysis, that a constant maximal approximation error is sufficient for achieving asymptotically optimal performance. Taken together, these results therefore demonstrate that highly performant load balancing is possible with very little communication. Through simulations, we observe that the proposed designs match or surpass the performance of state-of-the-art load balancing algorithms while drastically reducing communication rates by up to 90%.
Subspace Phase Retrieval
Venue: arXiv cs.IT 2024
Year: 2024

In recent years, phase retrieval has received much attention in statistics, applied mathematics and optical engineering. In this paper, we propose an efficient algorithm, termed Subspace Phase Retrieval (SPR), which can accurately recover an $n$-dimensional $k$-sparse complex-valued signal $\x$ given its $Ω(k^2\log n)$ magnitude-only Gaussian samples if the minimum nonzero entry of $\x$ satisfies $|x_{\min}| = Ω(\|\x\|/\sqrt{k})$. Furthermore, if the energy sum of the most significant $\sqrt{k}$ elements in $\x$ is comparable to $\|\x\|^2$, the SPR algorithm can exactly recover $\x$ with $Ω(k \log n)$ magnitude-only samples, which attains the information-theoretic sampling complexity for sparse phase retrieval. Numerical Experiments demonstrate that the proposed algorithm achieves the state-of-the-art reconstruction performance compared to existing ones.
Contemporary Recommendation Systems on Big Data and Their Applications: A Survey
Venue: arXiv cs.IR 2024
Year: 2024

This survey paper conducts a comprehensive analysis of the evolution and contemporary landscape of recommendation systems, which have been extensively incorporated across a myriad of web applications. It delves into the progression of personalized recommendation methodologies tailored for online products or services, organizing the array of recommendation techniques into four main categories: content-based, collaborative filtering, knowledge-based, and hybrid approaches, each designed to cater to specific contexts. The document provides an in-depth review of both the historical underpinnings and the cutting-edge innovations in the domain of recommendation systems, with a special focus on implementations leveraging big data analytics. The paper also highlights the utilization of prominent datasets such as MovieLens, Amazon Reviews, Netflix Prize, Last.fm, and Yelp in evaluating recommendation algorithms. It further outlines and explores the predominant challenges encountered in the current generation of recommendation systems, including issues related to data sparsity, scalability, and the imperative for diversified recommendation outputs. The survey underscores these challenges as promising directions for subsequent research endeavors within the discipline. Additionally, the paper examines various real-life applications driven by recommendation systems, addressing the hurdles involved in seamlessly integrating these systems into everyday life. Ultimately, the survey underscores how the advancements in recommendation systems, propelled by big data technologies, have the potential to significantly enhance real-world experiences.
Enhancing Distributional Stability among Sub-populations
Venue: arXiv cs.LG 2024
Year: 2024

Enhancing the stability of machine learning algorithms under distributional shifts is at the heart of the Out-of-Distribution (OOD) Generalization problem. Derived from causal learning, recent works of invariant learning pursue strict invariance with multiple training environments. Although intuitively reasonable, strong assumptions on the availability and quality of environments are made to learn the strict invariance property. In this work, we come up with the ``distributional stability" notion to mitigate such limitations. It quantifies the stability of prediction mechanisms among sub-populations down to a prescribed scale. Based on this, we propose the learnability assumption and derive the generalization error bound under distribution shifts. Inspired by theoretical analyses, we propose our novel stable risk minimization (SRM) algorithm to enhance the model's stability w.r.t. shifts in prediction mechanisms ($Y|X$-shifts). Experimental results are consistent with our intuition and validate the effectiveness of our algorithm. The code can be found at https://github.com/LJSthu/SRM.