A core element in decision-making under uncertainty is the feedback on the quality of the performed actions. However, in many applications, such feedback is restricted. For example, in recommendation systems, repeatedly asking the user to provide feedback on the quality of recommendations will annoy them. In this work, we formalize decision-making problems with querying budget, where there is a (possibly time-dependent) hard limit on the number of reward queries allowed. Specifically, we consider multi-armed bandits, linear bandits, and reinforcement learning problems. We start by analyzing the performance of `greedy' algorithms that query a reward whenever they can. We show that in fully stochastic settings, doing so performs surprisingly well, but in the presence of any adversity, this might lead to linear regret. To overcome this issue, we propose the Confidence-Budget Matching (CBM) principle that queries rewards when the confidence intervals are wider than the inverse square root of the available budget. We analyze the performance of CBM based algorithms in different settings and show that they perform well in the presence of adversity in the contexts, initial states, and budgets.

Spiking Neural Networks (SNNs) offer a novel computational paradigm that captures some of the efficiency of biological brains by processing through binary neural dynamic activations. Probabilistic SNN models are typically trained to maximize the likelihood of the desired outputs by using unbiased estimates of the log-likelihood gradients. While prior work used single-sample estimators obtained from a single run of the network, this paper proposes to leverage multiple compartments that sample independent spiking signals while sharing synaptic weights. The key idea is to use these signals to obtain more accurate statistical estimates of the log-likelihood training criterion, as well as of its gradient. The approach is based on generalized expectation-maximization (GEM), which optimizes a tighter approximation of the log-likelihood using importance sampling. The derived online learning algorithm implements a three-factor rule with global per-compartment learning signals. Experimental results on a classification task on the neuromorphic MNIST-DVS data set demonstrate significant improvements in terms of log-likelihood, accuracy, and calibration when increasing the number of compartments used for training and inference.

The ability to use symbols is the pinnacle of human intelligence, but has yet to be fully replicated in machines. Here we argue that the path towards symbolically fluent artificial intelligence (AI) begins with a reinterpretation of what symbols are, how they come to exist, and how a system behaves when it uses them. We begin by offering an interpretation of symbols as entities whose meaning is established by convention. But crucially, something is a symbol only for those who demonstrably and actively participate in this convention. We then outline how this interpretation thematically unifies the behavioural traits humans exhibit when they use symbols. This motivates our proposal that the field place a greater emphasis on symbolic behaviour rather than particular computational mechanisms inspired by more restrictive interpretations of symbols. Finally, we suggest that AI research explore social and cultural engagement as a tool to develop the cognitive machinery necessary for symbolic behaviour to emerge. This approach will allow for AI to interpret something as symbolic on its own rather than simply manipulate things that are only symbols to human onlookers, and thus will ultimately lead to AI with more human-like symbolic fluency.

We present the ARC-DA dataset, a direct-answer ("open response", "freeform") version of the ARC (AI2 Reasoning Challenge) multiple-choice dataset. While ARC has been influential in the community, its multiple-choice format is unrepresentative of real-world questions, and multiple choice formats can be particularly susceptible to artifacts. The ARC-DA dataset addresses these concerns by converting questions to direct-answer format using a combination of crowdsourcing and expert review. The resulting dataset contains 2985 questions with a total of 8436 valid answers (questions typically have more than one valid answer). ARC-DA is one of the first DA datasets of natural questions that often require reasoning, and where appropriate question decompositions are not evident from the questions themselves. We describe the conversion approach taken, appropriate evaluation metrics, and several strong models. Although high, the best scores (81% GENIE, 61.4% F1, 63.2% ROUGE-L) still leave considerable room for improvement. In addition, the dataset provides a natural setting for new research on explanation, as many questions require reasoning to construct answers. We hope the dataset spurs further advances in complex question-answering by the community. ARC-DA is available at https://allenai.org/data/arc-da

There has been an increasing interest in harnessing deep learning to tackle combinatorial optimization (CO) problems in recent years. Typical CO deep learning approaches leverage the problem structure in the model architecture. Nevertheless, the model selection is still mainly based on the conventional machine learning setting. Due to the discrete nature of CO problems, a single model is unlikely to learn the problem entirely. We introduce ZTop, which stands for Zero Training Overhead Portfolio, a simple yet effective model selection and ensemble mechanism for learning to solve combinatorial problems. ZTop is inspired by algorithm portfolios, a popular CO ensembling strategy, particularly restart portfolios, which periodically restart a randomized CO algorithm, de facto exploring the search space with different heuristics. We have observed that well-trained models acquired in the same training trajectory, with similar top validation performance, perform well on very different validation instances. Following this observation, ZTop ensembles a set of well-trained models, each providing a unique heuristic with zero training overhead, and applies them, sequentially or in parallel, to solve the test instances. We show how ZTopping, i.e., using a ZTop ensemble strategy with a given deep learning approach, can significantly improve the performance of the current state-of-the-art deep learning approaches on three prototypical CO domains, the hardest unique-solution Sudoku instances, challenging routing problems, and the graph maximum cut problem, as well as on multi-label classification, a machine learning task with a large combinatorial label space.

In chaotic modern society, there is an increasing demand for the realization of true 'fairness'. In Greek mythology, Themis, the 'goddess of justice', has a sword in her right hand to protect society from vices, and a 'balance of judgment' in her left hand that measures good and evil. In this study, we propose a fair distribution method 'utilising physics' for the profit in games of characteristic function form. Specifically, we show that the linear programming problem for calculating 'nucleolus' can be efficiently solved by considering it as a physical system in which gravity works. In addition to being able to significantly reduce computational complexity thereby, we believe that this system could have flexibility necessary to respond to real-time changes in the parameter.

There's no one-size-fits-all diet. If you want to avoid spiking your blood sugar with a snack, a banana may seem like a better choice than a sugary cookie. But some people in a 2015 study of 800 Israeli volunteers got their biggest blood sugar spike from bananas or bread instead of from sugar-laden baked goods. And as nutrition scientist Elizabeth Parks of the University of Missouri, Columbia, notes, “We all know people who lose weight easily, and others who don't.” Now, the U.S. National Institutes of Health (NIH) is making a major push to understand these individual differences. Last week, the agency announced what it calls the largest study yet to probe “precision nutrition,” a $156 million, 5-year effort to examine how 10,000 Americans process foods by collecting data ranging from continuous blood glucose levels to microbes in a person's gut. The study “has the potential to truly transform the field of nutrition science,” generating new tools, methods, and “a wealth of data to fuel discovery science for years to come,” Griffin Rodgers, director of the National Institute of Diabetes and Digestive and Kidney Diseases (NIDDK), said last year at an NIH board meeting where he introduced the project. Ultimately, it might enable nutritionists to tailor diets to an individual's genes and microbiome. It is part of a broader push at NIH to boost nutrition science, a field sometimes viewed as “fuzzy” because “we are free-range eaters” and our diets are hard to control, notes Paul Coates, vice president of the American Society for Nutrition, who headed NIH's dietary supplements office until he retired in 2018. In May 2020, NIH Director Francis Collins released the agency's first-ever 10-year strategic plan for nutrition science, acknowledging the importance of diet in chronic diseases such as heart disease and diabetes. The plan aims to fold in basic disciplines such as neurobiology, study the role of diet throughout life, consider how food can serve as medicine, and elevate precision nutrition. The concept recognizes that how the human body responds to food depends on factors from genetics to sleep habits, social environment, and gut microbes. For example, the Israeli study that found individual differences in the response to refined sugar versus fruit showed the microbiome was largely responsible. Now comes NIH's Nutrition for Precision Health, which will piggyback on All of Us, the agency's huge genomics and health study, which has fully enrolled 272,000 of a planned 1 million participants, more than 50% from minority groups. “We realized it would be a really great fit” to take advantage of the All of Us data and infrastructure, says Holly Nicastro, a study coordinator and program director at NIH's nutrition office. Some 10,000 All of Us participants who join the nutrition study will wear various monitors to track physical activity, blood sugar, and more; record what they eat; and visit a clinic to consume a specific meal and undergo clinical tests. A subset of up to 1500 will also follow three different diets at home or in the clinic, and then have the same tests. And 500 to 1000 volunteers will live at a clinical center for three 2-week stretches while eating three tightly prescribed diets. Such “controlled feeding” studies are the field's gold standard, but their high cost usually keeps them small. NIH has recently conducted some in its clinical center to explore, for example, the effects of ultraprocessed foods, but they involved only 20 people. By collecting a wide range of personal data, from participants' DNA makeup to their ZIP code, “we are removing a lot of that ‘noise’ that we had for years, created by the factors that we were not measuring before,” says Tufts University nutrition scientist José Ordovás who, with Parks, co-chaired a workshop last month to discuss the study. Artificial intelligence researchers will then use the collected data to create models that predict the best diet for an individual—an effort pioneered by the Israeli study, which spun off a company that developed an algorithm to tailor diets for people who are diabetic or trying to lose weight. A second, 5-year phase could test those models in clinical trials. NIH is now inviting proposals for study components such as a data center, clinical centers, and a microbiome center. The aim is to begin enrolling volunteers by January 2023. “There's so much excitement” about the study, Parks says. She and other nutritionists also welcome other signals of NIH's new focus. Its Office of Nutrition Research, once part of the NIH director's office, was demoted years ago to NIDDK. Last month, Collins announced it has been restored. Coates hopes that will mean a larger staff—the office now has just six people—and a modest budget to cofund studies with NIH institutes. “A lot [of nutrition science] falls between the cracks,” he says—gaps he now hopes will close.

In many applications of machine learning, such as recommender systems, where an input characterizing a user should be matched with a target representing an ordering of a large number of items, accessing fully supervised data (,) is not an option. Instead, one should expect weak information on the target, which could be a list of previously taken (if items are online courses), watched (if items are plays), etc., items by a user characterized by the feature vector. This motivates weakly supervised learning, aiming at learning a mapping from inputs to targets in such a setting where tools from supervised learning can not be applied off-the-shelves. Recent applications of weakly supervised learning showcase impressive results in solving complex tasks such as action retrieval on instructional videos (Miech et al., 2019), image semantic segmentation (Papandreou et al., 2015), salient object detection (Wang et al., 2017), 3D pose estimation (Dabral et al., 2018), text-to-speech synthesis (Jia et al., 2018), to name a few. However, those applications of weakly supervised learning are usually based on clever heuristics, and theoretical foundations of learning from weakly supervised data are scarce, especially when compared to statistical learning literature on supervised learning (Vapnik, 1995; Boucheron et al., 2005; Steinwart and Christmann, 2008). We aim to provide a step in this direction. In this paper, we focus on partial labelling, a popular instance of weak supervision, approached with a structured prediction point of view Ciliberto et al. (2020). We detail this setup in Section 2. Our contributions are organized as follows.

We propose a novel framework for modeling multiple multivariate point processes, each with heterogeneous event types that share an underlying space and obey the same generative mechanism. Focusing on Hawkes processes and their variants that are associated with Granger causality graphs, our model leverages an uncountable event type space and samples the graphs with different sizes from a nonparametric model called {\it graphon}. Given those graphs, we can generate the corresponding Hawkes processes and simulate event sequences. Learning this graphon-based Hawkes process model helps to 1) infer the underlying relations shared by different Hawkes processes; and 2) simulate event sequences with different event types but similar dynamics. We learn the proposed model by minimizing the hierarchical optimal transport distance between the generated event sequences and the observed ones, leading to a novel reward-augmented maximum likelihood estimation method. We analyze the properties of our model in-depth and demonstrate its rationality and effectiveness in both theory and experiments.

Federated Distillation (FD) is a popular novel algorithmic paradigm for Federated Learning, which achieves training performance competitive to prior parameter averaging based methods, while additionally allowing the clients to train different model architectures, by distilling the client predictions on an unlabeled auxiliary set of data into a student model. In this work we propose FedAUX, an extension to FD, which, under the same set of assumptions, drastically improves performance by deriving maximum utility from the unlabeled auxiliary data. FedAUX modifies the FD training procedure in two ways: First, unsupervised pre-training on the auxiliary data is performed to find a model initialization for the distributed training. Second, $(\varepsilon, \delta)$-differentially private certainty scoring is used to weight the ensemble predictions on the auxiliary data according to the certainty of each client model. Experiments on large-scale convolutional neural networks and transformer models demonstrate, that the training performance of FedAUX exceeds SOTA FL baseline methods by a substantial margin in both the iid and non-iid regime, further closing the gap to centralized training performance. Code is available at github.com/fedl-repo/fedaux.