OpenRaiser/Intern-Atlas huggingface dataset:
Finding Triangles or Independent Sets; and Other Dual Pair Approximations
Venue: arXiv cs.DS 2024
Year: 2024

We revisit the algorithmic problem of finding a triangle in a graph (\textsc{Triangle Detection}), and examine its relation to other problems such as \textsc{3Sum}, \textsc{Independent Set}, and \textsc{Graph Coloring}. We obtain several new algorithms: \smallskip (I) A simple randomized algorithm for finding a triangle in a graph. As an application, we study the range of a conjecture of Pǎtraşcu (2010) regarding the triangle detection problem. \smallskip (II) An algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n)$ (ie, linear) time: (i)~compute a $Ω(1/\sqrt{n})$-approximation of a maximum independent set in $G$ or (ii)~find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks. \smallskip (III) An algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n^{3/2})$ time: (i)~compute an $\sqrt{n}$-approximation for \textsc{Graph Coloring} of $G$ or (ii)~find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks on dense graphs, with $m =ω(n^{9/8})$. \smallskip (IV) The second and third results suggest the following broader research direction: if it is difficult to find (A) or (B) separately, can one find one of the two efficiently? This motivates the \emph{dual pair} concept we introduce. We discuss and provide several instances of dual-pair approximation.
Variety Evasive Subspace Families
Venue: arXiv cs.CC 2024
Year: 2024

We introduce the problem of constructing explicit variety evasive subspace families. Given a family $\mathcal{F}$ of subvarieties of a projective or affine space, a collection $\mathcal{H}$ of projective or affine $k$-subspaces is $(\mathcal{F},ε)$-evasive if for every $\mathcal{V}\in\mathcal{F}$, all but at most $ε$-fraction of $W\in\mathcal{H}$ intersect every irreducible component of $\mathcal{V}$ with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit $k$-subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine $n$-space. As one application, we obtain a complete derandomization of Noether's normalization lemma for varieties of low degree in a projective or affine $n$-space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester-Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a tight lower bound for the size of $k$-subspace families that are evasive for degree-$d$ varieties in a projective $n$-space. When $n-k=n^{Ω(1)}$, the lower bound is superpolynomial unless $d$ is bounded. The proof uses a dimension-counting argument on Chow varieties that parametrize projective subvarieties.
Deep Reinforcement Learning-based Methods for Resource Scheduling in Cloud Computing: A Review and Future Directions
Venue: arXiv cs.DC 2024
Year: 2024

As the quantity and complexity of information processed by software systems increase, large-scale software systems have an increasing requirement for high-performance distributed computing systems. With the acceleration of the Internet in Web 2.0, Cloud computing as a paradigm to provide dynamic, uncertain and elastic services has shown superiorities to meet the computing needs dynamically. Without an appropriate scheduling approach, extensive Cloud computing may cause high energy consumptions and high cost, in addition that high energy consumption will cause massive carbon dioxide emissions. Moreover, inappropriate scheduling will reduce the service life of physical devices as well as increase response time to users' request. Hence, efficient scheduling of resource or optimal allocation of request, that usually a NP-hard problem, is one of the prominent issues in emerging trends of Cloud computing. Focusing on improving quality of service (QoS), reducing cost and abating contamination, researchers have conducted extensive work on resource scheduling problems of Cloud computing over years. Nevertheless, growing complexity of Cloud computing, that the super-massive distributed system, is limiting the application of scheduling approaches. Machine learning, a utility method to tackle problems in complex scenes, is used to resolve the resource scheduling of Cloud computing as an innovative idea in recent years. Deep reinforcement learning (DRL), a combination of deep learning (DL) and reinforcement learning (RL), is one branch of the machine learning and has a considerable prospect in resource scheduling of Cloud computing. This paper surveys the methods of resource scheduling with focus on DRL-based scheduling approaches in Cloud computing, also reviews the application of DRL as well as discusses challenges and future directions of DRL in scheduling of Cloud computing.
Decision Making with Differential Privacy under a Fairness Lens
Venue: arXiv cs.AI 2024
Year: 2024

Agencies, such as the U.S. Census Bureau, release data sets and statistics about groups of individuals that are used as input to a number of critical decision processes. To conform to privacy and confidentiality requirements, these agencies are often required to release privacy-preserving versions of the data. This paper studies the release of differentially private data sets and analyzes their impact on some critical resource allocation tasks under a fairness perspective. {The paper shows that, when the decisions take as input differentially private data}, the noise added to achieve privacy disproportionately impacts some groups over others. The paper analyzes the reasons for these disproportionate impacts and proposes guidelines to mitigate these effects. The proposed approaches are evaluated on critical decision problems that use differentially private census data.
Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs
Venue: arXiv cs.DM 2024
Year: 2024

A conflict-free coloring of a graph $G$ is a (partial) coloring of its vertices such that every vertex $u$ has a neighbor whose assigned color is unique in the neighborhood of $u$. There are two variants of this coloring, one defined using the open neighborhood and one using the closed neighborhood. For both variants, we study the problem of deciding whether the conflict-free coloring of a given graph $G$ is at most a given number $k$. In this work, we investigate the relation of clique-width and minimum number of colors needed (for both variants) and show that these parameters do not bound one another. Moreover, we consider specific graph classes, particularly graphs of bounded clique-width and types of intersection graphs, such as distance hereditary graphs, interval graphs and unit square and disk graphs. We also consider Kneser graphs and split graphs. We give (often tight) upper and lower bounds and determine the complexity of the decision problem on these graph classes, which improve some of the results from the literature. Particularly, we settle the number of colors needed for an interval graph to be conflict-free colored under the open neighborhood model, which was posed as an open problem.
Efficiently Solving High-Order and Nonlinear ODEs with Rational Fraction Polynomial: the Ratio Net
Venue: arXiv cs.LG 2024
Year: 2024

Recent advances in solving ordinary differential equations (ODEs) with neural networks have been remarkable. Neural networks excel at serving as trial functions and approximating solutions within functional spaces, aided by gradient backpropagation algorithms. However, challenges remain in solving complex ODEs, including high-order and nonlinear cases, emphasizing the need for improved efficiency and effectiveness. Traditional methods have typically relied on established knowledge integration to improve problem-solving efficiency. In contrast, this study takes a different approach by introducing a new neural network architecture for constructing trial functions, known as ratio net. This architecture draws inspiration from rational fraction polynomial approximation functions, specifically the Pade approximant. Through empirical trials, it demonstrated that the proposed method exhibits higher efficiency compared to existing approaches, including polynomial-based and multilayer perceptron (MLP) neural network-based methods. The ratio net holds promise for advancing the efficiency and effectiveness of solving differential equations.
Phone-Level Prosody Modelling with GMM-Based MDN for Diverse and Controllable Speech Synthesis
Venue: arXiv cs.SD 2024
Year: 2024

Generating natural speech with a diverse and smooth prosody pattern is a challenging task. Although random sampling with phone-level prosody distribution has been investigated to generate different prosody patterns, the diversity of the generated speech is still very limited and far from what can be achieved by humans. This is largely due to the use of uni-modal distribution, such as single Gaussian, in the prior works of phone-level prosody modelling. In this work, we propose a novel approach that models phone-level prosodies with a GMM-based mixture density network(MDN) and then extend it for multi-speaker TTS using speaker adaptation transforms of Gaussian means and variances. Furthermore, we show that we can clone the prosodies from a reference speech by sampling prosodies from the Gaussian components that produce the reference prosodies. Our experiments on LJSpeech and LibriTTS dataset show that the proposed method with GMM-based MDN not only achieves significantly better diversity than using a single Gaussian in both single-speaker and multi-speaker TTS, but also provides better naturalness. The prosody cloning experiments demonstrate that the prosody similarity of the proposed method with GMM-based MDN is comparable to recent proposed fine-grained VAE while the target speaker similarity is better.
Diffusion-Based Representation Learning
Venue: arXiv cs.LG 2024
Year: 2024

Diffusion-based methods represented as stochastic differential equations on a continuous-time domain have recently proven successful as a non-adversarial generative model. Training such models relies on denoising score matching, which can be seen as multi-scale denoising autoencoders. Here, we augment the denoising score matching framework to enable representation learning without any supervised signal. GANs and VAEs learn representations by directly transforming latent codes to data samples. In contrast, the introduced diffusion-based representation learning relies on a new formulation of the denoising score matching objective and thus encodes the information needed for denoising. We illustrate how this difference allows for manual control of the level of details encoded in the representation. Using the same approach, we propose to learn an infinite-dimensional latent code that achieves improvements of state-of-the-art models on semi-supervised image classification. We also compare the quality of learned representations of diffusion score matching with other methods like autoencoder and contrastively trained systems through their performances on downstream tasks.
ClustML: A Measure of Cluster Pattern Complexity in Scatterplots Learnt from Human-labeled Groupings
Venue: arXiv cs.HC 2024
Year: 2024

Visual quality measures (VQMs) are designed to support analysts by automatically detecting and quantifying patterns in visualizations. We propose a new VQM for visual grouping patterns in scatterplots, called ClustML, which is trained on previously collected human subject judgments. Our model encodes scatterplots in the parametric space of a Gaussian Mixture Model and uses a classifier trained on human judgment data to estimate the perceptual complexity of grouping patterns. The numbers of initial mixture components and final combined groups. It improves on existing VQMs, first, by better estimating human judgments on two-Gaussian cluster patterns and, second, by giving higher accuracy when ranking general cluster patterns in scatterplots. We use it to analyze kinship data for genome-wide association studies, in which experts rely on the visual analysis of large sets of scatterplots. We make the benchmark datasets and the new VQM available for practical use and further improvements.
Rethinking Cross-modal Interaction from a Top-down Perspective for Referring Video Object Segmentation
Venue: arXiv cs.CV 2024
Year: 2024

Referring video object segmentation (RVOS) aims to segment video objects with the guidance of natural language reference. Previous methods typically tackle RVOS through directly grounding linguistic reference over the image lattice. Such bottom-up strategy fails to explore object-level cues, easily leading to inferior results. In this work, we instead put forward a two-stage, top-down RVOS solution. First, an exhaustive set of object tracklets is constructed by propagating object masks detected from several sampled frames to the entire video. Second, a Transformer-based tracklet-language grounding module is proposed, which models instance-level visual relations and cross-modal interactions simultaneously and efficiently. Our model ranks first place on CVPR2021 Referring Youtube-VOS challenge.
MNL-Bandit with Knapsacks: a near-optimal algorithm
Venue: arXiv cs.LG 2024
Year: 2024

We consider a dynamic assortment selection problem where a seller has a fixed inventory of $N$ substitutable products and faces an unknown demand that arrives sequentially over $T$ periods. In each period, the seller needs to decide on the assortment of products (satisfying certain constraints) to offer to the customers. The customer's response follows an unknown multinomial logit model (MNL) with parameter $\boldsymbol{v}$. If customer selects product $i \in [N]$, the seller receives revenue $r_i$. The goal of the seller is to maximize the total expected revenue from the $T$ customers given the fixed initial inventory of $N$ products. We present MNLwK-UCB, a UCB-based algorithm and characterize its regret under different regimes of inventory size. We show that when the inventory size grows quasi-linearly in time, MNLwK-UCB achieves a $\tilde{O}(N + \sqrt{NT})$ regret bound. We also show that for a smaller inventory (with growth $\sim T^α$, $α< 1$), MNLwK-UCB achieves a $\tilde{O}(N(1 + T^{\frac{1 - α}{2}}) + \sqrt{NT})$. In particular, over a long time horizon $T$, the rate $\tilde{O}(\sqrt{NT})$ is always achieved regardless of the constraints and the size of the inventory.
Time-Efficient Algorithms for Nash-Bargaining-Based Matching Market Models
Venue: arXiv cs.GT 2024
Year: 2024

In the area of matching-based market design, existing models using cardinal utilities suffer from two deficiencies: First, the Hylland-Zeckhauser (HZ) mechanism, which has remained a classic in economics for one-sided matching markets, is intractable; computation of even an approximate equilibrium is PPAD-complete. Second, there is an extreme paucity of such models. This led Hosseini and Vazirani (2022) to define a rich collection of Nash-bargaining-based models for one-sided and two-sided matching markets, in both Fisher and Arrow-Debreu settings, together with very fast implementations using available solvers and very encouraging experimental results. In this paper, we give fast algorithms with proven running times for the models introduced by Hosseini and Vazirani, using the techniques of multiplicative weights update (MWU) and conditional gradient descent (CGD). Additionally, we make the following contributions: (1) By Tröbst and Vazirani (2024), a linear one-sided Nash-bargaining-based matching market satisfies envy-freeness within factor two. We show that the other models satisfy approximate equal-share fairness, where the exact factor depends on the utility function being used in the particular model. (2) We define a Nash-bargaining-based model for non-bipartite matching markets and give fast algorithms for it using conditional gradient descent.
3D Human Pose Estimation Based on 2D-3D Consistency with Synchronized Adversarial Training
Venue: arXiv cs.CV 2024
Year: 2024

3D human pose estimation from a single image is still a challenging problem despite the large amount of work that has been performed in this field. Generally, most methods directly use neural networks and ignore certain constraints (e.g., reprojection constraints, joint angle, and bone length constraints). While a few methods consider these constraints but train the network separately, they cannot effectively solve the depth ambiguity problem. In this paper, we propose a GAN-based model for 3D human pose estimation, in which a reprojection network is employed to learn the mapping of the distribution from 3D poses to 2D poses, and a discriminator is employed for 2D-3D consistency discrimination. We adopt a novel strategy to synchronously train the generator, the reprojection network and the discriminator. Furthermore, inspired by the typical kinematic chain space (KCS) matrix, we introduce a weighted KCS matrix and take it as one of the discriminator's inputs to impose joint angle and bone length constraints. The experimental results on Human3.6M show that our method significantly outperforms state-of-the-art methods in most cases.
An App for the Discovery of Properties of Poncelet Triangles
Venue: arXiv cs.GR 2024
Year: 2024

We describe a newly-developed, free, browser-based application, for the interactive exploration of the dynamic geometry of Poncelet families of triangles. The main focus is on responsive display of the beauteous loci of centers of such families, refreshing them smoothly upon any changes in simulation parameters. The app informs the user when curves swept are conics and reports if certain metric quantities are conserved. Live simulations can be easily shared via a URL. A list of more than 400 pre-made experiments is included which can be regarded as conjectures and/or exercises. Millions of experiment combinations are possible.
Cooperative Online Learning with Feedback Graphs
Venue: arXiv cs.LG 2024
Year: 2024

We study the interplay between communication and feedback in a cooperative online learning setting, where a network of communicating agents learn a common sequential decision-making task through a feedback graph. We bound the network regret in terms of the independence number of the strong product between the communication network and the feedback graph. Our analysis recovers as special cases many previously known bounds for cooperative online learning with expert or bandit feedback. We also prove an instance-based lower bound, demonstrating that our positive results are not improvable except in pathological cases. Experiments on synthetic data confirm our theoretical findings.
Backdoor Learning Curves: Explaining Backdoor Poisoning Beyond Influence Functions
Venue: arXiv cs.LG 2024
Year: 2024

Backdoor attacks inject poisoning samples during training, with the goal of forcing a machine learning model to output an attacker-chosen class when presented a specific trigger at test time. Although backdoor attacks have been demonstrated in a variety of settings and against different models, the factors affecting their effectiveness are still not well understood. In this work, we provide a unifying framework to study the process of backdoor learning under the lens of incremental learning and influence functions. We show that the effectiveness of backdoor attacks depends on: (i) the complexity of the learning algorithm, controlled by its hyperparameters; (ii) the fraction of backdoor samples injected into the training set; and (iii) the size and visibility of the backdoor trigger. These factors affect how fast a model learns to correlate the presence of the backdoor trigger with the target class. Our analysis unveils the intriguing existence of a region in the hyperparameter space in which the accuracy on clean test samples is still high while backdoor attacks are ineffective, thereby suggesting novel criteria to improve existing defenses.
A Simple Generative Network
Venue: arXiv cs.LG 2024
Year: 2024

Generative neural networks are able to mimic intricate probability distributions such as those of handwritten text, natural images, etc. Since their inception several models were proposed. The most successful of these were based on adversarial (GAN), auto-encoding (VAE) and maximum mean discrepancy (MMD) relatively complex architectures and schemes. Surprisingly, a very simple architecture (a single feed-forward neural network) in conjunction with an obvious optimization goal (Kullback_Leibler divergence) was apparently overlooked. This paper demonstrates that such a model (denoted SGN for its simplicity) is able to generate samples visually and quantitatively competitive as compared with the fore-mentioned state of the art methods.
Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers
Venue: arXiv cs.MA 2024
Year: 2024

Two-player, constant-sum games are well studied in the literature, but there has been limited progress outside of this setting. We propose Joint Policy-Space Response Oracles (JPSRO), an algorithm for training agents in n-player, general-sum extensive form games, which provably converges to an equilibrium. We further suggest correlated equilibria (CE) as promising meta-solvers, and propose a novel solution concept Maximum Gini Correlated Equilibrium (MGCE), a principled and computationally efficient family of solutions for solving the correlated equilibrium selection problem. We conduct several experiments using CE meta-solvers for JPSRO and demonstrate convergence on n-player, general-sum games.
Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback
Venue: arXiv cs.DC 2024
Year: 2024

Existing committee-based Byzantine state machine replication (SMR) protocols, typically deployed in production blockchains, face a clear trade-off: (1) they either achieve linear communication cost in the happy path, but sacrifice liveness during periods of asynchrony, or (2) they are robust (progress with probability one) but pay quadratic communication cost. We believe this trade-off is unwarranted since existing linear protocols still have asymptotic quadratic cost in the worst case. We design Ditto, a Byzantine SMR protocol that enjoys the best of both worlds: optimal communication on and off the happy path (linear and quadratic, respectively) and progress guarantee under asynchrony and DDoS attacks. We achieve this by replacing the view-synchronization of partially synchronous protocols with an asynchronous fallback mechanism at no extra asymptotic cost. Specifically, we start from HotStuff, a state-of-the-art linear protocol, and gradually build Ditto. As a separate contribution and an intermediate step, we design a 2-chain version of HotStuff, Jolteon, which leverages a quadratic view-change mechanism to reduce the latency of the standard 3-chain HotStuff. We implement and experimentally evaluate all our systems. Notably, Jolteon's commit latency outperforms HotStuff by 200-300ms with varying system size. Additionally, Ditto adapts to the network and provides better performance than Jolteon under faulty conditions and better performance than VABA (a state-of-the-art asynchronous protocol) under faultless conditions. This proves our case that breaking the robustness-efficiency trade-off is in the realm of practicality.