30 entries matching the current filters. Sorted by recently added.
How many samples are needed to find a Nash equilibrium in a zero-sum matrix game, as a function of the particular instance?
How much can carefully choosing a small training set improve regression? Determine sharp loss ratios under a fixed data budget.
Reinforcement Learning (RL) has shown great empirical success in various application domains. The theoretical aspects of the problem have been extensively studied over past decades, particularly under tabular and…
Contextual bandits serve as a theoretical framework to design recommender systems, which often rely on user-sensitive data, making privacy a critical concern. However, a significant gap remains between the known…
Sparse linear problems can be learned well with online multiplicative updates. The question is whether there are closed-form updates based on the past examples that can sample efficiently learn such sparse linear…
Both asymptotic and non-asymptotic instance-dependent regret bounds are known for the stochastic multi-armed bandit problem. Such regret bounds are known to be tight up to lower order terms in the setting of…
The design of efficient differentially private (DP) learning algorithms with dimension-independent learning guarantees has been one of the central challenges in the field of privacy-preserving machine learning.…
Confidence intervals are a crucial building block in the analysis of various online learning problems. The analysis of kernel-based bandit and reinforcement learning problems utilize confidence intervals applicable…
Characterize how conditional mutual information controls generalization and the information complexity of learning.
Folklore results in the theory of Stochastic Approximation indicates the (minimax) optimality of Stochastic Gradient Descent (SGD) (Robbins and Monro, 1951) with polynomially decaying step sizes and iterate…
We ask whether there exists an efficient unsupervised learning algorithm for mixture of Gaussians in the over-complete case (number of mixtures is larger than the dimension). The notion of learning is taken to be…
The best arm identification problem (BEST-1-ARM) is the most basic pure exploration problem in stochastic multi-armed bandits. The problem has a long history and attracted significant attention for the last decade.…
The Recursive Teaching Dimension (RTD) of a concept class C is a complexity parameter referring to the worst-case number of labelled examples needed to learn any target concept in C from a teacher following the…
We pose an open problem on the complexity of learning the behavior of a quantum circuit with value injection queries. We define the learning model for quantum circuits and give preliminary results. Using the…
We consider the long-open problem of attribute-efficient learning of halfspaces. In this problem the learner is given random examples labeled by an unknown halfspace function f on R^n. Further f is r-sparse, that…
In this paper we consider the problem of learning a graph generating process given the evolving graph at a single point in time. Given a graph of sufficient size, can we learn the (repeatable) process that…
Can bandit allocation rules achieve optimal regret while remaining ex-post monotone, as required for truthful mechanisms?
To what extent is learnability impeded when information is missing in learning instances? We present relevant known results and concrete open problems, in the context of a natural extension of the PAC learning…
It is unknown what is the most suitable regularization for rotation matrices and how to maintain uncertainty over rotations in an online setting. We propose to address these questions by studying the minimax…
In sequential prediction with log-loss as well as density estimation with risk measured by KL divergence, one is often interested in the expected instantaneous loss, or, equivalently, the individual risk at a given…
Find an efficient conditional-probability estimator that remains robust when its model assumptions are violated.
Ant robots can repeatedly and robustly cover terrain by always moving away from the trails that they leave in the terrain. This coverage strategy can be modeled with graph traversal strategies similar to real-time…
Can large-margin halfspaces be learned efficiently by an improper learner under the stated distributional assumptions?
Find stronger approximation guarantees for sparsest-cut clustering by exploiting the structure of the underlying data.
Can minimax strategies for repeated games be learned efficiently when players only observe bandit feedback?