A General Method for Robust Learning from Batches

• URL: http://arxiv.org/abs/2002.11099v1
• Date: Tue, 25 Feb 2020 18:53:25 GMT
• Title: A General Method for Robust Learning from Batches
• Authors: Ayush Jain and Alon Orlitsky
• Abstract summary: We consider a general framework of robust learning from batches, and determine the limits of both classification and distribution estimation over arbitrary, including continuous, domains. We derive the first robust computationally-efficient learning algorithms for piecewise-interval classification, and for piecewise-polynomial, monotone, log-concave, and gaussian-mixture distribution estimation.
• Score: 56.59844655107251
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many applications, data is collected in batches, some of which are corrupt or even adversarial. Recent work derived optimal robust algorithms for estimating discrete distributions in this setting. We consider a general framework of robust learning from batches, and determine the limits of both classification and distribution estimation over arbitrary, including continuous, domains. Building on these results, we derive the first robust agnostic computationally-efficient learning algorithms for piecewise-interval classification, and for piecewise-polynomial, monotone, log-concave, and gaussian-mixture distribution estimation.

Related papers

• A naive aggregation algorithm for improving generalization in a class of learning problems [0.0]
  We present a naive aggregation algorithm for a typical learning problem with expert advice setting. In particular, we consider a class of learning problem of point estimations for modeling high-dimensional nonlinear functions.
  arXiv  Detail & Related papers  (2024-09-06T15:34:17Z)
• On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
  We provide theoretical guarantees for the convergence behaviour of diffusion-based generative models under strongly log-concave data. Our class of functions used for score estimation is made of Lipschitz continuous functions avoiding any Lipschitzness assumption on the score function. This approach yields the best known convergence rate for our sampling algorithm.
  arXiv  Detail & Related papers  (2023-11-22T18:40:45Z)
• Diverse Projection Ensembles for Distributional Reinforcement Learning [6.754994171490016]
  This work studies the combination of several different projections and representations in a distributional ensemble. We derive an algorithm that uses ensemble disagreement, measured by the average $1$-Wasserstein distance, as a bonus for deep exploration.
  arXiv  Detail & Related papers  (2023-06-12T13:59:48Z)
• Compound Batch Normalization for Long-tailed Image Classification [77.42829178064807]
  We propose a compound batch normalization method based on a Gaussian mixture. It can model the feature space more comprehensively and reduce the dominance of head classes. The proposed method outperforms existing methods on long-tailed image classification.
  arXiv  Detail & Related papers  (2022-12-02T07:31:39Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms. We develop a general framework from the perspective of Bregman minimization divergence. We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
  arXiv  Detail & Related papers  (2021-12-07T01:23:20Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound [15.557653926558638]
  We investigate a counterpart of majority votes over finite ensembles of classifiers, and study its generalization properties. We instantiate it with Dirichlet distributions: this allows for a closed-form and differentiable expression for the expected risk. The resulting majority vote learning algorithm achieves state-of-the-art accuracy and benefits from (non-vacuous) tight bounds.
  arXiv  Detail & Related papers  (2021-06-23T16:57:23Z)
• Greedy Bayesian Posterior Approximation with Deep Ensembles [22.466176036646814]
  Ensembles of independently trained objective are a state-of-the-art approach to estimate predictive uncertainty in Deep Learning. We show that our method is submodular with respect to the mixture of components for any problem in a function space.
  arXiv  Detail & Related papers  (2021-05-29T11:35:27Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.