MP-Boost: Minipatch Boosting via Adaptive Feature and Observation Sampling

• URL: http://arxiv.org/abs/2011.07218v1
• Date: Sat, 14 Nov 2020 04:26:13 GMT
• Title: MP-Boost: Minipatch Boosting via Adaptive Feature and Observation Sampling
• Authors: Mohammad Taha Toghani, Genevera I. Allen
• Abstract summary: MP-Boost is an algorithm loosely based on AdaBoost that learns by adaptively selecting small subsets of instances and features. We empirically demonstrate the interpretability, comparative accuracy, and computational time of our approach on a variety of binary classification tasks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boosting methods are among the best general-purpose and off-the-shelf machine learning approaches, gaining widespread popularity. In this paper, we seek to develop a boosting method that yields comparable accuracy to popular AdaBoost and gradient boosting methods, yet is faster computationally and whose solution is more interpretable. We achieve this by developing MP-Boost, an algorithm loosely based on AdaBoost that learns by adaptively selecting small subsets of instances and features, or what we term minipatches (MP), at each iteration. By sequentially learning on tiny subsets of the data, our approach is computationally faster than other classic boosting algorithms. Also as it progresses, MP-Boost adaptively learns a probability distribution on the features and instances that upweight the most important features and challenging instances, hence adaptively selecting the most relevant minipatches for learning. These learned probability distributions also aid in interpretation of our method. We empirically demonstrate the interpretability, comparative accuracy, and computational time of our approach on a variety of binary classification tasks.

Related papers

• Sample-Efficient Agnostic Boosting [19.15484761265653]
  Empirical Risk Minimization (ERM) outstrips the agnostic boosting methodology in being quadratically more sample efficient than all known boosting algorithms. A key feature of our algorithm is that it leverages the ability to reuse samples across multiple rounds of boosting, while guaranteeing a generalization error strictly better than those obtained by blackbox applications of uniform convergence arguments.
  arXiv  Detail & Related papers  (2024-10-31T04:50:29Z)
• The Many Faces of Optimal Weak-to-Strong Learning [10.985323882432086]
  We present a new and surprisingly simple Boosting algorithm that obtains a provably optimal sample complexity. Our pilot empirical study suggests that our new algorithm might outperform previous algorithms on large data sets.
  arXiv  Detail & Related papers  (2024-08-30T09:38:51Z)
• How to Boost Any Loss Function [63.573324901948716]
  We show that any loss function can be optimized with boosting. We also show that boosting can achieve a feat not yet known to be possible in the classical $0th$ order setting.
  arXiv  Detail & Related papers  (2024-07-02T14:08:23Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  We give a simple and efficient boosting algorithm, that does not require realizability assumptions. We present a new result on boosting for list learners, as well as provide a novel proof for the characterization of multiclass PAC learning.
  arXiv  Detail & Related papers  (2023-07-02T19:26:58Z)
• AdaBoost is not an Optimal Weak to Strong Learner [11.003568749905359]
  We show that the sample complexity of AdaBoost, and other classic variations thereof, are sub-optimal by at least one logarithmic factor in the desired accuracy of the strong learner.
  arXiv  Detail & Related papers  (2023-01-27T07:37:51Z)
• PromptBoosting: Black-Box Text Classification with Ten Forward Passes [61.38341243907045]
  We describe PromptBoosting, a query-efficient procedure for building a text classifier from a neural language model (LM) without access to the LM's parameters, gradients, or hidden representations. Experiments show that PromptBoosting achieves state-of-the-art performance in multiple black-box few-shot classification tasks, and matches or outperforms full fine-tuning in both few-shot and standard learning paradigms, while training 10x faster than existing black-box methods.
  arXiv  Detail & Related papers  (2022-12-19T06:04:54Z)
• Quantum Boosting using Domain-Partitioning Hypotheses [0.9264464791978363]
  Boosting is an ensemble learning method that converts a weak learner into a strong learner in the PAC learning framework. We show that Q-RealBoost provides a speedup over Q-AdaBoost in terms of both the bias of the weak learner and the time taken by the weak learner to learn the target concept class.
  arXiv  Detail & Related papers  (2021-10-25T10:46:13Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states. We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
  arXiv  Detail & Related papers  (2021-08-22T16:00:45Z)
• Boosting for Online Convex Optimization [64.15578413206715]
  We consider the decision-making framework of online convex optimization with a large number of experts. We define a weak learning algorithm as a mechanism that guarantees approximate regret against a base class of experts. We give an efficient boosting algorithm that guarantees near-optimal regret against the convex hull of the base class.
  arXiv  Detail & Related papers  (2021-02-18T12:30:49Z)
• ADABOOK & MULTIBOOK: Adaptive Boosting with Chance Correction [3.7819322027528113]
  It is possible for a weak learner to optimize Accuracy to the detriment of the more reaslistic chance-corrected measures, and when this happens the booster can give up too early. This paper thus complements the theoretical work showing the necessity of using chance-corrected measures for evaluation, with empirical work showing how use of a chance-corrected measure can improve boosting.
  arXiv  Detail & Related papers  (2020-10-11T01:17:32Z)
• On the Dual Formulation of Boosting Algorithms [92.74617630106559]
  We show that the Lagrange problems of AdaBoost, LogitBoost and soft-marginBoost are all dual problems with generalized hinge loss entropy. By looking at the dual problems of these boosting algorithms, we show that the success of boosting can be understood in terms of maintaining a better margin distribution.
  arXiv  Detail & Related papers  (2009-01-23T02:14:42Z)

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.