Private sketches protect linear regression data privacy.
problem Protecting sensitive information in linear regression.
method Release private sketches of datasets, compute approximate solutions.
result Private sketches maintain good approximation guarantees to the original problem.
Projector-based approach quantifies uncertainties in sketched linear regression.
problem How sketching affects statistical properties of linear regression solutions.
method Projector-based approach to sketched linear regression that is exact and requires minimal assumptions.
result Derives key quantities from classic linear regression that account for combined uncertainties.
Improved sketching for logistic and ℓ 1 \ell_1 ℓ 1 regression with near-linear dimensions.
problem Efficiently approximate ℓ 1 \ell_1 ℓ 1 and logistic regression problems. method New sketching techniques achieving near-linear dimensions for both problems.
result Achieved near-linear sketching dimensions for ℓ 1 \ell_1 ℓ 1 and logistic regression. Optimal sketching bounds for sparse linear regression under various loss functions are established.
problem Sparse linear regression under different loss functions.
method Distribution over oblivious sketches for sparse ℓ 2 \ell_2 ℓ 2 norm regression and hinge-like loss functions. result Optimal sketching bounds with O ( k log ( d / k ) / ε 2 ) O(k\log(d/k)/\varepsilon^2) O ( k log ( d / k ) / ε 2 ) rows for sparse ℓ 2 \ell_2 ℓ 2 norm regression and O ( μ 2 k log ( μ n d / ε ) / ε 2 ) O(μ^2 k\log(μn d/\varepsilon)/\varepsilon^2) O ( μ 2 k log ( μ n d / ε ) / ε 2 ) rows for hinge-like loss functions. Downsampling can improve generalization in ridgeless linear regression, especially with optimal sketching size.
problem Improving generalization in ridgeless linear regression with limited data.
method Investigating the effects of downsampling on the sketched ridgeless least square estimator in the proportional regime.
result Optimal sketching size minimizes out-of-sample prediction risks and stabilizes risk curves.
Unified study of ridge regression structure, cross-validation, and acceleration.
problem Understanding and optimizing ridge regression in large-data settings.
method Unified large-data linear model analysis, cross-validation bias correction, sketching accuracy study.
result Unified understanding and improved methods for ridge regression.
Improved privacy-preserving linear regression via iterative Hessian mixing.
problem Differentially private linear regression with improved accuracy and efficiency.
method Iterative Hessian Mixing (IHM) for differentially private ordinary least squares (DP-OLS).
result IHM provides better utility guarantees and outperforms AdaSSP in empirical evaluations.
The paper analyzes sketching methods for regression, showing SRHT is superior.
problem Improving regression accuracy with sketching methods.
method Randomly projecting data and then performing regression.
result SRHT outperforms Gaussian projections in asymptotic analysis.
Polynomial sketch approximates functions of low-rank matrices efficiently.
problem Approximating element-wise functions of low-rank matrices without full access.
method Combining polynomial approximation and tensor sketch for monomials.
result Efficient algorithm with lower complexity than full matrix access.
Novel bounds for logistic regression coreset construction and feature selection.
problem Efficiently summarize and reduce logistic regression inputs.
method Feature space sketching for logistic regression.
result Tight bounds for coreset construction and feature selection.
Localized sketching improves matrix multiplication and ridge regression complexity.
problem Efficiently approximate matrix multiplication and ridge regression with limited data availability.
method Localized sketching matrices for block diagonal structure, reducing sample complexity.
result Localized sketching achieves sample complexity matching global sketching methods.
Bayesian data sketching speeds up inference for large functional data.
problem Slow posterior computations in Bayesian varying coefficient models for large data.
method Compress functional response and predictor matrix using random linear transformation.
result Fully model-based Bayesian inference on compressed data.
A new data-oblivious sketch for logistic regression reduces data size while maintaining approximation accuracy.
problem Efficiently solving logistic regression in one pass over a data stream.
method Data-oblivious sketching approach that reduces data size to poly(μdlog n) weighted points.
result Sketching reduces data size significantly and provides approximation guarantees.
Given a matrix A ∈ R n × d A\in \mathbb{R}^{n\times d} A ∈ R n × d and a vector b ∈ R n b\in \mathbb{R}^n b ∈ R n , we consider the regression problem with ℓ ∞ \ell_\infty ℓ ∞ guarantees: finding a vector x ′ ∈ R d x'\in \mathbb{R}^d x ′ ∈ R d such that ∥ x ′ − x ∗ ∥ ∞ ≤ ε d ⋅ ∥ A x ∗ − b ∥ 2 ⋅ ∥ A † ∥ \|x'-x^*\|_\infty \leq \fracε{\sqrt{d}}\cdot \|Ax^*-b\|_2\cdot \|A^\dagger\| ∥ x ′ − x ∗ ∥ ∞ ≤ d ε ⋅ ∥ A x ∗ − b ∥ 2 ⋅ ∥ A † ∥ where $x^*=\arg\min_{x\in \mathbb{R}^d}\|Ax-b\|…
New method for efficient maximum likelihood estimation of p p p -generalized probit regression.
problem Efficient estimation of p p p -generalized probit regression models. method Combining sketching techniques with importance subsampling to obtain a coreset.
result Maximum likelihood estimator can be approximated efficiently up to a factor of ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) on large data. Matrix sketching balances class sizes for better supervised classification performance.
problem Class imbalance in supervised classification leads to poor performance.
method Matrix sketching using random projections to rebalance class sizes.
result Rebalanced classes improve classification performance, especially for minority classes.
In this paper, we revisit the large-scale constrained linear regression problem and propose faster methods based on some recent developments in sketching and optimization. Our algorithms combine (accelerated) mini-batch SGD with a new method called two-step preconditioning to achieve an approximate solution with a time…
We improve prediction risk estimation for large datasets using sketching and ridge regression.
problem Estimating prediction risks for large datasets efficiently and accurately.
method Random matrix theory, generalized cross validation, sketched ridge regression ensembles, and ensemble trick.
result Consistent risk estimation and prediction intervals for large-scale datasets.
We address the statistical and optimization impacts of the classical sketch and Hessian sketch used to approximately solve the Matrix Ridge Regression (MRR) problem. Prior research has quantified the effects of classical sketch on the strictly simpler least squares regression (LSR) problem. We establish that classical …
Improved ridge regression with Frequent Directions for large-scale tasks.
problem Improving performance of ridge regression for large-scale data.
method Combines Frequent Directions with iterative optimization schemes.
result Achieves high accuracy in estimating bias and variance for sketched ridge regression.
New algorithm speeds up regression tasks for large datasets.
problem Efficiently solving optimization and regression tasks with large datasets.
method Iterative Hessian Sketching (IHS) combined with matrix sketching techniques.
result Significantly faster algorithms for constrained regression tasks.
New method reduces linear regret in high-dimensional bandit problems.
problem Heavy spectral tails in streaming matrices lead to linear regret in sketch-based linear bandits.
method Dyadic Block Sketching, a multi-scale matrix sketching approach.
result Achieves sublinear regret bounds without prior knowledge of streaming matrix properties.
The paper shows how sketching data can simplify regression inference even when errors are heteroskedastic.
problem Performing robust inference with heteroskedastic errors using sketched data.
method Using random projections to sketch data, the paper shows that sketched estimates behave as if errors are homoskedastic.
result Estimation by random sampling does not have the same property, and sketched estimates are asymptotically normal with homoskedastic variance.
STORM enables edge computing for empirical risk minimization.
problem Training models on edge devices for streaming data.
method Online sketching for empirical risk minimization.
result STORM can estimate least-squares objective accurately.
TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was shown in Avron, Nguyen, Woodruff'14 that TensorSketch provides a subspace embedding, and therefore can be used for canonical correlation analysis, low rank approximation…
New methods for sketching non-PSD matrices improve regression and optimization tasks.
problem Efficiently handling non-PSD matrices in computations.
method Developed novel matrix sketching techniques for non-PSD and complex matrices.
result Improved performance in convex and non-convex optimization, regression, and vector-matrix-vector queries.
There is an especially strong need in modern large-scale data analysis to prioritize samples for manual inspection. For example, the inspection could target important mislabeled samples or key vulnerabilities exploitable by an adversarial attack. In order to solve the "needle in the haystack" problem of which samples t…
Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given n n n samples, the time and space complexity of computing the KRR estimate scale as O ( n 3 ) \mathcal{O}(n^3) O ( n 3 ) and O ( n 2 ) \mathcal{O}(n^2) O ( n 2 ) respectively, and so is prohibitive in many cases. We prop…
A new method for estimating large-scale linear models with improved precision.
problem Estimating large-scale linear statistical models efficiently.
method Sequential Least-Squares Estimators with Fast Randomized Sketching (SLSE-FRS), integrating Sketch-and-Solve and Iterative-Sketching methods.
result SLSE-FRS produces high-precision estimators, outperforming state-of-the-art methods.
Ridge leverage scores provide a balance between low-rank approximation and regularization, and are ubiquitous in randomized linear algebra and machine learning. Deterministic algorithms are also of interest in the moderately big data regime, because deterministic algorithms provide interpretability to the practitioner …
New algorithm reduces rank constrained optimization problems.
problem Rank constrained optimization problems in machine learning and statistics.
method Recursive Importance Sketching (RISRO) algorithm.
result RISRO offers clear advantages over existing algorithms and converges efficiently.
Generative model improves zero-shot sketch-based image retrieval.
problem Existing SBIR methods struggle with novel classes.
method Generative model learns to generate images conditioned on novel sketches.
result Significantly outperforms baselines on two challenging datasets.
We investigate regularized algorithms combining with projection for least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space. We prove convergence results with respect to variants of norms, under a capacity assumption on the hypothesis space and a …
We introduce a new sub-linear space sketch---the Weight-Median Sketch---for learning compressed linear classifiers over data streams while supporting the efficient recovery of large-magnitude weights in the model. This enables memory-limited execution of several statistical analyses over streams, including online featu…
We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, wi…
This paper speeds up kernel methods using sparsified Gaussian sketches.
problem Kernel methods' computational limitations.
method Sparsified Gaussian sketches for kernel methods.
result Efficient time and space savings for kernel methods.
Deterministic algorithm estimates ridge regression with minimal space.
problem Estimating ridge regression solutions efficiently.
method Deterministic space-efficient algorithm using Frequent Directions.
result First o ( d 2 ) o(d^2) o ( d 2 ) space deterministic streaming algorithm with guaranteed error. The paper sharpens the analysis of sketch-and-project methods using randomized singular value decomposition.
problem Improving convergence rates of sketch-and-project methods for solving linear systems and non-linear optimization problems.
method Developing a theoretical framework and new spectral bounds for the expected sketched projection matrix.
result The convergence rate improves linearly with sketch size and even faster with certain spectral decays.
New method solves constrained optimization problems efficiently.
problem Equality-constrained nonlinear, nonconvex optimization problems.
method Adaptive inexact Newton method with randomized iterative sketching.
result Global almost sure convergence and local linear/superlinear convergence.
New analysis proves sketching operators' RIP guarantees for mixture models without importance sampling.
problem Proving sketching operators' Restricted Isometry Property (RIP) for mixture models without assuming importance sampling.
method Proposed alternative analysis based on new deterministic bounds and concentration inequalities.
result Theoretical guarantees for sketching operators without importance sampling.
New method improves Gaussian kernel approximations for high-frequency data.
problem Limited scalability of kernel-based models to large data sets.
method Local random feature approximations using Maclaurin expansions and polynomial sketches.
result Significant improvement in kernel approximations and downstream performance for high-frequency data.
Sketching reduces data size for accurate spectral estimation.
problem Estimating spectral density from large simulation datasets.
method Sketching for dimensionality reduction and data compression.
result Sketching provides 90% accurate spectral density estimate with 10% data.
Randomized algorithm solves vector-valued regression problems with low-rank operators.
problem Vector-valued regression problems involving infinite-dimensional spaces.
method Randomized Reduced Rank Regression (R4) using Gaussian sketching for optimization.
result R4 estimators are efficient and accurate, with empirical risk close to optimal.
A fast algorithm for generalized matrix regression improves machine learning performance.
problem Efficiently solving generalized matrix regression problems in machine learning.
method Utilizes sketching technique to achieve ( 1 + ε ) (1+ε) ( 1 + ε ) relative error with sketching sizes of order $\cO(ε^{-1/2})$ . result The Fast GMR algorithm achieves better performance in symmetric positive definite matrix approximation and single pass singular value decomposition.
In this paper, we propose a general framework for sparse and low-rank tensor estimation from cubic sketchings. A two-stage non-convex implementation is developed based on sparse tensor decomposition and thresholded gradient descent, which ensures exact recovery in the noiseless case and stable recovery in the noisy cas…
Sketch-GNN reduces GNN training time and memory usage to sublinear scales.
problem Training GNNs on large graphs is computationally expensive and memory-intensive.
method Develops a sketch-based algorithm that trains GNNs on compact sketches of graph adjacency and node embeddings.
result Training time and memory usage grow sublinearly with respect to graph size.
Two bandit algorithms become efficient with sketching.
problem Efficiently processing large-scale linear bandit problems.
method Deterministic online sketching technique (Frequent Directions) to reduce update time.
result Regret bounds matching non-sketched versions when contexts span a subspace of dimension at most m.
A new method improves convergence in low-rank approximation.
problem Efficiently solving large-scale numerical linear algebra problems.
method Error-Powered Sketched Inverse Iteration (EPSI) Method.
result Convergence rate improves at least linearly with sketch size.