Study extends learnability equivalence to multi-class and regression, overcoming binary classification limits.
problem Equivalence of online and private learnability in multi-class and regression settings.
method Introduced a novel Littlestone dimension variant and threshold functions for multi-class classification.
result Online learnability implies private learnability in multi-class classification but not in regression.
New learnability criteria for non-iid processes equivalent to online learning.
problem Statistical learning under non-iid stochastic processes is underdeveloped.
method Defined two learnability notions and showed their equivalence to online learning.
result Learnability criteria for non-iid processes are equivalent to online learning.
Characterizes learnability of multioutput functions in various settings.
problem Learning multioutput function classes in batch and online settings.
method Characterizes learnability based on single-output restrictions.
result Complete characterization of learnability in multioutput classification and regression.
Online learning of linear operators between infinite-dimensional spaces is possible but with limitations.
problem Learning linear operators between infinite-dimensional Hilbert spaces in an online setting.
method Online learning approach for linear operators with bounded p p p -Schatten norm, proving impossibility for operator norm. result Separation between online learnability and uniform convergence for bounded linear operators.
Study online multiclass classification under bandit feedback, extending previous results.
problem Online multiclass classification with bandit feedback, focusing on label space unboundedness.
method Extend Daniely and Helbertal's results, show necessity and sufficiency of Bandit Littlestone dimension for learnability.
result Sequential uniform convergence is necessary but not sufficient for bandit online learnability.
Stability is a general notion that quantifies the sensitivity of a learning algorithm's output to small change in the training dataset (e.g. deletion or replacement of a single training sample). Such conditions have recently been shown to be more powerful to characterize learnability in the general learning setting und…
This work proves DP learnability implies online learnability for general classification tasks.
problem Link between differential privacy and online learning for general classification tasks.
method Establishes Ramsey-type theorems for trees to prove DP learnability implies online learnability.
result DP learnability implies online learnability for general classification tasks.
Characterizes concept classes for optimistic online learning.
problem Understanding minimal assumptions for online learnability.
method Investigates two questions about concept classes' learnability.
result Characterizes all concept classes for optimistically universal online learnability.
Study online learning with set-valued feedback, showing differences between deterministic and randomized approaches.
problem Online learning with set-valued feedback, where labels are sets rather than single labels.
method Introduced new combinatorial dimensions (Set Littlestone and Measure Shattering) to characterize learnability.
result Characterized deterministic and randomized online learnability, and established bounds for various learning settings.
Private classification and online prediction are shown to be equivalent.
problem Learning with differential privacy and online prediction equivalence.
method Introducing global stability and proving equivalence between online learnability and private PAC learnability.
result Every concept class with finite Littlestone dimension can be learned by a differentially-private algorithm.
New algorithm learns regression models privately under growth condition.
problem Private learning of nonparametric regression models.
method Novel filtering procedure to output stable hypotheses for nonparametric function classes.
result Established first nonparametric private learnability guarantee for diverging fat shattering dimensions.
Study improves online learning with adaptable agents in various settings.
problem Learning with improving agents in online settings.
method Extensive analysis of combinatorial dimensions, multiclass setup, bandit feedback, and agent cost.
result Characterization and analysis of online learnability in the model.
Characterizes statistical complexity of realizable regression in PAC and online learning.
problem Understanding the statistical complexity of realizable regression in both PAC and online learning settings.
method Introduces minimax instance optimal learners, novel and combinatorial dimensions to characterize learnability.
result Characterizes which classes of real-valued predictors are learnable and provides necessary conditions for learnability.
Research characterizes learnability of multilabel ranking problems.
problem Learnability of multilabel ranking problems with relevance-score feedback.
method Characterizes learnability in batch and online settings for a large family of ranking losses.
result Characterizes two equivalence classes of ranking losses based on learnability.
New insights into learning from distributional adversaries and private data.
problem Understanding minimal assumptions for learning and generalization under distributional constraints.
method Generalized smoothness as a characterization of learnability and privacy under distributional adversaries.
result Near complete characterization of families that admit learnability and privacy under distributional adversaries.
New algorithm learns multiclass concepts with finite Littlestone dimension.
problem Agnostic online multiclass classification in adversarial settings.
method Multiplicative weights algorithm with experts based on subsequences.
result Proves agnostic learnability if and only if Littlestone dimension is finite.
New protocol for online learning with partial feedback, extending classical methods.
problem Learning with partial feedback where only one acceptable label is observed per round.
method Introducing a collection version space to address the lack of direct extension of classical methods.
result Characterization of learnability in set-realizable regime using Partial-Feedback Littlestone dimension and Partial-Feedback Measure Shattering dimension.
We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning with i.i.d. data. Our proposed sequential complexities can be seen as extensions of these measures to …
New findings show limitations in converting private learning to online learning efficiently.
problem Limitations in converting private learning to online learning efficiently.
method Assuming one-way functions, we show an efficient conversion from pure-private learners to online learners is impossible.
result Efficient conversion from pure-private learners to online learners is impossible under certain assumptions.
New framework for understanding adversarial and stochastic learning.
problem Understanding the continuum from adversarial to stochastic settings in online learning.
method Distributionally constrained adversaries framework.
result Characterization of learnable distribution classes for various function classes.
New complexity measure helps in agnostic reinforcement learning with or without access to MDP dynamics.
problem Understanding the number of rounds needed to learn an ε-suboptimal policy in unknown MDPs.
method Introducing spanning capacity as a new complexity measure and developing POPLER algorithm.
result There is a separation between generative and online access models for agnostic learnability.
Study laws of large numbers in online classification, determining optimal regret bounds.
problem Understanding how sequential sampling affects online learning and classification.
method Characterized online learnable classes and determined optimal regret bounds using Littlestone's dimension.
result Optimal regret bounds in online learning are determined, resolving open questions.
Study robust online learning with adversarial perturbations.
problem Learning robust classifiers in the presence of adversarial perturbations.
method Formulated as an online learning problem, considered both realizable and agnostic learnability, defined new dimension controlling mistake/regret bounds.
result Showed new dimension controls mistake/regret bounds, generalized to multiclass hypothesis classes.
Research on predicting with lists of labels, characterizing learnability and providing algorithms.
problem Multiclass online prediction with multiple labels.
method Characterization using b b b -ary Littlestone dimension, adaptation of classical algorithms, combinatorial results. result Achievement of negative regret in some scenarios, complete characterization of learnability.
Learning theory has largely focused on two main learning scenarios. The first is the classical statistical setting where instances are drawn i.i.d. from a fixed distribution and the second scenario is the online learning, completely adversarial scenario where adversary at every time step picks the worst instance to pro…
We study online learnability of a wide class of problems, extending the results of (Rakhlin, Sridharan, Tewari, 2010) to general notions of performance measure well beyond external regret. Our framework simultaneously captures such well-known notions as internal and general Phi-regret, learning with non-additive global…
We study the problem of learning influence functions under incomplete observations of node activations. Incomplete observations are a major concern as most (online and real-world) social networks are not fully observable. We establish both proper and improper PAC learnability of influence functions under randomly missi…
Study on computable online learning with new conditions and complexities.
problem Characterizing optimal online learning under varying optimality requirements.
method Introduced anytime optimal (a-optimal) online learning and explored computational separations.
result Found a computational separation between a-optimal and optimal online learning.
Study on computational aspects of replicable learning, bridging statistical and algorithmic perspectives.
problem Understanding the computational connections between replicability and various learning paradigms.
method Design of replicable learners, lifting framework, and transformation techniques.
result Efficient replicable learners for specific learning problems under various distributions.
This work tackles online memory selection in continual learning using information theory.
problem Online selection of a representative replay memory from data streams.
method Information-theoretic criteria (surprise, learnability) and Bayesian model for efficient computation.
result InfoRS improves robustness against data imbalance compared to reservoir sampling.
In many domains, collecting sufficient labeled training data for supervised machine learning requires easily accessible but noisy sources, such as crowdsourcing services or tagged Web data. Noisy labels occur frequently in data sets harvested via these means, sometimes resulting in entire classes of data on which learn…
Study shows realizable learnability doesn't imply agnostic learnability for distributions.
problem Learnability and robustness of distribution classes.
method Analyzes the relationship between learnability and robustness for distribution learning.
result Realizable learnability does not imply agnostic learnability for distributions.
Curiosity-Critic improves world model training by focusing on cumulative prediction error.
problem Training world models with intrinsic rewards that consider cumulative prediction error.
method Curiosity-Critic uses a surrogate reward based on the difference between current and asymptotic prediction errors, estimated online by a co-trained critic.
result Curiosity-Critic outperforms other methods in training speed and final world model accuracy.
Understanding and interacting with everyday physical scenes requires rich knowledge about the structure of the world, represented either implicitly in a value or policy function, or explicitly in a transition model. Here we introduce a new class of learnable models--based on graph networks--which implement an inductive…
We develop a mean-field theory for multi-component ICA in high dimensions.
problem Understanding multi-component ICA in high-dimensional settings.
method Asymptotically exact mean-field theory for multi-component online ICA.
result Explicit learnability boundaries and competition conditions linking step size, data moments, and initialization.
Algorithm reduces regret in misspecified linear contextual bandits.
problem Misspecified linear contextual bandits with bounded misspecification.
method Data selection scheme for online regression, leveraging uncertainty.
result Regret bound of O ~ ( d 2 / Δ ) \tilde O(d^2/Δ) O ~ ( d 2 /Δ ) when ζ ≤ O ~ ( Δ / d ) ζ \leq \tilde O(Δ/\sqrt{d}) ζ ≤ O ~ ( Δ/ d ) . A deterministic apple tasting learner is developed, confirming a conjecture and providing tight bounds for mistake bounds.
problem Determining the learnability of hypothesis classes in binary online classification with apple tasting feedback.
method Developed a deterministic apple tasting learner and proved tight bounds for mistake bounds.
result Deterministic apple tasting is feasible and provides tight bounds for mistake bounds.
Study minimax rates for online learning with time-varying dynamics.
problem Online learning with time-varying state and cost dynamics.
method Non-constructive upper and lower bounds, complexity and stability terms.
result Characterization of minimax rates and necessary conditions for learnability.
New framework models echo chamber learning, proving tight bounds on algorithm performance.
problem Echo chambers in machine learning where systems learn from self-annotated data.
method Online Learning in the Replay Setting, Extended Threshold dimension, closure-based learner.
result Proves tight bounds on algorithm performance against replay adversaries.
Improved learning algorithms with privacy using smoothed analysis.
problem Designing robust and private learning algorithms.
method Smoothed analysis of adversarial and differentially private learning.
result Stronger regret and privacy error guarantees with smoothed adversaries.
Study apple tasting feedback in online binary classification, providing new insights into minimax expected mistakes.
problem Online binary classification with partial feedback (apple tasting).
method Combinatorial analysis, Littlestone dimension, Effective width.
result Established a trichotomy of minimax expected mistakes in the realizable setting.
Novel approach to universal online learning for bounded losses, closing open problems.
problem Characterizing processes for universal online learning under non-i.i.d. conditions.
method Characterization of processes admitting strong and weak universal learning, introduction of optimistically universal learning rule.
result Introduction of a novel 1NN algorithm that is optimistically universal for bounded losses.
This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given…
Example shows learnable distributions not privately learnable.
problem Learnable distributions under non-private conditions not transferable to differential privacy.
method Example of a distribution class learnable up to constant error in total variation distance but not under differential privacy.
result Contradicts conjecture of Ashtiani on learnability under differential privacy.
New findings on universal learning in contextual bandits with adversarial rewards.
problem Learning in contextual bandits with time-varying, adversarial rewards.
method Characterization of learnable processes and necessary/sufficient conditions for universal learning.
result Optimistic universal learning for contextual bandits with adversarial rewards is impossible in general.
Algorithm learns dynamics from past observations.
problem Learning a nonlinear dynamical system.
method Spectral filtering, online convex optimization.
result Vanishing prediction error for marginally stable systems.
Study on tradeoffs between mistakes and ERM oracle calls in online and transductive learning.
problem Analyzing online and transductive learning with limited ERM and weak consistency oracle access.
method Proves lower bounds and upper bounds on mistakes and oracle calls, considering realizable and agnostic cases.
result Achieves optimal mistake bounds with weak consistency queries for certain concept classes.
Study shows observing order book can significantly improve online market making performance.
problem Online market making with private valuations and limited feedback.
method Introduces action-dependent feedback model and proposes elimination-based and explore-then-perturb algorithms.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret bounds with high probability in various settings.