New bounds show agnostic multiclass learning depends on two dimensions: Natarajan and Daniely-Shalev-Shwartz.
problem Understanding sample complexity in multiclass classification with agnostic learning.
method Developed a novel online procedure based on a self-adaptive multiplicative-weights algorithm.
result Agnostic sample complexity bounds are in the form of DS^(1.5)/ε + Nat/ε^2, nearly tight up to a √DS factor.
We establish a tight characterization of the worst-case rates for the excess risk of agnostic learning with sample compression schemes and for uniform convergence for agnostic sample compression schemes. In particular, we find that the optimal rates of convergence for size-k agnostic sample compression schemes are of…
We obtain the first positive results for bounded sample compression in the agnostic regression setting with the ℓp loss, where p∈[1,∞]. We construct a generic approximate sample compression scheme for real-valued function classes exhibiting exponential size in the fat-shattering dimension but independen…
We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an ε-fraction of the samples. Such questions have a rich history spanning statistics, machine learning and theoretical computer science. Even in the most basic settings, the only known…
This paper develops dimension-agnostic inference methods for high-dimensional data.
problem Understanding how classical inference methods behave in high-dimensional settings.
method Using variational representations, sample splitting, and self-normalization to create a refined test statistic.
result The resulting statistic has a Gaussian limiting distribution regardless of how dimensionality scales with sample size.
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.
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.
Comparative learning combines realizable and agnostic settings for two hypothesis classes, reducing sample complexity.
problem Learning with two hypothesis classes in a more general setting than single hypothesis classes.
method Introduces comparative learning, defines mutual VC dimension and Littlestone dimension, and applies insights to multiaccuracy and multicalibration.
result Sample complexity of comparative learning is characterized by mutual VC dimension and Littlestone dimension.
New algorithms improve agnostic learning for triangles and polygons, reducing time complexity.
problem Efficient agnostic learning for geometric concept classes.
method Data structures and algorithms from computational geometry, probabilistic combinatorics.
result Optimal time complexity improvements for agnostic learning of triangles and polygons.
New methods interpret clustering outcomes without altering data structure.
problem Post-processing methods destroy data integrity and obscure interpretations.
method Algorithm-agnostic interpretation methods using permutation feature importance, individual conditional expectation, and partial dependence.
result Preserves original feature structure and explains clustering outcomes.
Study robust regression learning under adversarial attacks.
problem Understanding which function classes are learnable in the presence of adversarial attacks.
method Introduced a novel agnostic sample compression scheme and used fat-shattering dimension to construct adversarially robust sample compression schemes.
result Finite fat-shattering dimension classes are learnable in both realizable and agnostic settings.
Query access significantly speeds up learning Multi-Index Models under Gaussian distribution.
problem Agnostically learning Multi-Index Models (MIMs) under Gaussian distribution.
method Query access for MIMs with complexity O(k)poly(1/ε)poly(d) under standard regularity assumptions. result Query access gives significant runtime improvements over random examples for agnostically learning MIMs.
Paper defines a new dimension to measure self-directed learning complexity.
problem Understanding self-directed learning complexity in online learning theory.
method Developed a dimension SDdim to characterize self-directed learning mistake-bound. result Calculated SDdim for various concept classes and demonstrated learnability gaps. Improved private agnostic learning with near-optimal sample complexity.
problem Private agnostic learning with arbitrary privacy parameters.
method Near-optimal sample complexity construction.
result Near-optimal extra sample complexity of \(\widetilde{O}(\mathrm{VC}(\mathcal{C})/α^2)\) for any \(\varepsilon \leq 1\).
New bounds show complex neural networks need many queries to learn.
problem Learning non-polynomial activation functions with Gaussian marginals.
method Gradient boosting procedure to amplify lower bounds on SQ dimension of neural networks.
result Statistical-query lower bounds for ReLU regression with 2ncε queries. New algorithm reduces prediction error in online learning without knowing base measure.
problem Smoothed online learning without knowledge of base measure.
method R-Cover algorithm based on recursive coverings.
result First algorithm to guarantee sublinear regret for agnostic smoothed online learning without prior knowledge of base measure.
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.
Efficiently learns complex Boolean functions under Gaussian distributions.
problem Learning complex Boolean functions of halfspaces under Gaussian marginals.
method First efficient proper agnostic learning algorithm for arbitrary Boolean functions of K halfspaces.
result Matches the best known improper learning algorithm's run-time dependence on dimension.
New algorithm for learning functions with bounds on error and sample complexity.
problem Learning [0,1]-valued functions in a prediction model. method General-purpose algorithm with upper and lower bounds on expected error and sample complexity.
result Improved bounds on sample complexity and agnostic learning conditions.
The paper proposes a method to assess survey data credibility without needing many samples, regardless of data dimension.
problem Assessing the credibility of survey data across different dimensions.
method Task-based approach and model-specific distance metric for verifying survey data credibility in regression models.
result The sample complexity of the proposed algorithm is independent of the data dimension, making it more efficient.
New learner achieves optimal agnostic error in small error regime.
problem Optimizing agnostic learning in the small error regime.
method Careful aggregations of ERM classifiers.
result Achieves error $c \cdot τ+ O \left(\sqrt{\frac{τ(d + \log(1 / δ))}{m}} + \frac{d + \log(1 / δ)}{m}
ight)$, matching lower bound when τ≈d/m. Improved multi-group learning with group-realizable concepts.
problem Enhancing multi-group learning efficiency.
method Empirical risk minimization over group-realizable concepts.
result Improved sample complexity in group-realizable settings.
We clarify measurability assumptions in the agnostic PAC learning theorem.
problem Measurability assumptions in the Fundamental Theorem of Statistical Learning.
method Measure-theoretic scrutiny of existing proofs to extract minimal assumptions.
result Sound statement and detailed proof of the Fundamental Theorem in the agnostic setting.
New algorithms improve label complexity for active multi-distribution learning.
problem Active multi-distribution learning with improved label complexity.
method Developed new algorithms for active multi-distribution learning and established improved label complexity upper and lower bounds.
result Improved label complexity upper and lower bounds for active multi-distribution learning.
The current paper studies the problem of agnostic Q-learning with function approximation in deterministic systems where the optimal Q-function is approximable by a function in the class F with approximation error δ≥0. We propose a novel recursion-based algorithm and show that if $δ= O\left(ρ/\sqrt{…
Paper develops PAC verification for hypothesis classes and statistical algorithms.
problem Verifying machine learning models interactively.
method Develops interactive proof for PAC verification, proves lower bounds, and introduces a generalization.
result Improved protocol for verifying unions of intervals and statistical query algorithms.
Hardness proof for agnostically learning halfspaces from worst-case lattice problems.
problem Agnostically learning halfspaces in the presence of noise.
method Reduction to worst-case lattice problems (GapSVP, SIVP).
result No efficient algorithm can achieve misclassification error better than 1/2 - γ under given hardness assumptions.
First proper learning algorithm for Gaussian halfspaces with matching sample and computational complexity.
problem Agnostically learning halfspaces under Gaussian distribution.
method First proper learning algorithm with matching sample and computational complexity.
result First proper learning algorithm for agnostically learning halfspaces under Gaussian distribution with matching sample and computational complexity.
Characterizes the sample complexity of list regression tasks.
problem Understanding the sample complexity of list learning tasks in regression.
method Introducing two combinatorial dimensions: k-OIG dimension and k-fat-shattering dimension.
result These dimensions characterize realizable and agnostic k-list regression.
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
Study on learning to predict dynamical systems without assuming their structure.
problem Learning to predict the next state of a dynamical system with unknown evolution function.
method Defined new combinatorial measures to quantify mistake and regret bounds in realizable and agnostic settings.
result In the realizable setting, the number of mistakes can grow arbitrarily with time.
First-order ANIL learns shared representations even with overparametrization.
problem Lack of theoretical evidence for model-agnostic meta-learning (ANIL) learning shared representations.
method First-order ANIL with a linear two-layer network architecture, showing asymptotically low-rank solutions with overparametrization.
result First-order ANIL learns linear shared representations, even with overparametrization, and performs well in adaptation.
MAPS algorithm creates reliable prediction intervals for high-dimensional data.
problem Computing reliable conditional prediction intervals in high-dimensional settings.
method Lifted predictive model (LPM) and MAPS algorithm for distribution-free intervals.
result MAPS algorithm produces valid prediction intervals for any trained model.
New algorithm learns disjunctions faster than previous methods.
problem Learning Boolean disjunctions in the agnostic PAC model.
method Developed an agnostic learner with complexity 2ildeO(n1/3). result First separation between SQ and CSQ models in distribution-free agnostic learning.
New method for private density estimation of high-dimensional Gaussian mixtures.
problem Private density estimation for mixtures of unrestricted high-dimensional Gaussians.
method Exploits list global stability to prove upper bound on sample complexity.
result First upper bound on sample complexity for agnostic private density estimation.
The study optimizes polynomial regression for learning under Gaussian distributions.
problem Agnostic learning of Boolean and real-valued functions under Gaussian distributions.
method LP duality and polynomial degree analysis for L1-regression. result Optimal SQ lower bounds for various function classes.
Predicting the next position of movable objects has been a problem for at least the last three decades, referred to as trajectory prediction. In our days, the vast amounts of data being continuously produced add the big data dimension to the trajectory prediction problem, which we are trying to tackle by creating a λ-A…
New learning rules achieve optimal sample complexity for weakly supervised classification.
problem Learning from label proportions in weakly supervised settings.
method Debiased proportional square loss and EasyLLP learning rule.
result Achieves optimal sample complexity in both realizable and agnostic settings.
New algorithms save computation in agnostic learning with membership queries.
problem Efficiently learning touchstone classes with membership queries.
method Designing agnostic learning algorithms for circuits with sublinear gates.
result Agnostic learning algorithms for circuits with sublinear gates achieve significant computational savings.
We revisit the problem of differentially private release of classification queries. In this problem, the goal is to design an algorithm that can accurately answer a sequence of classification queries based on a private training set while ensuring differential privacy. We formally study this problem in the agnostic PAC …
New metric evaluates generative models across domains, diagnosing fidelity, diversity, and generalization.
problem Evaluating generative models in diverse domains with limited metrics.
method Introduces a 3D evaluation metric (α-Precision, β-Recall, Authenticity) for domain-agnostic diagnostics. result Unified metric characterizes fidelity, diversity, and generalization, diagnosing model performance.
We consider the problem of estimating the mean and covariance of a distribution from iid samples in Rn, in the presence of an η fraction of malicious noise; this is in contrast to much recent work where the noise itself is assumed to be from a distribution of known type. The agnostic problem includes many…
Recently, reducing communication time between machines becomes the main focus of distributed data mining. Previous methods propose to make workers do more computation locally before aggregating local solutions in the server such that fewer communication rounds between server and workers are required. However, these met…
New bounds for agnostic learning with average smoothness.
problem Distribution-free nonparametric regression with average smoothness.
method Distribution-free uniform convergence bounds and agnostic learning algorithm.
result Distribution-free uniform convergence bounds for average-smoothness classes in the agnostic setting.
New covariance estimator for financial portfolios.
problem Estimating large financial covariances in non-stationary environments.
method Exponentially weighted averages and cross-validation for nonlinearly shrinking sample eigenvalues.
result Our estimator performs well in large dimensions compared to existing estimators.
Boosting with unlabeled data achieves optimal sample complexity in agnostic settings.
problem Boosting's sample inefficiency in agnostic learning.
method Designing an agnostic boosting algorithm with unlabeled data to match ERM's sample complexity.
result The total sample complexity is optimal, with a vanishing fraction needing to be labeled.
New measure quantifies task difficulty for machine learning models.
problem Quantifying the inherent difficulty of machine learning tasks.
method Inductive bias complexity measure.
result Tasks requiring generalization over many dimensions are more difficult.
Proposes class-agnostic object detection to handle all objects without class labels.
problem Difficulty and cost in creating annotated datasets limit conventional object detection models to specific object types.
method Proposes class-agnostic object detection as a new problem and proposes training and evaluation protocols. Uses adversarial learning to exclude class-specific information.
result Adversarial learning improves class-agnostic detection efficacy.