Daily TMLR digest for Jun 19, 2023
TMLR
Accepted papers
===============
Title: Predicting Out-of-Domain Generalization with Neighborhood Invariance
Authors: Nathan Hoyen Ng, Neha Hulkund, Kyunghyun Cho, Marzyeh Ghassemi
Abstract: Developing and deploying machine learning models safely depends on the ability to char- acterize and compare their abilities to generalize to new environments. Although recent work has proposed a variety of methods that can directly predict or theoretically bound the generalization capacity of a model, they rely on strong assumptions such as matching train/test distributions and access to model gradients. In order to characterize generalization when these assumptions are not satisfied, we propose neighborhood invariance, a measure of a classifier’s output invariance in a local transformation neighborhood. Specifically, we sample a set of transformations and given an input test point, calculate the invariance as the largest fraction of transformed points classified into the same class. Crucially, our measure is simple to calculate, does not depend on the test point’s true label, makes no assumptions about the data distribution or model, and can be applied even in out-of-domain (OOD) settings where existing methods cannot, requiring only selecting a set of appropriate data transformations. In experiments on robustness benchmarks in image classification, sentiment analysis, and natural language inference, we demonstrate a strong and robust correlation between our neighborhood invariance measure and actual OOD generalization on over 4,600 models evaluated on over 100 train/test domain pairs.
URL: https://openreview.net/forum?id=jYkWdJzTwn
---
New submissions
===============
Title: Finterp: Cost-Time Analysis of Video Action Recognition using the Black Scholes Model
Abstract: We present a novel method to analyze the earliest instant of time at which a pretrained video action recognition neural network is capable of predicting the action class, with high confidence. We exploit the fact that this problem bears similarities with pricing options in a European stock market, consequentially, our approach, Finterp, is inspired by the Black Scholes model in finance. We formulate analogies between the conceptualization of the variables involved in the Black Scholes formula and video frames to derive the appropriate algorithm. We use Finterp to extensively analyze the prediction capabilities of the neural network over time, on multiple diverse datasets. Finterp reveals that optimal frames are concentrated at low instants of time for datasets with scene bias and mid instants of time for datasets with motion bias. We demonstrate that Finterp does not compromise on the confidence of action prediction in an attempt to minimize the length of video observed. The 'Black Scholes Accuracy' for state-of-the-art 3D CNNs such as I3D and X3D stands at $81-86\%$, $64\%$ and $25\%$ for Kinetics, UAV Human and Diving-48 respectively, revealing the need to develop neural networks that can learn unique temporal signatures for various actions. Finally, we extend Finterp to make optimal time instant predictions at the hierarchical level, where similar action classes are grouped together, and show that the optimal time instant predictions are at earlier time instants than the corresponding predictions without hierarchy. We will make all code publicly available.
URL: https://openreview.net/forum?id=crab4LLZj0
---
Title: Population-based Evaluation in Repeated Rock-Paper-Scissors as a Benchmark for Multiagent Reinforcement Learning
Abstract: Progress in fields of machine learning and adversarial planning has benefited significantly from benchmark domains, from checkers and the classic UCI data sets to Go and Diplomacy. In sequential decision-making, agent evaluation has largely been restricted to few interactions against experts, with the aim to reach some desired level of performance (e.g. beating a human professional player). We propose a benchmark for multiagent learning based on repeated play of the simple game Rock, Paper, Scissors along with a population of forty-three tournament entries, some of which are intentionally sub-optimal. We describe metrics to measure the quality of agents based both on average returns and exploitability. We then show that several RL, online learning, and language model approaches can learn good counter-strategies and generalize well, but ultimately lose to the top-performing bots, creating an opportunity for research in multiagent learning.
URL: https://openreview.net/forum?id=gQnJ7ODIAx
---
Title: Benefits of Max Pooling in Neural Networks: Theoretical and Experimental Evidence
Abstract: When deep neural networks became state of the art image classifiers, numerous max pooling operations were an important component of the architecture. However, modern computer vision networks typically have few if any max pooling operations. To understand
whether this trend is justified, we develop a mathematical framework
analyzing ReLU based approximations of max pooling, and prove a sense
in which max pooling cannot be replicated. We formulate and analyze a class of optimal
approximations, and find that residual can be made exponentially small in
the kernel size, but only with an exponentially wide approximation.
This work gives a theoretical basis for understanding the reduced use of
max pooling in newer architectures. Since max pooling does not seem necessary,
we conclude that empirically the inputs on which max pooling is distinct --
those with a large difference between the max and other values --is not
a pattern prevalent in natural images.
URL: https://openreview.net/forum?id=YgeXqrH7gA
---
Title: SkillS: Adaptive Skill Sequencing for Efficient Temporally-Extended Exploration
Abstract: The ability to effectively reuse prior knowledge is a key requirement when building general and flexible Reinforcement Learning (RL) agents. Skill reuse is one of the most common approaches, but current methods have considerable limitations. For example, fine-tuning an existing policy frequently fails, as the policy can degrade rapidly early in training. In a similar vein, distillation of expert behavior can lead to poor results when given sub-optimal experts. We compare several common approaches for skill transfer on multiple domains including changes in task and system dynamics. We identify how existing methods fail and introduce an alternative approach to mitigate these problems. Our approach learns to sequence temporally-extended skills for exploration but learns the final policy directly from the raw experience. This conceptual split enables rapid adaptation and thus efficient data collection but without constraining the final solution. It significantly outperforms many classical methods across a suite of evaluation tasks and we use a broad set of ablations to highlight the importance of different components of our method.
URL: https://openreview.net/forum?id=JwGKVpRfVD
---
Title: Fast Kernel Methods for Generic Lipschitz Losses via $p$-Sparsified Sketches
Abstract: Kernel methods are learning algorithms that enjoy solid theoretical foundations while suffering from important computational limitations. Sketching, which consists in looking for solutions among a subspace of reduced dimension, is a well-studied approach to alleviate these computational burdens. However, statistically-accurate sketches, such as the Gaussian one, usually contain few null entries, such that their application to kernel methods and their non-sparse Gram matrices remains slow in practice. In this paper, we show that sparsified Gaussian (and Rademacher) sketches still produce theoretically-valid approximations while allowing for important time and space savings thanks to an efficient \emph{decomposition trick}. To support our method, we derive excess risk bounds for both single and multiple output kernel problems, with generic Lipschitz losses, hereby providing new guarantees for a wide range of applications, from robust regression to multiple quantile regression. Our theoretical results are complemented with experiments showing the empirical superiority of our approach over state-of-the-art sketching methods.
URL: https://openreview.net/forum?id=ry2qgRqTOw
---
Title: Finetuning from Offline Reinforcement Learning: Challenges, Trade-offs and Practical Solutions
Abstract: Offline reinforcement learning (RL) allows for the training of competent agents from offline datasets without any interaction with the environment. Online finetuning of such offline models can further improve performance. But how should we ideally finetune agents obtained from offline RL training? While offline RL algorithms can in principle be used for finetuning, in practice, their online performance improves slowly. In contrast, we show that it is possible to use standard online off-policy algorithms for faster improvement. However, we find this approach may suffer from policy collapse, where the policy undergoes severe performance deterioration during initial online learning. We investigate the issue of policy collapse and how it relates to data diversity, algorithm choices and online replay distribution. Based on these insights, we propose a conservative policy optimization procedure that can achieve stable and sample-efficient online learning from offline pretraining.
URL: https://openreview.net/forum?id=PffrUvAOGy
---
Title: \texttt{FedBC}: Federated Learning Beyond Consensus
Abstract: Federated learning (FL) algorithms, such as FedAvg/FedProx, commonly rely on the consensus constraint, enforcing local models to be equal to the global model obtained through the averaging of local updates. However, in practical FL settings with heterogeneous agents, we question the necessity of enforcing consensus. We empirically observe that relaxing consensus constraint an improve both local and global performance to a certain extent. To mathematically formulate it, we replace the consensus constraint in standard FL objective with the proximity between the local and the global model controlled by a tolerance parameter $\gamma$, and propose a novel Federated Learning Beyond Consensus (\texttt{FedBC}) algorithm to solve it.
Theoretically, we establish that \texttt{FedBC} converges to a first-order stationary point at rates that matches the state of the art, up to an additional error term that depends on a tolerance parameter $\gamma$.
Finally, we demonstrate that \texttt{FedBC} balances the global and local model test accuracy metrics across a suite of datasets (Synthetic, MNIST, CIFAR-10, Shakespeare), achieving competitive performance with state-of-the-art.
URL: https://openreview.net/forum?id=FCgSHlFnYT
---
Title: A simple, efficient and scalable contrastive masked autoencoder for learning visual representations
Abstract: Hybrid self-supervised learning methods that combine masked image modelling and contrastive learning have demonstrated state-of-the-art performance across many vision tasks. In this work we identify a property overlooked by previous hybrid methods: they can achieve considerable efficiency improvements compared to contrastive learning, whilst still outperforming the constituent contrastive and masked image modelling training components. To demonstrate this, we introduce CAN a minimal and conceptually clean synthesis of (C) contrastive learning, (A) masked autoencoders, and (N) the noise prediction approach used in diffusion models. CAN is designed to be efficient, masking 50\% of patches in \emph{both} views, meaning that the overall FLOPs load of SimCLR is 70\% higher than CAN for ViT-L backbones. Our combined approach outperforms its MAE and SimCLR constituent parts on an extensive set of downstream transfer learning and robustness tasks under both linear probe and finetune protocols, and pre-training on large scale datasets such as JFT-300M and ImageNet-21K. Code is provided in the supplementary material, and will be publicly released.
URL: https://openreview.net/forum?id=pjdxPts6er
---
Title: A Robust Backpropagation-Free Framework for Images
Abstract: While current deep learning algorithms have been successful for a wide variety of artificial intelligence (AI) tasks, including those involving structured image data, they present deep neurophysiological conceptual issues due to their reliance on the gradients, computed by backpropagation of errors (backprop). Gradients are required to obtain synaptic weight adjustments but require knowledge of feed-forward activities for the backward propagation. But because there is no known biological way for an error (backward) network to be precisely aware of the weights of the original (forward) network, many current deep learning algorithms are majorly biologically implausible. This is known as the “weight transport problem”. We present a more biologically plausible approach towards solving the weight transport problem for structured image data, by introducing the error-kernel driven activation alignment (EKDAA) algorithm, to train convolutional neural networks (CNNs) using locally derived error transmission kernels and error maps. Like standard deep learning networks, EKDAA performs the standard forward process via weights and activation functions, but its backward error computation involves learning error kernels to propagate local error signals through the network. We demonstrate the efficacy of EKDAA by performing the task of visual-recognition on the Fashion MNIST, CIFAR-10 and SVHN benchmarks, along with demonstrating its ability to extract visual features from natural color images. Furthermore, we present results for a CNN trained using a non-differentiable activation function.
URL: https://openreview.net/forum?id=leqr0vQzeN
---