Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression

• URL: http://arxiv.org/abs/2304.00051v1
• Date: Fri, 31 Mar 2023 18:12:33 GMT
• Title: Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression
• Authors: Alexander Munteanu, Simon Omlor, David Woodruff
• Abstract summary: We improve upon previous oblivious sketching and turnstile streaming results for $ell_1$ and logistic regression. We also give a tradeoff that yields a $1+varepsilon$ approximation in input sparsity time. Our sketch can be extended to approximate a regularized version of logistic regression where the data-dependent regularizer corresponds to the variance of the individual logistic losses.
• Score: 74.28017932704704
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We improve upon previous oblivious sketching and turnstile streaming results for $\ell_1$ and logistic regression, giving a much smaller sketching dimension achieving $O(1)$-approximation and yielding an efficient optimization problem in the sketch space. Namely, we achieve for any constant $c>0$ a sketching dimension of $\tilde{O}(d^{1+c})$ for $\ell_1$ regression and $\tilde{O}(\mu d^{1+c})$ for logistic regression, where $\mu$ is a standard measure that captures the complexity of compressing the data. For $\ell_1$-regression our sketching dimension is near-linear and improves previous work which either required $\Omega(\log d)$-approximation with this sketching dimension, or required a larger $\operatorname{poly}(d)$ number of rows. Similarly, for logistic regression previous work had worse $\operatorname{poly}(\mu d)$ factors in its sketching dimension. We also give a tradeoff that yields a $1+\varepsilon$ approximation in input sparsity time by increasing the total size to $(d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for $\ell_1$ and to $(\mu d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for logistic regression. Finally, we show that our sketch can be extended to approximate a regularized version of logistic regression where the data-dependent regularizer corresponds to the variance of the individual logistic losses.

Related papers

• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  We develop a novel algorithm for sampling rows $a_i$ of a matrix $AinmathbbRntimes d$, proportional to their $ell_p$ norm, when $A$ is presented in a turnstile data stream. Our algorithm not only returns the set of sampled row indexes, it also returns slightly perturbed rows $tildea_i approx a_i$, and approximates their sampling probabilities up to $varepsilon$ relative error. For logistic regression, our framework yields the first algorithm that achieves a $
  arXiv  Detail & Related papers  (2024-06-01T07:33:41Z)
• Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations [51.14495595270775]
  We adapt the Frank-Wolfe algorithm for $L_1$ penalized linear regression to be aware of sparse inputs and to use them effectively. Our results demonstrate that this procedure can reduce runtime by a factor of up to $2,200times$, depending on the value of the privacy parameter $epsilon$ and the sparsity of the dataset.
  arXiv  Detail & Related papers  (2023-10-30T19:52:43Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  We study oblivious sketching for $k$-sparse linear regression under various loss functions such as an $ell_p$ norm, or from a broad class of hinge-like loss functions. We show that for sparse $ell$vareps regression, there is an oblivious distribution over sketches with $Theta(klog(d/k)/varepsilon2)$ rows, which is tight up to a constant factor. We also show that sketching $O(mu2 klog(mu n d/varepsilon)/var
  arXiv  Detail & Related papers  (2023-04-05T07:24:19Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• Oblivious sketching for logistic regression [72.42202783677811]
  We present the first data oblivious sketch for logistic regression. Our sketches are fast, simple, easy to implement, and our experiments demonstrate their practicality.
  arXiv  Detail & Related papers  (2021-07-14T11:29:26Z)
• L1 Regression with Lewis Weights Subsampling [10.796388585158184]
  We show that sampling from $X$ according to its Lewis weights and outputting the empirical minimizer succeeds with probability $1-delta$ for $m. We also give a corresponding lower bound of $Omega(fracdvarepsilon2 + (d + frac1varepsilon2) logfrac1delta)$.
  arXiv  Detail & Related papers  (2021-05-19T23:15:00Z)
• Truncated Linear Regression in High Dimensions [26.41623833920794]
  In truncated linear regression, $(A_i, y_i)_i$ whose dependent variable equals $y_i= A_irm T cdot x* + eta_i$ is some fixed unknown vector of interest. The goal is to recover $x*$ under some favorable conditions on the $A_i$'s and the noise distribution. We prove that there exists a computationally and statistically efficient method for recovering $k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated samples.
  arXiv  Detail & Related papers  (2020-07-29T00:31:34Z)

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.