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}.

We thank all the reviewers for their constructive feedback! Here we provide more experimental results in Figure 1. Hence, gradient descent can get stuck in local optima more easily. R3's observations for collaborative filtering (CF) are valid but they apply

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.

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.

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.

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).