30 entries matching the current filters. Sorted by recently added.
How much overparameterization lets alternating least squares or gradient descent reliably decompose a third-order tensor?
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…
We describe an open problem: reduce offline nonconvex stochastic optimization to regret minimization in online convex optimization. The conjectured reduction aims to make progress on explaining the success of…
Find a tight, instance-dependent characterization of the number of samples needed to test equality to a known distribution.
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.
We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax…
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…
Can a tensor be decomposed efficiently whenever Kruskal’s condition guarantees its uniqueness?
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…