The growing interest in complex decision-making and language modeling problems highlights the importance of sample-efficient learning over very long horizons. This work takes a step in this direction by investigating contextual linear bandits where the current reward depends on at most $s$ prior contexts, up to a time horizon of $h$. In order to avoid polynomial dependence on $h$, we propose new algorithms that leverage sparsity to discover the dependence pattern and arm parameters jointly. We consider both the data-poor ($T<h$) and data-rich  ($T\ge h$) regimes, and derive  respective regret upper bounds $\tilde O(\sqrt{sdT} +\min\{ q, T\})$ and $\tilde O(\sqrt{sdT})$ that are both optimal in $d$ and $T$,  with sparsity $s$, feature dimension $d$,  total time horizon $T$, and $q$ that is adaptive to the reward dependence pattern. 
Complementing upper bounds, we also show that learning over a single trajectory brings inherent challenges: While the dependence pattern and arm parameters form a rank-1 matrix, circulant matrices are not isometric over rank-1 manifolds and sample complexity indeed benefits from the sparse reward structure. Our results necessitate a new analysis to address long-range temporal dependencies across data and avoid polynomial dependence on the reward horizon $h$. Specifically, we utilize connections to the restricted isometry property of circulant matrices formed by dependent sub-Gaussian vectors and establish new guarantees that are also of independent interest.

Stochastic Contextual Bandits with Long Horizon Rewards

We investigate top-m arm identification, a basic problem in bandit theory, in a multi-agent learning model in which agents collaborate to learn an objective function.  We are interested in designing collaborative learning algorithms that achieve maximum speedup (compared to single-agent learning algorithms) using minimum communication cost, as communication is frequently the bottleneck in multi-agent learning.  We give both algorithmic and impossibility results, and conduct a set of experiments to demonstrate the effectiveness of our algorithms. 

Communication-Efficient Collaborative Best Arm Identification

The generalization ability often determines the success of machine learning algorithms in practice. Therefore, it is of great theoretical and practical importance to understand and bound the generalization error of machine learning algorithms. In this paper, we provide the first generalization results of the popular stochastic gradient descent (SGD) algorithm in the distributed asynchronous decentralized setting. Our analysis is based on the uniform stability tool, where stable means that the learned model does not change much in small variations of the training set. Under some mild assumptions, we perform a comprehensive generalizability analysis of the asynchronous decentralized SGD, including generalization error and excess generalization error bounds for the strongly convex, convex, and non-convex cases. Our theoretical results reveal the effects of the learning rate, training data size, training iterations, decentralized communication topology, and asynchronous delay on the generalization performance of the asynchronous decentralized SGD. We also study the optimization error regarding the objective function values and investigate how the initial point affects the excess generalization error. Finally, we conduct extensive experiments on MNIST, CIFAR-10, CIFAR-100, and Tiny-ImageNet datasets to validate the theoretical findings.

Stability-Based Generalization Analysis of the Asynchronous Decentralized SGD

The study of implicit regularization induced by gradient-based optimization in deep learning is a long-standing pursuit. In the present paper, we characterize the implicit regularization of momentum gradient descent (MGD) in the continuous-time view, so-called momentum gradient flow (MGF).   We show that the components of weight vector are learned for a depth-$N$ linear neural network at  the different evolution rates, and this evolution gap increases with the depth $N$. Firstly, we show that if $N=1$, the evolution gap between the weight components is linear, which is consistent with the performance of ridge. In particular, we establish a tight coupling between MGF and ridge which for least squares regression. In details, we prove that, under the calibration $t=\sqrt{2/\lambda}$, where $t$ is the time  parameter in MGF and $\lambda$ is the tuning parameter in ridge, the risk of MGF is no more than 1.54 times that of ridge and their relative Bayesian risk is hardly different. Secondly,  if the model becomes deeper, i.e. $N\geq2$, the evolution gap becomes more significant, which implies an implicit bias towards sparse solutions. The numerical experiments strongly support our theoretical results.

The Implicit Regularization of Momentum Gradient Descent in Overparametrized Models

Seed plants vary tremendously in size and morphology. However, variation and covariation between plant traits may at least in part be governed by universal biophysical laws and biological constants. Metabolic Scaling Theory (MST) posits that whole-organismal metabolism and growth rate are under stabilizing selection that minimizes the scaling of hydrodynamic resistance and maximizes the scaling of resource uptake. This constrains variation in physiological traits and in the rate of biomass accumulation, so that they can be expressed as mathematical functions of plant size with near constant allometric scaling exponents across species. However, observed variation in allometric exponents questions the evolutionary drivers and the universality of scaling exponents. We have measured growth scaling and fitness traits of 451 Arabidopsis thaliana accessions with sequenced genomes. Variation among accessions around the scaling exponent predicted by MST correlated with climate, seed production and stress resistance. Genomic analyses indicate that growth allometry is affected by many genes associated with local climate and abiotic stress response. The gene with the strongest effect, PUB4, has molecular signatures of balancing selection, suggesting that intraspecific variation in growth scaling is maintained by opposing selection on two major components of fitness, seed production and abiotic stress resistance. Our findings support one of the core MST predictions and suggest that allometry contributes to local adaptation to contrasting environments. Our results help reconcile past debates on the origin of allometric scaling in biology, and begin to link adaptive variation in allometric scaling to specific genes.

Adaptive diversification of metabolic scaling in the plant Arabidopsis thaliana

Monitoring plant growth with computer vision is an important topic in plant science. This monitoring can be challenging when plants are located in outdoor conditions due to light variations and other noises. On other hand, there is a lack of annotated datasets available for such outdoor environments to train machine learning algorithms while indoor similar datasets may be more easily available. In this communication, we investigate, for the first time to the best of our knowledge in plant imaging, how to take benefit from model trained in fully controlled environment to build model for an outdoor environment. This is illustrated with the prediction of seedling development from top view RGB images.  

Underline digital video library

Stochastic Contextual Bandits with Long Horizon Rewards

Communication-Efficient Collaborative Best Arm Identification

Stability-Based Generalization Analysis of the Asynchronous Decentralized SGD

The Implicit Regularization of Momentum Gradient Descent in Overparametrized Models

Adaptive diversification of metabolic scaling in the plant Arabidopsis thaliana

Deep learning-based detection of seedling development from indoor to outdoor

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES