OpenRaiser/Intern-Atlas huggingface dataset:
Sketching approximability of all finite CSPs
Venue: arXiv cs.CC 2024
Year: 2024

A constraint satisfaction problem (CSP), $\textsf{Max-CSP}(\mathcal{F})$, is specified by a finite set of constraints $\mathcal{F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from $\mathcal{F}$ to subsequences of the $n$ variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the $(γ,β)$-approximation version of the problem for parameters $0 \leq β< γ\leq 1$, the goal is to distinguish instances where at least $γ$ fraction of the constraints can be satisfied from instances where at most $β$ fraction of the constraints can be satisfied. In this work we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family $\mathcal{F}$ and every $β< γ$, we show that either a linear sketching algorithm solves the problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in $o(\sqrt{n})$ space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of $q=k=2$, where we get a dichotomy, and the case when the satisfying assignments of the constraints of $\mathcal{F}$ support a distribution on $[q]^k$ with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables $q=2$, binary constraints $k=2$, singleton families $|\mathcal{F}|=1$ and only considered the setting where constraints are placed on literals rather than variables.
Makespan Trade-offs for Visiting Triangle Edges
Venue: arXiv cs.DM 2024
Year: 2024

We study a primitive vehicle routing-type problem in which a fleet of $n$unit speed robots start from a point within a non-obtuse triangle $Δ$, where $n \in \{1,2,3\}$. The goal is to design robots' trajectories so as to visit all edges of the triangle with the smallest visitation time makespan. We begin our study by introducing a framework for subdividing $Δ$into regions with respect to the type of optimal trajectory that each point $P$ admits, pertaining to the order that edges are visited and to how the cost of the minimum makespan $R_n(P)$ is determined, for $n\in \{1,2,3\}$. These subdivisions are the starting points for our main result, which is to study makespan trade-offs with respect to the size of the fleet. In particular, we define $ R_{n,m} (Δ)= \max_{P \in Δ} R_n(P)/R_m(P)$, and we prove that, over all non-obtuse triangles $Δ$: (i) $R_{1,3}(Δ)$ ranges from $\sqrt{10}$ to $4$, (ii) $R_{2,3}(Δ)$ ranges from $\sqrt{2}$ to $2$, and (iii) $R_{1,2}(Δ)$ ranges from $5/2$ to $3$. In every case, we pinpoint the starting points within every triangle $Δ$ that maximize $R_{n,m} (Δ)$, as well as we identify the triangles that determine all $\inf_ΔR_{n,m}(Δ)$ and $\sup_ΔR_{n,m}(Δ)$ over the set of non-obtuse triangles.
Universal Online Convex Optimization Meets Second-order Bounds
Venue: arXiv cs.LG 2024
Year: 2024

Recently, several universal methods have been proposed for online convex optimization, and attain minimax rates for multiple types of convex functions simultaneously. However, they need to design and optimize one surrogate loss for each type of functions, making it difficult to exploit the structure of the problem and utilize existing algorithms. In this paper, we propose a simple strategy for universal online convex optimization, which avoids these limitations. The key idea is to construct a set of experts to process the original online functions, and deploy a meta-algorithm over the linearized losses to aggregate predictions from experts. Specifically, the meta-algorithm is required to yield a second-order bound with excess losses, so that it can leverage strong convexity and exponential concavity to control the meta-regret. In this way, our strategy inherits the theoretical guarantee of any expert designed for strongly convex functions and exponentially concave functions, up to a double logarithmic factor. As a result, we can plug in off-the-shelf online solvers as black-box experts to deliver problem-dependent regret bounds. For general convex functions, it maintains the minimax optimality and also achieves a small-loss bound. Furthermore, we extend our universal strategy to online composite optimization, where the loss function comprises a time-varying function and a fixed regularizer. To deal with the composite loss functions, we employ a meta-algorithm based on the optimistic online learning framework, which not only possesses a second-order bound, but also can utilize estimations for upcoming loss functions. With appropriate configurations, we demonstrate that the additional regularizer does not contribute to the meta-regret, thus maintaining the universality in the composite setting.
Type-Based Termination for Futures
Venue: arXiv cs.PL 2024
Year: 2024

In sequential functional languages, sized types enable termination checking of programs with complex patterns of recursion in the presence of mixed inductive-coinductive types. In this paper, we adapt sized types and their metatheory to the concurrent setting. We extend the semi-axiomatic sequent calculus, a subsuming paradigm for futures-based functional concurrency, and its underlying operational semantics with recursion and arithmetic refinements. The latter enables a new and highly general sized type scheme we call sized type refinements. As a widely applicable technical device, we type recursive programs with infinitely deep typing derivations that unfold all recursive calls. Then, we observe that certain such derivations can be made infinitely wide but finitely deep. The resulting trees serve as the induction target of our termination result, which we develop via a novel logical relations argument.
Learning Weakly Convex Sets in Metric Spaces
Venue: arXiv cs.LG 2024
Year: 2024

One of the central problems studied in the theory of machine learning is the question of whether, for a given class of hypotheses, it is possible to efficiently find a {consistent} hypothesis, i.e., which has zero training error. While problems involving {\em convex} hypotheses have been extensively studied, the question of whether efficient learning is possible for non-convex hypotheses composed of possibly several disconnected regions is still less understood. Although it has been shown quite a while ago that efficient learning of weakly convex hypotheses, a parameterized relaxation of convex hypotheses, is possible for the special case of Boolean functions, the question of whether this idea can be developed into a generic paradigm has not been studied yet. In this paper, we provide a positive answer and show that the consistent hypothesis finding problem can indeed be solved in polynomial time for a broad class of weakly convex hypotheses over metric spaces. To this end, we propose a general domain-independent algorithm for finding consistent weakly convex hypotheses and prove sufficient conditions for its efficiency that characterize the corresponding hypothesis classes. To illustrate our general algorithm and its properties, we discuss several non-trivial learning examples to demonstrate how it can be used to efficiently solve the corresponding consistent hypothesis finding problem. Without the weak convexity constraint, these problems are known to be computationally intractable. We then proceed to show that the general idea of our algorithm can even be extended to the case of extensional weakly convex hypotheses, as it naturally arise, e.g., when performing vertex classification in graphs. We prove that using our extended algorithm, the problem can be solved in polynomial time provided the distances in the domain can be computed efficiently.
Byzantine-Resilient Population Protocols
Venue: arXiv cs.DC 2024
Year: 2024

Population protocols model information spreading and computation in network systems where pairwise node exchanges are determined by an external random scheduler and nodes have small memory. Most of the population protocols in the literature assume that the participating $n$ nodes are honest. Such an assumption may not be, however, accurate for large-scale systems of small devices. Hence, in this work, we study population protocols in a setting where up to $f$ nodes can be Byzantine. We examine the majority (binary) consensus problem against different levels of adversary strengths, ranging from the Full Byzantine adversary that has complete knowledge of all the node states to the Weak Content-Oblivious Byzantine adversary that has only knowledge about which exchanges take place. We also take into account Dynamic vs Static node corruption by the adversary. We give lower bounds that require any algorithm solving the majority consensus to have initial difference $d = Ω(f + 1)$ for the tally between the two proposed values, which holds for both the Full Static and Weak Dynamic adversaries. We then present an algorithm that solves the majority consensus problem and tolerates $f \leq n / c$ Byzantine nodes, for some constant $c>0$, with $d = Ω(f + \sqrt{n \log n})$ and $O(\log^3 n)$ parallel time steps, using $O(\log^3 n)$ states per node. We also give an alternative algorithm, with the same asymptotic performance, for $d = Ω(\min\{f \log^2 n + 1,n\})$. Finally, we combine both algorithms into one using a new robust distributed common coin. The only other known previous work on Byzantine-resilient population protocols tolerates up to $f = o(\sqrt n)$ faulty nodes and was analyzed against a Static adversary; hence, our protocols significantly improve fault-tolerance by an $ω(\sqrt n)$ factor and all of them work correctly against a stronger Dynamic adversary.
Position-Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions
Venue: arXiv cs.LG 2024
Year: 2024

Most existing graph neural networks (GNNs) learn node embeddings using the framework of message passing and aggregation. Such GNNs are incapable of learning relative positions between graph nodes within a graph. To empower GNNs with the awareness of node positions, some nodes are set as anchors. Then, using the distances from a node to the anchors, GNNs can infer relative positions between nodes. However, P-GNNs arbitrarily select anchors, leading to compromising position-awareness and feature extraction. To eliminate this compromise, we demonstrate that selecting evenly distributed and asymmetric anchors is essential. On the other hand, we show that choosing anchors that can aggregate embeddings of all the nodes within a graph is NP-complete. Therefore, devising efficient optimal algorithms in a deterministic approach is practically not feasible. To ensure position-awareness and bypass NP-completeness, we propose Position-Sensing Graph Neural Networks (PSGNNs), learning how to choose anchors in a back-propagatable fashion. Experiments verify the effectiveness of PSGNNs against state-of-the-art GNNs, substantially improving performance on various synthetic and real-world graph datasets while enjoying stable scalability. Specifically, PSGNNs on average boost AUC more than 14% for pairwise node classification and 18% for link prediction over the existing state-of-the-art position-aware methods. Our source code is publicly available at: https://github.com/ZhenyueQin/PSGNN.
The Power of Sampling: Dimension-free Risk Bounds in Private ERM
Venue: arXiv cs.LG 2024
Year: 2024

Differentially private empirical risk minimization (DP-ERM) is a fundamental problem in private optimization. While the theory of DP-ERM is well-studied, as large-scale models become prevalent, traditional DP-ERM methods face new challenges, including (1) the prohibitive dependence on the ambient dimension, (2) the highly non-smooth objective functions, (3) costly first-order gradient oracles. Such challenges demand rethinking existing DP-ERM methodologies. In this work, we show that the regularized exponential mechanism combined with existing samplers can address these challenges altogether: under the standard unconstrained domain and low-rank gradients assumptions, our algorithm can achieve rank-dependent risk bounds for non-smooth convex objectives using only zeroth order oracles, which was not accomplished by prior methods. This highlights the power of sampling in differential privacy. We further construct lower bounds, demonstrating that when gradients are full-rank, there is no separation between the constrained and unconstrained settings. Our lower bound is derived from a general black-box reduction from unconstrained to the constrained domain and an improved lower bound in the constrained setting, which might be of independent interest.
One-shot learning of paired association navigation with biologically plausible schemas
Venue: arXiv cs.NE 2024
Year: 2024

Schemas are knowledge structures that can enable rapid learning. Rodent one-shot learning in a multiple paired association navigation task has been postulated to be schema-dependent. We still only poorly understand how schemas, conceptualized at Marr's computational level, are neurally implemented. Moreover, a biologically plausible computational model of the rodent learning has not been demonstrated. Accordingly, we here compose an agent from schemas with biologically plausible neural implementations. The agent gradually learns a metric representation of its environment using a path integration temporal difference error, allowing it to localize in any environment. Additionally, the agent contains an associative memory that can stably form numerous one-shot associations between sensory cues and goal coordinates, implemented with a feedforward layer or a reservoir of recurrently connected neurons whose plastic output weights are governed by a 4-factor reward-modulated Exploratory Hebbian (EH) rule. A third network performs vector subtraction between the agent's current and goal location to decide the direction of movement. We further show that schemas supplemented by an actor-critic allows the agent to succeed even if an obstacle prevents direct heading, and that temporal-difference learning of a working memory gating mechanism enables one-shot learning despite distractors. Our agent recapitulates learning behavior observed in experiments and provides testable predictions that can be probed in future experiments.
Cross-Subject Domain Adaptation for Classifying Working Memory Load with Multi-Frame EEG Images
Venue: arXiv cs.LG 2024
Year: 2024

Working memory (WM), denoting the information temporally stored in the mind, is a fundamental research topic in the field of human cognition. Electroencephalograph (EEG), which can monitor the electrical activity of the brain, has been widely used in measuring the level of WM. However, one of the critical challenges is that individual differences may cause ineffective results, especially when the established model meets an unfamiliar subject. In this work, we propose a cross-subject deep adaptation model with spatial attention (CS-DASA) to generalize the workload classifications across subjects. First, we transform EEG time series into multi-frame EEG images incorporating spatial, spectral, and temporal information. First, the Subject-Shared module in CS-DASA receives multi-frame EEG image data from both source and target subjects and learns the common feature representations. Then, in the subject-specific module, the maximum mean discrepancy is implemented to measure the domain distribution divergence in a reproducing kernel Hilbert space, which can add an effective penalty loss for domain adaptation. Additionally, the subject-to-subject spatial attention mechanism is employed to focus on the discriminative spatial features from the target image data. Experiments conducted on a public WM EEG dataset containing 13 subjects show that the proposed model is capable of achieving better performance than existing state-of-the-art methods.
Alignment and Comparison of Directed Networks via Transition Couplings of Random Walks
Venue: arXiv cs.LG 2024
Year: 2024

We describe and study a transport based procedure called NetOTC (network optimal transition coupling) for the comparison and alignment of two networks. The networks of interest may be directed or undirected, weighted or unweighted, and may have distinct vertex sets of different sizes. Given two networks and a cost function relating their vertices, NetOTC finds a transition coupling of their associated random walks having minimum expected cost. The minimizing cost quantifies the difference between the networks, while the optimal transport plan itself provides alignments of both the vertices and the edges of the two networks. Coupling of the full random walks, rather than their marginal distributions, ensures that NetOTC captures local and global information about the networks, and preserves edges. NetOTC has no free parameters, and does not rely on randomization. We investigate a number of theoretical properties of NetOTC and present experiments establishing its empirical performance.
Customizing Graph Neural Networks using Path Reweighting
Venue: arXiv cs.LG 2024
Year: 2024

Graph Neural Networks (GNNs) have been extensively used for mining graph-structured data with impressive performance. However, because these traditional GNNs do not distinguish among various downstream tasks, embeddings embedded by them are not always effective. Intuitively, paths in a graph imply different semantics for different downstream tasks. Inspired by this, we design a novel GNN solution, namely Customized Graph Neural Network with Path Reweighting (CustomGNN for short). Specifically, the proposed CustomGNN can automatically learn the high-level semantics for specific downstream tasks to highlight semantically relevant paths as well to filter out task-irrelevant noises in a graph. Furthermore, we empirically analyze the semantics learned by CustomGNN and demonstrate its ability to avoid the three inherent problems in traditional GNNs, i.e., over-smoothing, poor robustness, and overfitting. In experiments with the node classification task, CustomGNN achieves state-of-the-art accuracies on three standard graph datasets and four large graph datasets. The source code of the proposed CustomGNN is available at \url{https://github.com/cjpcool/CustomGNN}.
Software-Based Dialogue Systems: Survey, Taxonomy and Challenges
Venue: arXiv cs.CL 2024
Year: 2024

The use of natural language interfaces in the field of human-computer interaction is undergoing intense study through dedicated scientific and industrial research. The latest contributions in the field, including deep learning approaches like recurrent neural networks, the potential of context-aware strategies and user-centred design approaches, have brought back the attention of the community to software-based dialogue systems, generally known as conversational agents or chatbots. Nonetheless, and given the novelty of the field, a generic, context-independent overview on the current state of research of conversational agents covering all research perspectives involved is missing. Motivated by this context, this paper reports a survey of the current state of research of conversational agents through a systematic literature review of secondary studies. The conducted research is designed to develop an exhaustive perspective through a clear presentation of the aggregated knowledge published by recent literature within a variety of domains, research focuses and contexts. As a result, this research proposes a holistic taxonomy of the different dimensions involved in the conversational agents' field, which is expected to help researchers and to lay the groundwork for future research in the field of natural language interfaces.
Recent Deep Semi-supervised Learning Approaches and Related Works
Venue: arXiv cs.LG 2024
Year: 2024

This work proposes an overview of the recent semi-supervised learning approaches and related works. Despite the remarkable success of neural networks in various applications, there exist a few formidable constraints, including the need for a large amount of labeled data. Therefore, semi-supervised learning, which is a learning scheme in which scarce labels and a larger amount of unlabeled data are utilized to train models (e.g., deep neural networks), is getting more important. Based on the key assumptions of semi-supervised learning, which are the manifold assumption, cluster assumption, and continuity assumption, the work reviews the recent semi-supervised learning approaches. In particular, the methods in regard to using deep neural networks in a semi-supervised learning setting are primarily discussed. In addition, the existing works are first classified based on the underlying idea and explained, then the holistic approaches that unify the aforementioned ideas are detailed.
Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
Venue: arXiv cs.DS 2024
Year: 2024

The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition, which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set.
The Role of Contextual Information in Best Arm Identification
Venue: arXiv cs.LG 2024
Year: 2024

We study the best-arm identification problem with fixed confidence when contextual (covariate) information is available in stochastic bandits. Although we can use contextual information in each round, we are interested in the marginalized mean reward over the contextual distribution. Our goal is to identify the best arm with a minimal number of samplings under a given value of the error rate. We show the instance-specific sample complexity lower bounds for the problem. Then, we propose a context-aware version of the "Track-and-Stop" strategy, wherein the proportion of the arm draws tracks the set of optimal allocations and prove that the expected number of arm draws matches the lower bound asymptotically. We demonstrate that contextual information can be used to improve the efficiency of the identification of the best marginalized mean reward compared with the results of Garivier & Kaufmann (2016). We experimentally confirm that context information contributes to faster best-arm identification.