Accurate Coresets for Latent Variable Models and Regularized Regression

• URL: http://arxiv.org/abs/2412.20189v1
• Date: Sat, 28 Dec 2024 16:01:49 GMT
• Title: Accurate Coresets for Latent Variable Models and Regularized Regression
• Authors: Sanskar Ranjan, Supratim Shit,
• Abstract summary: We introduce a unified framework for constructing accurate coresets. We present accurate coreset construction algorithms for general problems. We substantiate our theoretical findings with extensive experimental evaluations on real datasets.
• Score: 1.9567015559455132
• License:
• Abstract: Accurate coresets are a weighted subset of the original dataset, ensuring a model trained on the accurate coreset maintains the same level of accuracy as a model trained on the full dataset. Primarily, these coresets have been studied for a limited range of machine learning models. In this paper, we introduce a unified framework for constructing accurate coresets. Using this framework, we present accurate coreset construction algorithms for general problems, including a wide range of latent variable model problems and $\ell_p$-regularized $\ell_p$-regression. For latent variable models, our coreset size is $O\left(\mathrm{poly}(k)\right)$, where $k$ is the number of latent variables. For $\ell_p$-regularized $\ell_p$-regression, our algorithm captures the reduction of model complexity due to regularization, resulting in a coreset whose size is always smaller than $d^{p}$ for a regularization parameter $\lambda > 0$. Here, $d$ is the dimension of the input points. This inherently improves the size of the accurate coreset for ridge regression. We substantiate our theoretical findings with extensive experimental evaluations on real datasets.

Related papers

• Scaling Laws in Linear Regression: Compute, Parameters, and Data [86.48154162485712]
  We study the theory of scaling laws in an infinite dimensional linear regression setup. We show that the reducible part of the test error is $Theta(-(a-1) + N-(a-1)/a)$. Our theory is consistent with the empirical neural scaling laws and verified by numerical simulation.
  arXiv  Detail & Related papers  (2024-06-12T17:53:29Z)
• Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensing [30.508036898655114]
  Pruning schemes have been widely used in practice to reduce the complexity of trained models with a massive number of parameters. Running gradient descent in the absence of regularization results in models which are not suitable for greedy pruning, i.e., many columns could have their $ell$ norm comparable to that of the maximum. Our results provide the first rigorous insights on why greedy pruning + fine-tuning leads to smaller models which also generalize well.
  arXiv  Detail & Related papers  (2023-03-20T21:05:44Z)
• Easy Differentially Private Linear Regression [16.325734286930764]
  We study an algorithm which uses the exponential mechanism to select a model with high Tukey depth from a collection of non-private regression models. We find that this algorithm obtains strong empirical performance in the data-rich setting.
  arXiv  Detail & Related papers  (2022-08-15T17:42:27Z)
• $p$-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets [74.37849422071206]
  We study the $p$-generalized probit regression model, which is a generalized linear model for binary responses. We show how the maximum likelihood estimator for $p$-generalized probit regression can be approximated efficiently up to a factor of $(1+varepsilon)$ on large data.
  arXiv  Detail & Related papers  (2022-03-25T10:54:41Z)
• Coresets for Time Series Clustering [33.801060211529354]
  We study the problem of constructing coresets for clustering problems with time series data. Our main contribution is an algorithm to construct coresets for a mixture model. We empirically assess the performance of our coreset with synthetic data.
  arXiv  Detail & Related papers  (2021-10-28T16:21:13Z)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  We propose a simple and practical tool $mathsfFriendlyCore$ that takes a set of points $cal D$ from an unrestricted (pseudo) metric space as input. When $cal D$ has effective diameter $r$, $mathsfFriendlyCore$ returns a "stable" subset $cal D_Gsubseteq cal D$ that includes all points. $mathsfFriendlyCore$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy
  arXiv  Detail & Related papers  (2021-10-19T17:43:50Z)
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios [69.2027612631023]
  We show that locality is key in determining the learning curve exponent $beta$. We conclude by proving, using a natural assumption, that performing kernel regression with a ridge that decreases with the size of the training set leads to similar learning curve exponents to those we obtain in the ridgeless case.
  arXiv  Detail & Related papers  (2021-06-16T08:27:31Z)
• Flexible Model Aggregation for Quantile Regression [92.63075261170302]
  Quantile regression is a fundamental problem in statistical learning motivated by a need to quantify uncertainty in predictions. We investigate methods for aggregating any number of conditional quantile models. All of the models we consider in this paper can be fit using modern deep learning toolkits.
  arXiv  Detail & Related papers  (2021-02-26T23:21:16Z)
• Coresets for Regressions with Panel Data [29.910677117943568]
  We first define coresets for regression problems with panel data and then present efficient algorithms to construct coresets. Our approach is based on the Feldman-Langberg framework in which a key step is to upper bound the "total sensitivity" Empirically, we assess our approach with real-world datasets.
  arXiv  Detail & Related papers  (2020-11-02T13:58:31Z)
• On Coresets For Regularized Regression [8.965836729525394]
  We analyze the size of coresets for regularized versions of regression of the form $|mathbfAx-mathbfb|_pr + lambda|mathbfx|_qs$. We show that when $r neq s$, no coreset for regularized regression can have size smaller than the optimal coreset of the unregularized version.
  arXiv  Detail & Related papers  (2020-06-09T18:25:04Z)
• Model-Based Reinforcement Learning with Value-Targeted Regression [48.92439657407732]
  We focus on finite-horizon episodic RL where the transition model $P$ belongs to a known family of models $mathcalP$. We derive a bound on the regret, which, in the special case of linear mixtures, the regret bound takes the form $tildemathcalO(dsqrtH3T)$.
  arXiv  Detail & Related papers  (2020-06-01T17:47:53Z)

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.