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 algorithm learns halfspaces over hypercube with random bit flips.
problem Agnostic learning of Boolean halfspaces over discrete domains is computationally hard.
method Smoothed analysis with random bit flips for discrete inputs.
result First efficient algorithm for smoothed agnostic learning of halfspaces over Boolean hypercube.
New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.
problem Smoothed agnostic learning of halfspaces under subgaussian distributions.
method Statistical Query (SQ) lower bound using moment-matching hard distribution and linear programming duality.
result First non-trivial lower bound on complexity nearly matches known upper bound.
NSGD-M optimizes machine learning models without hyperparameter tuning, even under relaxed smoothness.
problem Training machine learning models with optimal complexity under relaxed smoothness assumptions.
method Normalized Stochastic Gradient Descent with Momentum (NSGD-M) without stepsize tuning.
result NSGD-M achieves nearly optimal complexity without prior knowledge of problem parameters.
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.
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.
Study non-stationary distributions, proving risk bounds for density estimation.
problem Estimating current distribution under gradual changes.
method Proves tight minimax risk bounds for nonparametric density estimation under drift.
result Generalizes previous results on agnostic learning under drift.
Gradient EM converges exponentially to optimal solution in agnostic mixtures.
problem Fitting k parametric functions to given data points without a generative model. method Gradient EM algorithm for agnostic mixtures of arbitrary parametric functions.
result Gradient EM converges exponentially to population loss minimizers with high probability.
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.
Double Machine Learning estimators are asymptotically inadmissible under structure-agnostic models.
problem Minimax estimators may be inadmissible under structure-agnostic models.
method Exhibit second-order (U-statistic) estimators that asymptotically dominate DML estimators.
result Double Machine Learning estimators are asymptotically inadmissible under structure-agnostic models.
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…
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.
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 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.
Improved learning rates with new smoothness measure.
problem Learning with noisy data and unknown function class.
method Generalized Hölder smoothness to average smoothness, proving upper and lower bounds.
result Achieved nearly optimal learning rates in realizable and agnostic settings.
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.
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.
Study shows transductive learning is equivalent to PAC learning for most natural loss functions.
problem Understanding the relationship between transductive and PAC learning models.
method Extending existing results and developing new techniques to analyze the equivalence of the two models.
result Transductive learning is essentially equivalent to PAC learning for realizable learning with most natural loss functions.
NeAda solves nonconvex minimax optimization by balancing primal and dual variables adaptively.
problem Nonconvex minimax optimization challenges with parameter-agnostic adaptive algorithms.
method Nested Adaptive (NeAda) framework with inner and outer loops for primal and dual variables.
result Achieves near-optimal convergence rates for nonconvex-strongly-concave problems.
DAFNO learns surrogates for complex systems on irregular geometries.
problem Learning accurate surrogates for complex physical systems on irregular geometries.
method DAFNO incorporates a smoothed characteristic function in the integral layer architecture of FNOs, leveraging FFT for rapid computations.
result DAFNO achieves state-of-the-art accuracy on material modeling and airfoil simulation datasets.
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.
Decision tree learning heuristics fail even in smoothed analysis for complex targets.
problem Greedy decision tree learning heuristics fail for complex target functions in the smoothed analysis model.
method Construct counterexamples and analyze the behavior of heuristics in the smoothed setting and agnostic setting.
result Greedy decision tree learning heuristics can build trees of exponential depth before achieving high accuracy for certain complex target functions.
Current deep learning based text classification methods are limited by their ability to achieve fast learning and generalization when the data is scarce. We address this problem by integrating a meta-learning procedure that uses the knowledge learned across many tasks as an inductive bias towards better natural languag…
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…
Study agnostic RL in large state spaces with weak function approximation.
problem Statistical intractability of agnostic policy learning in various environments.
method Investigates agnostic policy learning with different forms of environment access.
result Agnostic policy learning remains statistically intractable with certain forms of environment access.
Improved agnostic learning time via Gaussian surface area analysis.
problem Learning polynomial threshold functions under Gaussian marginals.
method Improvement of polynomial degree required for approximation.
result Near optimal bounds on agnostic learning complexity.
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.
This paper studies universal rates of ERM for binary classification under agnostic learning.
problem The challenge of achieving universal rates of ERM for binary classification under agnostic learning.
method The paper explores the agnostic universal rates of ERM for binary classification, revealing three possible rates: e−n, o(n−1/2), or arbitrarily slow. result The paper provides a complete characterization of which concept classes fall into each of the three categories of agnostic universal rates.
A new biased gradient descent method for conditional stochastic optimization.
problem Challenges in constructing unbiased gradient estimators for conditional stochastic optimization.
method Proposes a biased stochastic gradient descent (BSGD) algorithm and analyzes its sample complexities.
result Establishes sample complexities of BSGD for various objectives and shows that BSpiderBoost matches the lower bound complexity.
New algorithm reduces pricing error by a factor of T^2/3.
problem Optimal pricing under non-Lipschitz demand with unknown jumps and atoms.
method Conservative-Markdown Redirect-UCB Pricing, combining estimation, probing, and redirection.
result Achieves optimal regret of O(T^2/3), matching lower bounds.
Surrogate-based analysis of interactions via local effect smooths
problem Detecting and characterizing feature interactions in machine learning models
method Surrogate-based analysis using generalized additive models
result Empirical validation of effectiveness for pairwise interactions
Paper analyzes error exponent in agnostic PAC learning.
problem Analyzing performance of agnostic PAC learning.
method Using error exponent from Information Theory to analyze PAC learning.
result Improved distribution-dependent error exponent for agnostic learning.
This paper proposes a system-agnostic policy for dynamic scheduling.
problem Dynamic scheduling in changing systems is challenging due to system-specific optimal policies.
method Descriptive policy that learns a system-agnostic scheduling principle.
result System-agnostic meta-learning enables adaptation to unseen system characteristics.
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.
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.
New method learns SIMs with arbitrary monotone activations without strong distributional assumptions.
problem Learning Single-Index Models with arbitrary monotone activations.
method Based on omniprediction with calibrated multiaccuracy and Bregman divergences.
result First agnostic learning result for SIMs with arbitrary monotone activations.
New method calibrates multi-class predictions efficiently without sacrificing accuracy.
problem Efficiently calibrating multi-class predictions without sacrificing accuracy.
method Formulated robust projected smooth calibration and new recalibration algorithms.
result Achieves strong guarantees for binary classification tasks with polynomial complexity.
Unified framework for realizable and agnostic learning.
problem Lack of a unified theory for realizable and agnostic learnability.
method Three-line blackbox reduction.
result Unified understanding across various learning settings.
Improved agnostic boosting with better sample efficiency.
problem Agnostic boosting's poor sample efficiency compared to Empirical Risk Minimization.
method Leverages sample reuse across rounds, guarantees better generalization.
result Substantially more sample-efficient agnostic boosting algorithm.
AI methods broaden signal discovery in scientific data.
problem Limited coverage of possible signals in model-dependent searches.
method Model-agnostic AI strategies for broad exploration.
result Enhanced discovery potential in experimental science.
Bayesian MAML outperforms MAML in meta learning tasks with theoretical guarantees.
problem Theoretical understanding of Bayesian MAML's superiority over MAML.
method Comparison of meta test risks between Bayesian MAML and MAML in meta linear regression.
result Bayesian MAML has provably lower meta test risks than MAML in both distribution agnostic and linear centroid cases.
Model agnostic feature importance for DNNs in NLP.
problem Characterizing DNNs as black boxes and explaining their decision-making process.
method Phrase-wise feature importance calculation for model agnostic DNNs.
result Robust and generalizable approach to feature importance calculation.
New insights into RL with weak function approximation.
problem Statistical complexity of RL with function approximation in large state spaces.
method Agnostic policy learning framework, exploring environment access, coverage, and representational conditions.
result Characterization of fundamental performance bounds and statistical separations.
Boosts weak online learners to strong ones with sublinear regret.
problem Online learning agnostic setting without strong guarantees.
method Reduction to online convex optimization, boosting via marginally-better-than-trivial regret guarantees.
result First agnostic online boosting algorithm with sublinear regret.
New algorithm for reliable learning of Gaussian halfspaces with improved sample and computational complexity.
problem Learning halfspaces under Gaussian marginals with reliable agnostic model.
method Developed a new algorithm for reliable learning of Gaussian halfspaces with specific sample and computational complexity.
result Achieved a new algorithm with improved sample and computational complexity for reliable learning of Gaussian halfspaces.
New method extends low-rank MDPs to continuous action spaces.
problem Limited applicability of current low-rank MDP methods to continuous action spaces.
method Extending FLAMBE algorithm to continuous action spaces with Hölder smoothness conditions.
result Similar PAC bound achieved for continuous actions with polynomial dependence on smoothness order.
Gradient descent finds halfspaces with low error for agnostic learning.
problem Agnostic learning of linear halfspaces with convex surrogates.
method Gradient descent on convex surrogates for zero-one loss.
result Gradient descent finds halfspaces with error O(OPT1/2+ε) in poly time and sample complexity. New algorithm improves active learning in agnostic pool-based classification.
problem Efficient active learning in the agnostic setting with minimized sample complexity.
method Solves an experimental design problem to determine a distribution over examples for label requests.
result Achieves sample complexity bounds never worse than best disagreement coefficient-based bounds, sometimes significantly smaller.