nils-herrmann/clean_scirepeval huggingface dataset:
Decentralized Multi-Armed Bandit Can Outperform Classic Upper Confidence Bound
Authors: Jingxuan Zhu, Ethan Mulle, Christopher Salomon Smith, Ji Liu

This paper studies a decentralized multi-armed bandit problem in a multi-agent network. The problem is simultaneously solved by $N$ agents assuming they face a common set of $M$ arms and share the same mean of each arm’s reward. Each agent can receive information only from its neighbors, where the neighbor relations among the agents are described by a directed graph whose vertices represent agents and whose directed edges depict neighbor relations. A fully decentralized multi-armed bandit algorithm is proposed for each agent, which twists the classic consensus algorithm and upper confidence bound (UCB) algorithm. It is shown that the algorithm guarantees each agent to achieve a better logarithmic asymptotic regret than the classic UCB provided the neighbor graph is strongly connected. The regret can be further improved if the neighbor graph is undirected and connected.
Impossibility results for fair representation
Authors: Tosca Lechner, Nivasini Ananthakrishnan, Sushant Agarwal, Shai Ben-David

With the growing awareness to fairness in machine learning and the realization of the central role that data representation has in data processing tasks, there is an obvious interest in notions of fair data representations. We provide a formal framework for examining the fairness of data representations through the lens of their effect on decisions (mainly classification) made based on data represented that way.  Using that framework, we prove that several desiderata for fair representations cannot be achieved. While some of our conclusions are intuitive, we formulate (and prove) crisp statements of such impossibilities, often contrasting impressions conveyed by many recent works on fair representations.
Practical Bayesian Optimization of Objectives with Conditioning Variables
Authors: Michael Arthur Leopold Pearce, Janis Klaise, Matthew Groves

Bayesian optimization is a class of data efficient model based algorithms typically
focused on global optimization. We consider the more general case where a user is
faced with multiple problems that each need to be optimized conditional on a state
variable, for example given a range of cities with different patient distributions,
we optimize the ambulance locations conditioned on patient distribution. Given partitions of Cifar10,
we optimize CNN hyperparameters for each partition. 
across objectives boosts optimization of each objective in two ways: in modelling by
data sharing across objectives, and also in acquisition by quantifying how a single
point on one objective can provide benefit to all objectives. For this we propose a framework
for conditional optimization: ConBO. This can be built on top of a range of acquisition functions
and we propose a new Hybrid Knowledge Gradient acquisition function. The resulting method is intuitive and
theoretically grounded, performs either similar to or significantly better than recently published works
on a range of problems, and is easily parallelized to collect a batch of points.
Geometric Attention Networks for Small Point Clouds
Authors: Matthew Spellings

Much of the success of deep learning is drawn from building architectures that properly respect underlying symmetry and structure in the data on which they operate—a set of considerations that have been united under the banner of geometric deep learning. Often problems in the physical sciences deal with relatively small sets of points in two- or three-dimensional space wherein translation, rotation, and permutation equivariance are important or even vital for models to be useful in practice. In this work, we present an architecture for deep learning on these small point clouds with rotation and permutation equivariance, composed of a set of products of terms from the geometric algebra and reductions over those products using an attention mechanism. The geometric algebra provides valuable mathematical structure by which to combine vector, scalar, and other types of geometric inputs in a systematic way to account for rotation invariance or covariance, while attention yields a powerful way to impose permutation equivariance. We demonstrate the usefulness of these architectures by training models to solve sample problems relevant to physics, chemistry, and biology.
Beyond Fine-Tuning: Transferring Behavior in Reinforcement Learning
Authors: Víctor Campos, Pablo Sprechmann, Steven Stenberg Hansen, Andre Barreto, Steven Kapturowski, Alex Vitvitskyi, Adria Puigdomenech Badia, Charles Blundell

Designing agents that acquire knowledge autonomously and use it to solve new tasks efficiently is an important challenge in reinforcement learning. Knowledge acquired during an unsupervised pre-training phase is often transferred by fine-tuning neural network weights once rewards are exposed, as is common practice in supervised domains. Given the nature of the reinforcement learning problem, we argue that standard fine-tuning strategies alone are not enough for efficient transfer in challenging domains. We introduce Behavior Transfer (BT), a technique that leverages pre-trained policies for exploration and that is complementary to transferring neural network weights. Our experiments show that, when combined with large-scale pre-training in the absence of rewards, existing intrinsic motivation objectives can lead to the emergence of complex behaviors. These pre-trained policies can then be leveraged by BT to discover better solutions than without pre-training, and combining BT with standard fine-tuning strategies results in additional benefits. The largest gains are generally observed in domains requiring structured exploration, including settings where the behavior of the pre-trained policies is misaligned with the downstream task.
Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
Authors: Meyer Scetbon, Gabriel Peyré, marco cuturi

The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem. Its main goal is to seek an assignment (more generally a coupling matrix) that can register points across otherwise incomparable datasets. As a non-convex and quadratic generalization of optimal transport (OT), GW is NP-hard. Yet, heuristics are known to work reasonably well in practice, the state of the art approach being to solve a sequence of nested regularized OT problems. While popular, that heuristic remains too costly to scale, with cubic complexity in the number of samples $n$. We show in this paper how a recent variant of the Sinkhorn algorithm can substantially speed up the resolution of GW. That variant restricts the set of admissible couplings to those admitting a low rank factorization as the product of two sub-couplings. By updating alternatively each sub-coupling, our algorithm computes a stationary point of the problem in quadratic time with respect to the number of samples. When cost matrices have themselves low rank, our algorithm has time complexity $\mathcal{O}(n)$. We demonstrate the efficiency of our method on simulated and real data.
Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
Authors: Kaiwen Zhou, Lai Tian, Anthony Man-Cho So, James Cheng

The problem of finding near-stationary points in convex optimization has not been adequately studied yet, unlike other optimality measures such as the function value. Even in the deterministic case, the optimal method (OGM-G, due to Kim and Fessler (2021)) has just been discovered recently. In this work, we conduct a systematic study of algorithmic techniques for finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries: (1) we discover a memory-saving variant of OGM-G based on the performance estimation problem approach (Drori and Teboulle, 2014); (2) we design a new accelerated SVRG variant that can simultaneously achieve fast rates for minimizing both the gradient norm and function value; (3) we propose an adaptively regularized accelerated SVRG variant, which does not require the knowledge of some unknown initial constants and achieves near-optimal complexities. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future developments.
Unit Ball Model for Embedding Hierarchical Structures in the Complex Hyperbolic Space
Authors: Huiru Xiao, Caigao JIANG, Yangqiu Song, james Y zhang, Junwu Xiong

Learning the representation of data with hierarchical structures in the hyperbolic space attracts increasing attention in recent years. 
Due to the constant negative curvature, the hyperbolic space resembles tree metrics and captures the tree-like properties naturally, which enables the hyperbolic embeddings to improve over traditional Euclidean models. However, many real-world hierarchically structured data such as taxonomies and multitree networks have varying local structures and they are not trees, thus they do not ubiquitously match the constant curvature property of the hyperbolic space. To address this limitation of hyperbolic embeddings, we explore the complex hyperbolic space, which has the variable negative curvature, for representation learning. Specifically, we propose to learn the embeddings of hierarchically structured data in the unit ball model of the complex hyperbolic space. The unit ball model based embeddings have a more powerful representation capacity to capture a variety of hierarchical structures. Through experiments on synthetic and real-world data, we show that our approach improves over the hyperbolic embedding models significantly.
Improved rates for prediction and identification for partially observed linear dynamical systems
Authors: Holden Lee

Identification of a linear time-invariant dynamical system from partial observations is a fundamental problem in control theory. Particularly challenging are systems exhibiting long-term memory. A natural question is how learn such systems with non-asymptotic statistical rates depending on the inherent dimensionality (order) $d$ of the system, rather than on the possibly much larger memory length. We propose an algorithm that given a single trajectory of length $T$ with gaussian observation noise, learns the system with a near-optimal rate of $\widetilde O\left(\sqrt\frac{d}{T}\right)$ in $\mathcal{H}_2$ error, with only logarithmic, rather than polynomial dependence on memory length. We also give bounds under process noise and improved bounds for learning a realization of the system. Our algorithm is based on multi-scale low-rank approximation: SVD applied to Hankel matrices of geometrically increasing sizes. Our analysis relies on careful application of concentration bounds on the Fourier domain -- we give sharper concentration bounds for sample covariance of correlated inputs and for $\cal H_\infty$ norm estimation, which may be of independent interest.
Learning Division with Neural Arithmetic Logic Modules
Authors: Bhumika Mistry, Katayoun Farrahi, Jonathon Hare

To achieve systematic generalisation, it first makes sense to master simple tasks such as arithmetic. 
Of the four fundamental arithmetic operations (+,-,$\times$,$\div$), division is considered the most difficult for both humans and computers. In this paper we show that robustly learning division in a systematic manner remains a challenge even at the simplest level of dividing two numbers. We propose two novel approaches for division which we call the Neural Reciprocal Unit (NRU) and the Neural Multiplicative Reciprocal Unit (NMRU), and present improvements for an existing division module, the Real Neural Power Unit (Real NPU). Experiments in learning division with input redundancy on 225 different training sets, find that our proposed modifications to the Real NPU obtains an average success of 85.3$\%$ improving over the original by 15.1$\%$. In light of the suggestion above, our NMRU approach can further improve the success to 91.6$\%$.
ML4C: Seeing Causality Through Latent Vicinity
Authors: Haoyue Dai, Rui Ding, Yuanyuan Jiang, Shi Han, Dongmei Zhang

Supervised Causal Learning (SCL) aims to learn causal relations from observational data by accessing previously seen datasets associated with ground truth causal relations. This paper presents a first attempt at addressing a fundamental question: What are the benefits from supervision and how does it benefit? Starting from seeing that SCL is not better than random guessing if the learning target is non-identifiable a priori, we propose a two-phase paradigm for SCL by explicitly considering structure identifiability. Following this paradigm, we tackle the problem of SCL on discrete data and propose ML4C. The core of ML4C is a binary classifier with a novel learning target: it classifies whether an Unshielded Triple (UT) is a v-structure or not. Starting from an input dataset with the corresponding skeleton provided, ML4C orients each UT once it is classified as a v-structure. These v-structures are together used to construct the final output. To address the fundamental question of SCL, we propose a principled method for ML4C featurization: we exploit the vicinity of a given UT (i.e., the neighbors of UT in skeleton), and derive features by considering the conditional dependencies and structural entanglement within the vicinity. We further prove that ML4C is asymptotically perfect. Last but foremost, thorough experiments conducted on benchmark datasets demonstrate that ML4C remarkably outperforms other state-of-the-art algorithms in terms of accuracy, robustness and transferability. In summary, ML4C shows promising results on validating the effectiveness of supervision for causal learning.
Optimal detection of the feature matching map in presence of noise and outliers
Authors: Tigran Galstyan, Arshak Minasyan, Arnak S. Dalalyan

We consider the problem of finding the matching map between two sets of $d$-dimensional vectors from noisy observations, where the second set contains outliers. The matching map is then an injection, which can be consistently estimated only if the vectors of the second set are well separated. The main result shows that, in the high-dimensional setting, a detection region of unknown injection may be characterized by the sets of vectors for which the inlier-inlier distance is of order at least $d^{1/4}$ and the inlier-outlier distance is of order at least $d^{1/2}$. These rates are achieved using the estimated matching minimizing the sum of logarithms of distances between matched pairs of points. We also prove corresponding lower bounds establishing optimality. Finally, we report the results of numerical experiments on both synthetic and real world data that illustrate our theoretical results and provide further insight into the properties of the estimators studied in this work.
Unsupervised Dynamic Routing Via Competition Over Network Loss
Authors: Lei Zhao, Lin Wang, Jiuqiao Yu

This paper proposes a novel neural network architecture that can simultaneously do normal network optimizing while attaining the ability of unsupervised learning. Almost all existing unsupervised learning algorithms are based on doing calculations on the input space or feature space, this paper proposes a new possibility to discover a structure in the functional space without supervision. Using the self-organizing map over the competition of the loss of individual neural column, we route the input to the most appropriate modules dynamically, by doing this we separate the input functional space into different sub spaces which are represented by each individual neural column. At the end of the paper, we propose several possible architectures based on the philosophy of this paper that could build a neural network system block by block.
Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment
Authors: Cheng Yang, Gene Cheung, Wai-tian Tan, Guangtao Zhai

In semi-supervised graph-based binary classifier learning, a subset of known labels $\hat{x}_i$ are used to infer unknown labels, assuming that the label signal $\x$ is smooth with respect to a similarity graph specified by a Laplacian matrix.
When restricting labels $x_i$ to binary values, the problem is NP-hard.
While a conventional semi-definite programming (SDP) relaxation can be solved in polynomial time using, for example, the alternating direction method of multipliers (ADMM), the complexity of iteratively projecting a candidate matrix $\M$ onto the positive semi-definite (PSD) cone ($\M \succeq 0$) remains high.
In this paper, leveraging a recent linear algebraic theory called Gershgorin disc perfect alignment (GDPA), we propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
Specifically, we first recast the SDP relaxation to its SDP dual, where a feasible solution $\H \succeq 0$ can be interpreted as a Laplacian matrix corresponding to a balanced signed graph sans the last node.
To achieve graph balance, we split the last node into two that respectively contain the original positive and negative edges, resulting in a new Laplacian $\bar{\H}$.
We repose the SDP dual for solution $\bar{\H}$, then replace the PSD cone constraint $\bar{\H} \succeq 0$ with linear constraints derived from GDPA---sufficient conditions to ensure $\bar{\H}$ is PSD---so that the optimization becomes an LP per iteration.
Finally, we extract predicted labels from our converged LP solution $\bar{\H}$. 
Experiments show that our algorithm enjoyed a $40\times$ speedup on average over the next fastest scheme while retaining comparable label prediction performance.
Principal Components Bias in Deep Neural Networks
Authors: Guy Hacohen, Daphna Weinshall

Recent work suggests that convolutional neural networks of different architectures learn to classify images in the same order. To understand this phenomenon, we revisit the over-parametrized deep linear network model. Our asymptotic analysis, assuming that the hidden layers are wide enough, reveals that the convergence rate of this model's parameters is exponentially faster along directions corresponding to the larger principal components of the data, at a rate governed by the singular values. We term this convergence pattern the Principal Components bias (PC-bias). We show how the PC-bias streamlines the order of learning of both linear and non-linear networks, more prominently at earlier stages of learning. We then compare our results to the spectral bias, showing that both biases can be seen independently, and affect the order of learning in different ways. Finally, we discuss how the PC-bias may explain some benefits of early stopping and its connection to PCA, and why deep networks converge more slowly when given random labels.