Search

A frame $(x_j)_{j\in J}$ for a Hilbert space $H$ allows for a linear and stable reconstruction of any vector $x\in H$ from the linear measurements $(\langle x,x_j\rangle)_{j\in J}$. However, there are many situations where some information in the frame coefficients is lost. In applications where one is using sensors with a fixed dynamic range, any measurement above that range is registered as the maximum, and any measurement below that range is registered as the minimum. Depending on the context, recovering a vector from such measurements is called either declipping or saturation recovery. We initiate a frame theoretic approach to saturation recovery in a similar way to what [BCE06] did for phase retrieval. We characterize when saturation recovery is possible, show optimal frames for use with saturation recovery correspond to minimal multi-fold packings in projective space, and prove that the classical frame algorithm may be adapted to this non-linear problem to provide a reconstruction algorithm., Comment: 20 pages

Quantum sensors offer unparalleled precision, accuracy, and sensitivity for a variety of measurement applications. We report a compact magnetometer based on a ferrimagnetic sensing element in an oscillator architecture that circumvents challenges common to other quantum sensing approaches such as limited dynamic range, limited bandwidth, and dependence on vacuum, cryogenic, or laser components. The device exhibits a fixed, calibration-free response governed by the electron gyromagnetic ratio. Exchange narrowing in the ferrimagnetic material produces sub-MHz transition linewidths despite the high unpaired spin density ($\sim 10^{22}$ cm$^{-3}$). The magnetometer achieves a minimum sensitivity of 100 fT/$\sqrt{\text{Hz}}$ to AC magnetic fields of unknown phase and a sensitivity below 200 fT/$\sqrt{\text{Hz}}$ over a bandwidth $\gtrsim \! 1$ MHz. By encoding magnetic field in frequency rather than amplitude, the device provides a dynamic range in excess of 1 mT. The passive, thermal initialization of the sensor's quantum state requires only a magnetic bias field, greatly reducing power requirements compared to laser-initialized quantum sensors. With additional development, this device promises to be a leading candidate for high-performance magnetometry outside the laboratory, and the oscillator architecture is expected to provide advantages across a wide range of sensing platforms., Comment: 18 pages, 4 figures

Animals have evolved various agile locomotion strategies, such as sprinting, leaping, and jumping. There is a growing interest in developing legged robots that move like their biological counterparts and show various agile skills to navigate complex environments quickly. Despite the interest, the field lacks systematic benchmarks to measure the performance of control policies and hardware in agility. We introduce the Barkour benchmark, an obstacle course to quantify agility for legged robots. Inspired by dog agility competitions, it consists of diverse obstacles and a time based scoring mechanism. This encourages researchers to develop controllers that not only move fast, but do so in a controllable and versatile way. To set strong baselines, we present two methods for tackling the benchmark. In the first approach, we train specialist locomotion skills using on-policy reinforcement learning methods and combine them with a high-level navigation controller. In the second approach, we distill the specialist skills into a Transformer-based generalist locomotion policy, named Locomotion-Transformer, that can handle various terrains and adjust the robot's gait based on the perceived environment and robot states. Using a custom-built quadruped robot, we demonstrate that our method can complete the course at half the speed of a dog. We hope that our work represents a step towards creating controllers that enable robots to reach animal-level agility., Comment: 17 pages, 19 figures

A frame $(x_j)_{j\in J}$ for a Hilbert space $H$ is said to do phase retrieval if for all distinct vectors $x,y\in H$ the magnitude of the frame coefficients $(|\langle x, x_j\rangle|)_{j\in J}$ and $(|\langle y, x_j\rangle|)_{j\in J}$ distinguish $x$ from $y$ (up to a unimodular scalar). A frame which does phase retrieval is said to do $C$-stable phase retrieval if the recovery of any vector $x\in H$ from the magnitude of the frame coefficients is $C$-Lipschitz. It is known that if a frame does stable phase retrieval then any sufficiently small perturbation of the frame vectors will do stable phase retrieval, though with a slightly worse stability constant. We provide new quantitative bounds on how the stability constant for phase retrieval is affected by a small perturbation of the frame vectors. These bounds are significant in that they are independent of the dimension of the Hilbert space and the number of vectors in the frame., Comment: 14 pages

We formulate a quantitative finite-dimensional conjecture about frame multipliers and prove that it is equivalent to Conjecture 1 in [SB2]. We then present solutions to the conjecture for certain classes of frame multipliers. In particular, we prove that there is a universal constant $\kappa>0$ so that for all $C,\beta>0$ and $N\in\mathbb{N}$ the following is true. Let $(x_j)_{j=1}^N$ and $(f_j)_{j=1}^N$ be sequences in a finite dimensional Hilbert space which satisfy $\|x_j\|=\|f_j\|$ for all $1\leq j\leq N$ and $$\Big\|\sum_{j=1}^N \varepsilon_j\langle x,f_j\rangle x_j\Big\|\leq C\|x\|, \qquad\textrm{ for all $x\in \ell_2^M$ and $|\varepsilon_j|=1$}. $$ If the frame operator for $(f_j)_{j=1}^N$ has eigenvalues $\lambda_1\geq...\geq\lambda_M$ and $\lambda_1\leq \beta M^{-1}\sum_{j=1}^M\lambda_j$ then $(f_j)_{j=1}^N$ has Bessel bound $\kappa \beta^2 C$. The same holds for $(x_j)_{j=1}^N$., Comment: 19 pages

A frame $(x_j)_{j\in J}$ for a Hilbert space $H$ is said to do phase retrieval if for all distinct vectors $x,y\in H$ the magnitude of the frame coefficients $(|\langle x, x_j\rangle|)_{j\in J}$ and $(|\langle y, x_j\rangle|)_{j\in J}$ distinguish $x$ from $y$ (up to a unimodular scalar). We consider the weaker condition where the magnitude of the frame coefficients distinguishes $x$ from every vector $y$ in a small neighborhood of $x$ (up to a unimodular scalar). We prove that some of the important theorems for phase retrieval hold for this local condition, where as some theorems are completely different. We prove as well that when considering stability of phase retrieval, the worst stability inequality is always witnessed at orthogonal vectors. This allows for much simpler calculations when considering optimization problems for phase retrieval., Comment: Added some additional comments and references

Language models demonstrate both quantitative improvement and new qualitative capabilities with increasing scale. Despite their potentially transformative impact, these new capabilities are as yet poorly characterized. In order to inform future research, prepare for disruptive new model capabilities, and ameliorate socially harmful effects, it is vital that we understand the present and near-future capabilities and limitations of language models. To address this challenge, we introduce the Beyond the Imitation Game benchmark (BIG-bench). BIG-bench currently consists of 204 tasks, contributed by 450 authors across 132 institutions. Task topics are diverse, drawing problems from linguistics, childhood development, math, common-sense reasoning, biology, physics, social bias, software development, and beyond. BIG-bench focuses on tasks that are believed to be beyond the capabilities of current language models. We evaluate the behavior of OpenAI's GPT models, Google-internal dense transformer architectures, and Switch-style sparse transformers on BIG-bench, across model sizes spanning millions to hundreds of billions of parameters. In addition, a team of human expert raters performed all tasks in order to provide a strong baseline. Findings include: model performance and calibration both improve with scale, but are poor in absolute terms (and when compared with rater performance); performance is remarkably similar across model classes, though with benefits from sparsity; tasks that improve gradually and predictably commonly involve a large knowledge or memorization component, whereas tasks that exhibit "breakthrough" behavior at a critical scale often involve multiple steps or components, or brittle metrics; social bias typically increases with scale in settings with ambiguous context, but this can be improved with prompting., Comment: 27 pages, 17 figures + references and appendices, repo: https://github.com/google/BIG-bench

A longstanding goal of the field of AI is a method for learning a highly capable, generalist agent from diverse experience. In the subfields of vision and language, this was largely achieved by scaling up transformer-based models and training them on large, diverse datasets. Motivated by this progress, we investigate whether the same strategy can be used to produce generalist reinforcement learning agents. Specifically, we show that a single transformer-based model - with a single set of weights - trained purely offline can play a suite of up to 46 Atari games simultaneously at close-to-human performance. When trained and evaluated appropriately, we find that the same trends observed in language and vision hold, including scaling of performance with model size and rapid adaptation to new games via fine-tuning. We compare several approaches in this multi-game setting, such as online and offline RL methods and behavioral cloning, and find that our Multi-Game Decision Transformer models offer the best scalability and performance. We release the pre-trained models and code to encourage further research in this direction., Comment: NeurIPS 2022. 24 pages, 16 figures. Additional information, videos and code can be seen at https://sites.google.com/view/multi-game-transformers

For a Banach space $X$ with a shrinking Schauder frame $(x_i,f_i)$ we provide an explicit method for constructing a shrinking associated basis. In the case that the minimal associated basis is not shrinking, we prove that every shrinking associated basis of $(x_i,f_i)$ dominates an uncountable family of incomparable shrinking associated bases of $(x_i,f_i)$. By adapting a construction of Pe{\l}czy{\'n}ski, we characterize spaces with shrinking Schauder frames as spaces having the $w^*$-bounded approximation property., Comment: comments welcome

Assembly of multi-part physical structures is both a valuable end product for autonomous robotics, as well as a valuable diagnostic task for open-ended training of embodied intelligent agents. We introduce a naturalistic physics-based environment with a set of connectable magnet blocks inspired by children's toy kits. The objective is to assemble blocks into a succession of target blueprints. Despite the simplicity of this objective, the compositional nature of building diverse blueprints from a set of blocks leads to an explosion of complexity in structures that agents encounter. Furthermore, assembly stresses agents' multi-step planning, physical reasoning, and bimanual coordination. We find that the combination of large-scale reinforcement learning and graph-based policies -- surprisingly without any additional complexity -- is an effective recipe for training agents that not only generalize to complex unseen blueprints in a zero-shot manner, but even operate in a reset-free setting without being trained to do so. Through extensive experiments, we highlight the importance of large-scale training, structured representations, contributions of multi-task vs. single-task learning, as well as the effects of curriculums, and discuss qualitative behaviors of trained agents., Comment: Accompanying project webpage can be found at: https://sites.google.com/view/learning-direct-assembly

Most successes in robotic manipulation have been restricted to single-arm robots, which limits the range of solvable tasks to pick-and-place, insertion, and objects rearrangement. In contrast, dual and multi arm robot platforms unlock a rich diversity of problems that can be tackled, such as laundry folding and executing cooking skills. However, developing controllers for multi-arm robots is complexified by a number of unique challenges, such as the need for coordinated bimanual behaviors, and collision avoidance amongst robots. Given these challenges, in this work we study how to solve bi-manual tasks using reinforcement learning (RL) trained in simulation, such that the resulting policies can be executed on real robotic platforms. Our RL approach results in significant simplifications due to using real-time (4Hz) joint-space control and directly passing unfiltered observations to neural networks policies. We also extensively discuss modifications to our simulated environment which lead to effective training of RL policies. In addition to designing control algorithms, a key challenge is how to design fair evaluation tasks for bi-manual robots that stress bimanual coordination, while removing orthogonal complicating factors such as high-level perception. In this work, we design a Connect Task, where the aim is for two robot arms to pick up and attach two blocks with magnetic connection points. We validate our approach with two xArm6 robots and 3D printed blocks with magnetic attachments, and find that our system has 100% success rate at picking up blocks, and 65% success rate at the Connect Task., Comment: Our accompanying project webpage can be found at: https://sites.google.com/view/bimanual-attachment

Phase retrieval is known to always be unstable when using a frame or continuous frame for an infinite dimensional Hilbert space. We consider a generalization of phase retrieval to the setting of subspaces of $L_2$ which coincides with using a continuous frame for phase retrieval when the subspace is the range of the analysis operator of a continuous frame. We then prove that there do exist infinite dimensional subspaces of $L_2$ where phase retrieval is stable. That is, we give a method for constructing an infinite dimensional subspace $Y\subseteq L_2$ such that there exists $C\geq 1$ so that $$\min\big(\big\|f-g\big\|_{L_2},\big\|f+g\big\|_{L_2}\big)\leq C \big\| |f|-|g| \big\|_{L_2} \qquad\textrm{ for all }f,g\in Y. $$ This construction also leads to new results on uniform stability of phase retrieval in finite dimensions. Our construction has a deterministic component and a random component. When using sub-Gaussian random variables we achieve phase retrieval with high probability and stability constant independent of the dimension $n$ when using $m$ on the order of $n$ random vectors. Without sub-Gaussian or any other higher moment assumptions, we are able to achieve phase retrieval with high probability and stability constant independent of the dimension $n$ when using $m$ on the order of $n\log(n)$ random vectors., Comment: 27 pages

The goal of continuous control is to synthesize desired behaviors. In reinforcement learning (RL)-driven approaches, this is often accomplished through careful task reward engineering for efficient exploration and running an off-the-shelf RL algorithm. While reward maximization is at the core of RL, reward engineering is not the only -- sometimes nor the easiest -- way for specifying complex behaviors. In this paper, we introduce \braxlines, a toolkit for fast and interactive RL-driven behavior generation beyond simple reward maximization that includes Composer, a programmatic API for generating continuous control environments, and set of stable and well-tested baselines for two families of algorithms -- mutual information maximization (MiMax) and divergence minimization (DMin) -- supporting unsupervised skill learning and distribution sketching as other modes of behavior specification. In addition, we discuss how to standardize metrics for evaluating these algorithms, which can no longer rely on simple reward maximization. Our implementations build on a hardware-accelerated Brax simulator in Jax with minimal modifications, enabling behavior synthesis within minutes of training. We hope Braxlines can serve as an interactive toolkit for rapid creation and testing of environments and behaviors, empowering explosions of future benchmark designs and new modes of RL-driven behavior generation and their algorithmic research.

Given an $N$-dimensional subspace $X$ of $L_p([0,1])$, we consider the problem of choosing $M$-sampling points which may be used to discretely approximate the $L_p$ norm on the subspace. We are particularly interested in knowing when the number of sampling points $M$ can be chosen on the order of the dimension $N$. For the case $p=2$ it is known that $M$ may always be chosen on the order of $N$ as long as the subspace $X$ satisfies a natural $L_\infty$ bound, and for the case $p=\infty$ there are examples where $M$ may not be chosen on the order of $N$. We show for all $1\leq p<2$ that there exist classes of subspaces of $L_p([0,1])$ which satisfy the $L_\infty$ bound, but where the number of sampling points $M$ cannot be chosen on the order of $N$. We show as well that the problem of discretizing the $L_p$ norm of subspaces is directly connected with frame theory. In particular, we prove that discretizing a continuous frame to obtain a discrete frame which does stable phase retrieval requires discretizing both the $L_2$ norm and the $L_1$ norm on the range of the analysis operator of the continuous frame., Comment: 17 pages, version 2