item
A Smooth Computational Transition in Tensor PCA
We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order-$p$ tensor PCA problem where $p \geq 3$ is a fixed integer, we show that when the signal-to-noise ratio is $λn^{-\frac{p}{4}}$ where $λ=Ω(1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$ where $C=C(λ)$ is a constant depending on $λ$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy \cite{HSS15} or based on the Kikuchi hierarchy in statistical physics \cite{WEM19}. Furthermore, our result shows a smooth tradeoff between the signal-to-noise ratio and the computational cost in this problem, thereby confirming a conjecture posed in \cite{KWB22}.
Reviews: A Meta-Learning Perspective on Cold-Start Recommendations for Items
This is an interesting and well-written paper but there are some parts that are not well explained, hence my recommendation. These aspects are not clear: 1. I am not sure about the "meta-learning" part. The recommendation task is simply formulated as a binary classification task (without using matrix factorization). The relation to meta-learning is not convincing to me. 2. "it becomes natural to take advantage of deep neural networks (the common approach in meta-learning)" - this is not a valid claim - deep learning is not the common approach for meta-learning; please see the papers by Brazdil and also the survey by Vilaltra & Drissi.
On the Empirical Complexity of Reasoning and Planning in LLMs
Kang, Liwei, Zhao, Zirui, Hsu, David, Lee, Wee Sun
Chain-of-thought (CoT), tree-of-thought (ToT), and related techniques work surprisingly well in practice for some complex reasoning tasks with Large Language Models (LLMs), but why? This work seeks the underlying reasons by conducting experimental case studies and linking the performance benefits to well-established sample and computational complexity principles in machine learning. We experimented with 6 reasoning tasks, ranging from grade school math, air travel planning, ..., to Blocksworld. The results suggest that (i) both CoT and ToT benefit significantly from task decomposition, which breaks a complex reasoning task into a sequence of steps with low sample complexity and explicitly outlines the reasoning structure, and (ii) for computationally hard reasoning tasks, the more sophisticated tree structure of ToT outperforms the linear structure of CoT. These findings provide useful guidelines for the use of LLM in solving reasoning tasks in practice.
From Summary to Action: Enhancing Large Language Models for Complex Tasks with Open World APIs
Liu, Yulong, Yuan, Yunlong, Wang, Chunwei, Han, Jianhua, Ma, Yongqiang, Zhang, Li, Zheng, Nanning, Xu, Hang
The distinction between humans and animals lies in the unique ability of humans to use and create tools. Tools empower humans to overcome physiological limitations, fostering the creation of magnificent civilizations. Similarly, enabling foundational models like Large Language Models (LLMs) with the capacity to learn external tool usage may serve as a pivotal step toward realizing artificial general intelligence. Previous studies in this field have predominantly pursued two distinct approaches to augment the tool invocation capabilities of LLMs. The first approach emphasizes the construction of relevant datasets for model fine-tuning. The second approach, in contrast, aims to fully exploit the inherent reasoning abilities of LLMs through in-context learning strategies. In this work, we introduce a novel tool invocation pipeline designed to control massive real-world APIs. This pipeline mirrors the human task-solving process, addressing complicated real-life user queries. At each step, we guide LLMs to summarize the achieved results and determine the next course of action. We term this pipeline `from Summary to action', Sum2Act for short. Empirical evaluations of our Sum2Act pipeline on the ToolBench benchmark show significant performance improvements, outperforming established methods like ReAct and DFSDT. This highlights Sum2Act's effectiveness in enhancing LLMs for complex real-world tasks.
DeepProbe: Information Directed Sequence Understanding and Chatbot Design via Recurrent Neural Networks
Yin, Zi, Chang, Keng-hao, Zhang, Ruofei
Information extraction and user intention identification are central topics in modern query understanding and recommendation systems. In this paper, we propose DeepProbe, a generic information-directed interaction framework which is built around an attention-based sequence to sequence (seq2seq) recurrent neural network. DeepProbe can rephrase, evaluate, and even actively ask questions, leveraging the generative ability and likelihood estimation made possible by seq2seq models. DeepProbe makes decisions based on a derived uncertainty (entropy) measure conditioned on user inputs, possibly with multiple rounds of interactions. Three applications, namely a rewritter, a relevance scorer and a chatbot for ad recommendation, were built around DeepProbe, with the first two serving as precursory building blocks for the third. We first use the seq2seq model in DeepProbe to rewrite a user query into one of standard query form, which is submitted to an ordinary recommendation system. Secondly, we evaluate DeepProbe's seq2seq model-based relevance scoring. Finally, we build a chatbot prototype capable of making active user interactions, which can ask questions that maximize information gain, allowing for a more efficient user intention idenfication process. We evaluate first two applications by 1) comparing with baselines by BLEU and AUC, and 2) human judge evaluation. Both demonstrate significant improvements compared with current state-of-the-art systems, proving their values as useful tools on their own, and at the same time laying a good foundation for the ongoing chatbot application.
On Social Envy-Freeness in Multi-Unit Markets
Flammini, Michele (Gran Sasso Science Institute &) | Mauro, Manuel (University of L'Aquila) | Tonelli, Matteo (Gran Sasso Science Institute)
We consider a market setting in which buyers are individuals of a population, whose relationships are represented by an underlying social graph. Given buyers valuations for the items being sold, an outcome consists of a pricing of the objects and an allocation of bundles to the buyers. An outcome is social envy-free if no buyer strictly prefers the bundles of her neighbors in the social graph. We focus on the revenue maximization problem in multi-unit markets, in which there are multiple copies of a same item being sold and each buyer is assigned a set of identical items. We consider the four different cases arising by considering different buyers valuations, i.e., single-minded or general, and by adopting different forms of pricing, that is item- or bundle-pricing. For all the above cases we show the hardness of the revenue maximization problem and give corresponding approximation results. All our approximation bounds are optimal or nearly optimal. Moreover, we provide an optimal allocation algorithm for general valuations with item-pricing, under the assumption of social graphs of bounded treewidth. Finally, we determine optimal bounds on the corresponding price of envy-freeness, that is on the worst case ratio between the maximum revenue that can be achieved without envy-freeness constraints, and the one obtainable in case of social relationships. Some of our results close hardness open questions or improve already known ones in the literature concerning the classical setting without sociality.
26 Inference and Knowledge in Language Comprehension
To use language one must be able to make inferences about the information which language conveys. This is apparent in many ways. For one thing, many of the processes which we typically consider "linguistic" require inference making. For example, structural disambiguation: (1) Waiter, I would like spaghetti with meat sauce and wine. You would not expect to be served a bowl of spaghetti floating in meat sauce and wine. That is, you would expect the meal represented by structure (2) rather than that represented by (3).
Towards the Integration of Programming by Demonstration and Programming by Instruction using Golog
Fritz, Christian (Information Sciences Institute, University of Southern California) | Gil, Yolanda (Information Sciences Institute, University of Southern California)
We present a formal approach for combining programming by demonstration (PbD) with programming by instruction (PbI) — a largely unsolved problem. Our solution is based on the integration of two successful formalisms: version space algebras and the logic programming language Golog. Version space algebras have been successfully applied to programming by demonstration. Intuitively, a version space describes a set of candidate procedures and a learner filters this space as necessary to be consistent with all given demonstrations of the target procedure. Golog, on the other hand, is a logical programming language defined in the situation calculus that allows for the specification of non-deterministic programs. While Golog was originally proposed as a means for integrating programming and automated planning, we show that it serves equally well as a formal framework for integrating PbD and PbI. Our approach is the result of two key insights: (a) Golog programs can be used to define version spaces, and (b) with only a minor augmentation, the existing Golog semantics readily provides the update-function for such version spaces, given demonstrations. Moreover, as we will show, two or more programs can be symbolically synchronized, resulting in the intersection of two, possibly infinite, version spaces. The framework thus allows for a rather flexible integration of PbD and PbI, and in addition establishes a new connection between two active research areas, enabling cross-fertilization.