Related papers: A Combinatorial Characterization of Supervised Online Learnability

A Combinatorial Characterization of Supervised Online Learnability

URL: http://arxiv.org/abs/2307.03816v2
Date: Fri, 9 Feb 2024 18:27:51 GMT
Title: A Combinatorial Characterization of Supervised Online Learnability
Authors: Vinod Raman, Unique Subedi, Ambuj Tewari
Abstract summary: We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. We give a new scale-sensitive dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability.
Score: 20.291598040396302
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No characterization of online learnability is known at this level of generality. We give a new scale-sensitive combinatorial dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability. In addition, we show that the sequential minimax dimension subsumes most existing combinatorial dimensions in online learning theory.

Related papers

Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
We aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. We first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. In the context of online learning we provide a dimension that characterizes the minimax optimal instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression.
arXiv Detail & Related papers (2023-07-07T21:39:25Z)
Online Learning with Set-Valued Feedback [18.054632903107546]
We study a variant of online multiclass classification where the learner predicts a single label but receives a textitset of labels as feedback. We show that unlike online multiclass learning with single-label feedback, deterministic and randomized online learnability are textitnot equivalent even in the realizable setting.
arXiv Detail & Related papers (2023-06-09T20:43:19Z)
Multiclass Online Learning and Uniform Convergence [34.21248304961989]
We study multiclass classification in the adversarial online learning setting. We prove that any multiclass concept class is agnostically learnable if and only if its Littlestone dimension is finite.
arXiv Detail & Related papers (2023-03-30T21:35:48Z)
Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient [65.08966446962845]
offline reinforcement learning, which aims at optimizing decision-making strategies with historical data, has been extensively applied in real-life applications. We take a step by considering offline reinforcement learning with differentiable function class approximation (DFA) Most importantly, we show offline differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning algorithm.
arXiv Detail & Related papers (2022-10-03T07:59:42Z)
Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
arXiv Detail & Related papers (2022-06-01T23:26:51Z)
Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism [65.46524775457928]
offline reinforcement learning seeks to utilize offline/historical data to optimize sequential decision-making strategies. We study the statistical limits of offline reinforcement learning with linear model representations.
arXiv Detail & Related papers (2022-03-11T09:00:12Z)
Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
arXiv Detail & Related papers (2020-08-19T04:53:31Z)
Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory [110.99247009159726]
Temporal-difference and Q-learning play a key role in deep reinforcement learning, where they are empowered by expressive nonlinear function approximators such as neural networks. In particular, temporal-difference learning converges when the function approximator is linear in a feature representation, which is fixed throughout learning, and possibly diverges otherwise.
arXiv Detail & Related papers (2020-06-08T17:25:22Z)
On the Equivalence between Online and Private Learnability beyond Binary Classification [26.400891660337777]
We show that private learnability implies online learnability in both settings. We show that while online learnability continues to imply private learnability in multi-class classification, current proof techniques encounter significant hurdles in the regression setting.
arXiv Detail & Related papers (2020-06-02T23:30:41Z)
Towards a combinatorial characterization of bounded memory learning [21.031088723668486]
We develop dimensions that characterize bounded memory learning. We prove both upper and lower bounds for our candidate solution. We conjecture that our characterization holds in a much wider regime of parameters.
arXiv Detail & Related papers (2020-02-08T09:04:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.