Petros Drineas

ICML Conference 2025 Conference Paper

Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization

• Xinyu Luo
• Site Bai
• Bolian Li
• Petros Drineas
• Ruqi Zhang
• Brian Bullins

While popular optimization methods such as SGD, AdamW, and Lion depend on steepest descent updates in either $\ell_2$ or $\ell_\infty$ norms, there remains a critical gap in handling the non-Euclidean structure observed in modern deep networks training. In this work, we address this need by introducing a new accelerated $\ell_p$ steepest descent algorithm, called Stacey, which uses interpolated primal-dual iterate sequences to effectively navigate non-Euclidean smooth optimization tasks. In addition to providing novel theoretical guarantees for the foundations of our algorithm, we empirically compare our approach against these popular methods on tasks including image classification and language model (LLM) pretraining, demonstrating both faster convergence and higher final accuracy. We further evaluate different values of $p$ across various models and datasets, underscoring the importance and efficiency of non-Euclidean approaches over standard Euclidean methods. Code can be found at https: //github. com/xinyuluo8561/Stacey.

NeurIPS Conference 2025 Conference Paper

Structure-Aware Spectral Sparsification via Uniform Edge Sampling

• Kaiwen He
• Petros Drineas
• Rajiv Khanna

Spectral clustering is a fundamental method for graph partitioning, but its reliance on eigenvector computation limits scalability to massive graphs. Classical sparsification methods preserve spectral properties by sampling edges proportionally to their effective resistances, but require expensive preprocessing to estimate these resistances. We study whether uniform edge sampling—a simple, structure-agnostic strategy—can suffice for spectral clustering. Our main result shows that for graphs admitting a well-separated $k$-clustering, characterized by a large structure ratio $\Upsilon(k) = \lambda_{k+1} / \rho_G(k)$, uniform sampling preserves the spectral subspace used for clustering. Specifically, we prove that uniformly sampling $O(\gamma^2 n \log n / \varepsilon^2)$ edges, where $\gamma$ is the Laplacian condition number, yields a sparsifier whose top $(n-k)$-dimensional eigenspace is approximately orthogonal to the cluster indicators. This ensures that the spectral embedding remains faithful, and clustering quality is preserved. Our analysis introduces new resistance bounds for intra-cluster edges, a rank-$(n-k)$ effective resistance formulation, and a matrix Chernoff bound adapted to the dominant eigenspace. These tools allow us to bypass importance sampling entirely. Conceptually, our result connects recent coreset-based clustering theory to spectral sparsification, showing that under strong clusterability, even uniform sampling is structure-aware. This provides the first provable guarantee that uniform edge sampling suffices for structure-preserving spectral clustering.

NeurIPS Conference 2024 Conference Paper

The Space Complexity of Approximating Logistic Loss

• Gregory Dexter
• Petros Drineas
• Rajiv Khanna

We provide space complexity lower bounds for data structures that approximate logistic loss up to $\epsilon$-relative error on a logistic regression problem with data $\mathbf{X} \in \mathbb{R}^{n \times d}$ and labels $\mathbf{y} \in \\{-1, 1\\}^d$. The space complexity of existing coreset constructions depend on a natural complexity measure $\mu_\mathbf{y}(\mathbf{X})$. We give an $\tilde{\Omega}(\frac{d}{\epsilon^2})$ space complexity lower bound in the regime $\mu_\mathbf{y}(\mathbf{X}) = \mathcal{O}(1)$ that shows existing coresets are optimal in this regime up to lower order factors. We also prove a general $\tilde{\Omega}(d\cdot \mu_\mathbf{y}(\mathbf{X}))$ space lower bound when $\epsilon$ is constant, showing that the dependency on $\mu_\mathbf{y}(\mathbf{X})$ is not an artifact of mergeable coresets. Finally, we refute a prior conjecture that $\mu_\mathbf{y}(\mathbf{X})$ is hard to compute by providing an efficient linear programming formulation, and we empirically compare our algorithm to prior approximate methods.

YNIMG Journal 2023 Journal Article

Multiomic approach and Mendelian randomization analysis identify causal associations between blood biomarkers and subcortical brain structure volumes

• Pritesh R Jain
• Madison Yates
• Carlos Rubin de Celis
• Petros Drineas
• Neda Jahanshad
• Paul Thompson
• Peristera Paschou

Alterations in subcortical brain structure volumes have been found to be associated with several neurodegenerative and psychiatric disorders. At the same time, genome-wide association studies (GWAS) have identified numerous common variants associated with brain structure. In this study, we integrate these findings, aiming to identify proteins, metabolites, or microbes that have a putative causal association with subcortical brain structure volumes via a two-sample Mendelian randomization approach. This method uses genetic variants as instrument variables to identify potentially causal associations between an exposure and an outcome. The exposure data that we analyzed comprised genetic associations for 2994 plasma proteins, 237 metabolites, and 103 microbial genera. The outcome data included GWAS data for seven subcortical brain structure volumes including accumbens, amygdala, caudate, hippocampus, pallidum, putamen, and thalamus. Eleven proteins and six metabolites were found to have a significant association with subcortical structure volumes, with nine proteins and five metabolites replicated using independent exposure data. We found causal associations between accumbens volume and plasma protease c1 inhibitor as well as strong association between putamen volume and Agouti signaling protein. Among metabolites, urate had the strongest association with thalamic volume. No significant associations were detected between the microbial genera and subcortical brain structure volumes. We also observed significant enrichment for biological processes such as proteolysis, regulation of the endoplasmic reticulum apoptotic signaling pathway, and negative regulation of DNA binding. Our findings provide insights to the mechanisms through which brain volumes may be affected in the pathogenesis of neurodevelopmental and psychiatric disorders and point to potential treatment targets for disorders that are associated with subcortical brain structure volumes.

NeurIPS Conference 2023 Conference Paper

Refined Mechanism Design for Approximately Structured Priors via Active Regression

• Christos Boutsikas
• Petros Drineas
• Marios Mertzanidis
• Alexandros Psomas
• Paritosh Verma

We consider the problem of a revenue-maximizing seller with a large number of items $m$ for sale to $n$ strategic bidders, whose valuations are drawn independently from high-dimensional, unknown prior distributions. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute, and, even when they can be found, are often rife with various counter-intuitive properties. In this paper, following a model introduced recently by Cai and Daskalakis [CD22], we consider the case that bidders' prior distributions can be well-approximated by a topic model. We design an active learning component, responsible for interacting with the bidders and outputting low-dimensional approximations of their types, and a mechanism design component, responsible for robustifying mechanisms for the low-dimensional model to work for the approximate types of the former component. On the active learning front, we cast our problem in the framework of Randomized Linear Algebra (RLA) for regression problems, allowing us to import several breakthrough results from that line of research, and adapt them to our setting. On the mechanism design front, we remove many restrictive assumptions of prior work on the type of access needed to the underlying distributions and the associated mechanisms. To the best of our knowledge, our work is the first to formulate connections between mechanism design, and RLA for active learning of regression problems, opening the door for further applications of randomized linear algebra primitives to mechanism design.

NeurIPS Conference 2023 Conference Paper

Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming

• Gregory Dexter
• Petros Drineas
• David Woodruff
• Taisuke Yasuda

Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS). In this work, we develop new techniques to extend the applicability of sketching-based approaches to the sparse dictionary learning and the Euclidean $k$-means clustering problems. In particular, we initiate the study of the challenging setting where the dictionary/clustering assignment for each of the $n$ input points must be output, which has surprisingly received little attention in prior work. On the fast algorithms front, we obtain a new approach for designing PTAS's for the $k$-means clustering problem, which generalizes to the first PTAS for the sparse dictionary learning problem. On the streaming algorithms front, we obtain new upper bounds and lower bounds for dictionary learning and $k$-means clustering. In particular, given a design matrix $\mathbf A\in\mathbb R^{n\times d}$ in a turnstile stream, we show an $\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde O(n/\epsilon^2 + dk/\epsilon)$ space upper bound for $k$-means clustering, as well as an $\tilde O(n)$ space upper bound for $k$-means clustering on random order row insertion streams with a natural "bounded sensitivity" assumption. On the lower bounds side, we obtain a general $\tilde\Omega(n/\epsilon + dk/\epsilon)$ lower bound for $k$-means clustering, as well as an $\tilde\Omega(n/\epsilon^2)$ lower bound for algorithms which can estimate the cost of a single fixed set of candidate centers.

JMLR Journal 2022 Journal Article

Faster Randomized Interior Point Methods for Tall/Wide Linear Programs

• Agniva Chowdhury
• Gregory Dexter
• Palma London
• Haim Avron
• Petros Drineas

Linear programming (LP) is an extremely useful tool which has been successfully applied to solve various problems in a wide range of areas, including operations research, engineering, economics, or even more abstract mathematical areas such as combinatorics. It is also used in many machine learning applications, such as $\ell_1$-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior Point Methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider both feasible and infeasible IPMs for the special case where the number of variables is much larger than the number of constraints. Using tools from Randomized Linear Algebra, we present a preconditioning technique that, when combined with the iterative solvers such as Conjugate Gradient or Chebyshev Iteration, provably guarantees that IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real-world and synthetic data. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

ICML Conference 2022 Conference Paper

On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming

• Gregory Dexter
• Agniva Chowdhury
• Haim Avron
• Petros Drineas

Interior point methods (IPMs) are a common approach for solving linear programs (LPs) with strong theoretical guarantees and solid empirical performance. The time complexity of these methods is dominated by the cost of solving a linear system of equations at each iteration. In common applications of linear programming, particularly in machine learning and scientific computing, the size of this linear system can become prohibitively large, requiring the use of iterative solvers, which provide an approximate solution to the linear system. However, approximately solving the linear system at each iteration of an IPM invalidates the theoretical guarantees of common IPM analyses. To remedy this, we theoretically and empirically analyze (slightly modified) predictor-corrector IPMs when using approximate linear solvers: our approach guarantees that, when certain conditions are satisfied, the number of IPM iterations does not increase and that the final solution remains feasible. We also provide practical instantiations of approximate linear solvers that satisfy these conditions for special classes of constraint matrices using randomized linear algebra.

NeurIPS Conference 2020 Conference Paper

Faster Randomized Infeasible Interior Point Methods for Tall/Wide Linear Programs

• Agniva Chowdhury
• Palma London
• Haim Avron
• Petros Drineas

Linear programming (LP) is used in many machine learning applications, such as $\ell_1$-regularized SVMs, basis pursuit, nonnegative matrix factorization, etc. Interior Point Methods (IPMs) are one of the most popular methods to solve LPs both in theory and in practice. Their underlying complexity is dominated by the cost of solving a system of linear equations at each iteration. In this paper, we consider \emph{infeasible} IPMs for the special case where the number of variables is much larger than the number of constraints (i. e. , wide), or vice-versa (i. e. , tall) by taking the dual. Using tools from Randomized Linear Algebra, we present a preconditioning technique that, when combined with the Conjugate Gradient iterative solver, provably guarantees that infeasible IPM algorithms (suitably modified to account for the error incurred by the approximate solver), converge to a feasible, approximately optimal solution, without increasing their iteration complexity. Our empirical evaluations verify our theoretical results on both real and synthetic data.

FOCS Conference 2020 Conference Paper

Near Optimal Linear Algebra in the Online and Sliding Window Models

• Vladimir Braverman
• Petros Drineas
• Cameron Musco
• Christopher Musco
• Jalaj Upadhyay
• David P. Woodruff
• Samson Zhou

We initiate the study of numerical linear algebra in the sliding window model, where only the most recent W updates in a stream form the underlying data set. Although many existing algorithms in the sliding window model use or borrow elements from the smooth histogram framework (Braverman and Ostrovsky, FOCS 2007), we show that many interesting linear-algebraic problems, including spectral and vector induced matrix norms, generalized regression, and low-rank approximation, are not amenable to this approach in the row-arrival model. To overcome this challenge, we first introduce a unified row-sampling based framework that gives randomized algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and ℓ 1 -subspace embeddings in the sliding window model, which often use nearly optimal space and achieve nearly input sparsity runtime. Our algorithms are based on “reverse online” versions of offline sampling distributions such as (ridge) leverage scores, ℓ 1 sensitivities, and Lewis weights to quantify both the importance and the recency of a row; our structural results on these distributions may be of independent interest for future algorithmic design. Although our techniques initially address numerical linear algebra in the sliding window model, our row-sampling framework rather surprisingly implies connections to the well-studied online model; our structural results also give the first sample optimal (up to lower order terms) online algorithm for low-rank approximation/projection-cost preservation. Using this powerful primitive, we give online algorithms for column/row subset selection and principal component analysis that resolves the main open question of Bhaskara et al. (FOCS 2019). We also give the first online algorithm for ℓ 1 -subspace embeddings. We further formalize the connection between the online model and the sliding window model by introducing an additional unified framework for deterministic algorithms using a merge and reduce paradigm and the concept of online coresets, which we define as a weighted subset of rows of the input matrix that can be used to compute a good approximation to some given function on all of its prefixes. Our sampling based algorithms in the row-arrival online model yield online coresets, giving deterministic algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and ℓ 1 - subspace embeddings in the sliding window model that use nearly optimal space.

UAI Conference 2019 Conference Paper

Randomized Iterative Algorithms for Fisher Discriminant Analysis

• Agniva Chowdhury
• Jiasen Yang
• Petros Drineas

Fisher discriminant analysis (FDA) is a widely used method for classification and dimensionality reduction. When the number of predictor variables greatly exceeds the number of observations, one of the alternatives for conventional FDA is regularized Fisher discriminant analysis (RFDA). In this paper, we present a simple, iterative, sketching-based algorithm for RFDA that comes with provable accuracy guarantees when compared to the conventional approach. Our analysis builds upon two simple structural results that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized linear algebra. We analyze the behavior of RFDA when leverage scores and ridge leverage scores are used to select predictor variables, and prove that accurate approximations can be achieved by a sample whose size depends on the effective degrees of freedom of the RFDA problem. Our results yield significant improvements over existing approaches and our empirical evaluations support our theoretical analyses.

ICML Conference 2018 Conference Paper

An Iterative, Sketching-based Framework for Ridge Regression

• Agniva Chowdhury
• Jiasen Yang
• Petros Drineas

Ridge regression is a variant of regularized least squares regression that is particularly suitable in settings where the number of predictor variables greatly exceeds the number of observations. We present a simple, iterative, sketching-based algorithm for ridge regression that guarantees high-quality approximations to the optimal solution vector. Our analysis builds upon two simple structural results that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized linear algebra. An important contribution of our work is the analysis of the behavior of subsampled ridge regression problems when the ridge leverage scores are used: we prove that accurate approximations can be achieved by a sample whose size depends on the degrees of freedom of the ridge-regression problem rather than the dimensions of the design matrix. Our experimental evaluations verify our theoretical results on both real and synthetic data.

JMLR Journal 2017 Journal Article

Recovering PCA and Sparse PCA via Hybrid-(l1,l2) Sparse Sampling of Data Elements

• Abhisek Kundu
• Petros Drineas
• Malik Magdon-Ismail

This paper addresses how well we can recover a data matrix when only given a few of its elements. We present a randomized algorithm that element-wise sparsifies the data, retaining only a few of its entries. Our new algorithm independently samples the data using probabilities that depend on both squares ($\ell_2$ sampling) and absolute values ($\ell_1$ sampling) of the entries. We prove that this hybrid algorithm ($i$) achieves a near-PCA reconstruction of the data, and ($ii$) recovers sparse principal components of the data, from a sketch formed by a sublinear sample size. Hybrid-($\ell_1,\ell_2$) inherits the $\ell_2$-ability to sample the important elements, as well as the regularization properties of $\ell_1$ sampling, and maintains strictly better quality than either $\ell_1$ or $\ell_2$ on their own. Extensive experimental results on synthetic, image, text, biological, and financial data show that not only are we able to recover PCA and sparse PCA from incomplete data, but we can speed up such computations significantly using our sparse sketch. [abs] [ pdf ][ bib ] &copy JMLR 2017. ( edit, beta )

NeurIPS Conference 2015 Conference Paper

Approximating Sparse PCA from Incomplete Data

• Abhisek Kundu
• Petros Drineas
• Malik Magdon-Ismail

We study how well one can recover sparse principal componentsof a data matrix using a sketch formed from a few of its elements. We show that for a wide class of optimization problems, if the sketch is close (in the spectral norm) to the original datamatrix, then one can recover a near optimal solution to the optimizationproblem by using the sketch. In particular, we use this approach toobtain sparse principal components and show that for \math{m} data pointsin \math{n} dimensions, \math{O(\epsilon^{-2}\tilde k\max{m, n})} elements gives an\math{\epsilon}-additive approximation to the sparse PCA problem(\math{\tilde k} is the stable rank of the data matrix). We demonstrate our algorithms extensivelyon image, text, biological and financial data. The results show that not only are we able to recover the sparse PCAs from the incomplete data, but by using our sparse sketch, the running timedrops by a factor of five or more.

NeurIPS Conference 2015 Conference Paper

Column Selection via Adaptive Sampling

• Saurabh Paul
• Malik Magdon-Ismail
• Petros Drineas

Selecting a good column (or row) subset of massive data matrices has found many applications in data analysis and machine learning. We propose a new adaptive sampling algorithm that can be used to improve any relative-error column selection algorithm. Our algorithm delivers a tighter theoretical bound on the approximation error which we also demonstrate empirically using two well known relative-error column subset selection algorithms. Our experimental results on synthetic and real-world data show that our algorithm outperforms non-adaptive sampling as well as prior adaptive sampling approaches.

SODA Conference 2013 Conference Paper

The Fast Cauchy Transform and Faster Robust Linear Regression

• Kenneth L. Clarkson
• Petros Drineas
• Malik Magdon-Ismail
• Michael W. Mahoney
• Xiangrui Meng
• David P. Woodruff

We provide fast algorithms for overconstrained ℓ p regression and related problems: for an n × d input matrix A and vector b ∊ ℝ n, in O ( nd log n ) time we reduce the problem min x ∊ ℝ d ‖ A x − b ‖ p to the same problem with input matrix A of dimension s × d and corresponding b of dimension s × 1. Here, Ã and are a coreset for the problem, consisting of sampled and rescaled rows of A and b; and s is independent of n and polynomial in d. Our results improve on the best previous algorithms when n ≫ d, for all p ∊ [1, ∞) except p = 2; in particular, they improve the O ( nd 1. 376+ ) running time of Sohler and Woodruff (STOC, 2011) for p = 1, that uses asymptotically fast matrix multiplication, and the O ( nd 5 log n ) time of Dasgupta et al. (SICOMP, 2009) for general p, that uses ellipsoidal rounding. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general ℓ p problems. To complement this theory, we provide a detailed empirical evaluation of implementations of our algorithms for p = 1, comparing them with several related algorithms. Among other things, our empirical results clearly show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for ℓ p spaces and, for p = 1, a fast subspace embedding of independent interest that we call the Fast Cauchy Transform: a matrix Π: ℝ n → ℝ O ( d log d ), found obliviously to A, that approximately preserves the ℓ 1 norms: that is, ‖ Ax ‖ 1 ≈ ‖Π A x ‖ 1, for all x, with distortion O ( d 2 + η log d ), for an arbitrarily small constant η > 0; and, moreover, ΠA can be computed in O ( nd log d ) time. The techniques underlying our Fast Cauchy Transform include fast Johnson-Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.

ICML Conference 2012 Conference Paper

Fast approximation of matrix coherence and statistical leverage

• Michael W. Mahoney
• Petros Drineas
• Malik Magdon-Ismail
• David P. Woodruff

JMLR Journal 2012 Journal Article

Fast Approximation of Matrix Coherence and Statistical Leverage

• Petros Drineas
• Malik Magdon-Ismail
• Michael W. Mahoney
• David P. Woodruff

The statistical leverage scores of a matrix A are the squared row-norms of the matrix containing its (top) left singular vectors and the coherence is the largest leverage score. These quantities are of interest in recently-popular problems such as matrix completion and Nyström-based low-rank matrix approximation as well as in large-scale statistical data analysis applications more generally; moreover, they are of interest since they define the key structural nonuniformity that must be dealt with in developing fast randomized matrix algorithms. Our main result is a randomized algorithm that takes as input an arbitrary n × d matrix A, with n >> d, and that returns as output relative-error approximations to all n of the statistical leverage scores. The proposed algorithm runs (under assumptions on the precise values of n and d ) in O(n d log n) time, as opposed to the O(nd 2 ) time required by the naïve algorithm that involves computing an orthogonal basis for the range of A. Our analysis may be viewed in terms of computing a relative-error approximation to an under constrained least-squares approximation problem, or, relatedly, it may be viewed as an application of Johnson-Lindenstrauss type ideas. Several practically-important extensions of our basic result are also described, including the approximation of so-called cross-leverage scores, the extension of these ideas to matrices with n ≈ d, and the extension to streaming environments. [abs] [ pdf ][ bib ] &copy JMLR 2012. ( edit, beta )

FOCS Conference 2011 Conference Paper

Near Optimal Column-Based Matrix Reconstruction

• Christos Boutsidis
• Petros Drineas
• Malik Magdon-Ismail

We consider low-rank reconstruction of a matrix using a subset of its columns and we present asymptotically optimal algorithms for both spectral norm and Frobenius norm reconstruction. The main tools we introduce to obtain our results are: (i) the use of fast approximate SVD-like decompositions for column-based matrix reconstruction, and (ii) two deterministic algorithms for selecting rows from matrices with orthonormal columns, building upon the sparse representation theorem for decompositions of the identity that appeared in [1].

NeurIPS Conference 2011 Conference Paper

Sparse Features for PCA-Like Linear Regression

• Christos Boutsidis
• Petros Drineas
• Malik Magdon-Ismail

Principal Components Analysis~(PCA) is often used as a feature extraction procedure. Given a matrix $X \in \mathbb{R}^{n \times d}$, whose rows represent $n$ data points with respect to $d$ features, the top $k$ right singular vectors of $X$ (the so-called \textit{eigenfeatures}), are arbitrary linear combinations of all available features. The eigenfeatures are very useful in data analysis, including the regularization of linear regression. Enforcing sparsity on the eigenfeatures, i. e. , forcing them to be linear combinations of only a \textit{small} number of actual features (as opposed to all available features), can promote better generalization error and improve the interpretability of the eigenfeatures. We present deterministic and randomized algorithms that construct such sparse eigenfeatures while \emph{provably} achieving in-sample performance comparable to regularized linear regression. Our algorithms are relatively simple and practically efficient, and we demonstrate their performance on several data sets.

NeurIPS Conference 2010 Conference Paper

Random Projections for $k$-means Clustering

• Christos Boutsidis
• Anastasios Zouzias
• Petros Drineas

This paper discusses the topic of dimensionality reduction for $k$-means clustering. We prove that any set of $n$ points in $d$ dimensions (rows in a matrix $A \in \RR^{n \times d}$) can be projected into $t = \Omega(k / \eps^2)$ dimensions, for any $\eps \in (0, 1/3)$, in $O(n d \lceil \eps^{-2} k/ \log(d) \rceil )$ time, such that with constant probability the optimal $k$-partition of the point set is preserved within a factor of $2+\eps$. The projection is done by post-multiplying $A$ with a $d \times t$ random matrix $R$ having entries $+1/\sqrt{t}$ or $-1/\sqrt{t}$ with equal probability. A numerical implementation of our technique and experiments on a large face images dataset verify the speed and the accuracy of our theoretical results.

SODA Conference 2009 Conference Paper

An improved approximation algorithm for the column subset selection problem

• Christos Boutsidis
• Michael W. Mahoney
• Petros Drineas

We consider the problem of selecting the “best” subset of exactly k columns from an m × n matrix A. In particular, we present and analyze a novel two-stage algorithm that runs in O (min{ mn 2, m 2 n }) time and returns as output an m × k matrix C consisting of exactly k columns of A. In the first stage (the randomized stage), the algorithm randomly selects O ( k log k ) columns according to a judiciously-chosen probability distribution that depends on information in the top- k right singular subspace of A. In the second stage (the deterministic stage), the algorithm applies a deterministic column-selection procedure to select and return exactly k columns from the set of columns selected in the first stage. Let C be the m × k matrix containing those k columns, let P C denote the projection matrix onto the span of those columns, and let A k denote the “best” rank- k approximation to the matrix A as computed with the singular value decomposition. Then, we prove that with probability at least 0. 7. This spectral norm bound improves upon the best previously-existing result (of Gu and Eisenstat [21]) for the spectral norm version of this Column ubset election Problem. We also prove that with the same probability. This Frobenius norm bound is only a factor of worse than the best previously existing existential result and is roughly better than the best previous algorithmic result (both of Deshpande et al. [11]) for the Frobenius norm version of this Column ubset election Problem.

NeurIPS Conference 2009 Conference Paper

Unsupervised Feature Selection for the $k$-means Clustering Problem

• Christos Boutsidis
• Petros Drineas
• Michael Mahoney

We present a novel feature selection algorithm for the $k$-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter $\epsilon \in (0, 1)$, selects and appropriately rescales in an unsupervised manner $\Theta(k \log(k / \epsilon) / \epsilon^2)$ features from a dataset of arbitrary dimensions. We prove that, if we run any $\gamma$-approximate $k$-means algorithm ($\gamma \geq 1$) on the features selected using our method, we can find a $(1+(1+\epsilon)\gamma)$-approximate partition with high probability.

SODA Conference 2008 Conference Paper

Sampling algorithms and coresets for ℓ p regression

• Anirban Dasgupta 0001
• Petros Drineas
• Boulos Harb
• Ravi Kumar 0001
• Michael W. Mahoney

SODA Conference 2006 Conference Paper

Sampling algorithms for l 2 regression and applications

• Petros Drineas
• Michael W. Mahoney
• S. Muthukrishnan 0001

JMLR Journal 2005 Journal Article

On the Nystrom Method for Approximating a Gram Matrix for Improved Kernel-Based Learning

• Petros Drineas
• Michael W. Mahoney

A problem for many kernel-based methods is that the amount of computation required to find the solution scales as O(n 3 ), where n is the number of training examples. We develop and analyze an algorithm to compute an easily-interpretable low-rank approximation to an n × n Gram matrix G such that computations of interest may be performed more rapidly. The approximation is of the form ~ G k = CW k + C T, where C is a matrix consisting of a small number c of columns of G and W k is the best rank- k approximation to W, the matrix formed by the intersection between those c columns of G and the corresponding c rows of G. An important aspect of the algorithm is the probability distribution used to randomly sample the columns; we will use a judiciously-chosen and data-dependent nonuniform probability distribution. Let ||·|| 2 and ||·|| F denote the spectral norm and the Frobenius norm, respectively, of a matrix, and let G k be the best rank- k approximation to G. We prove that by choosing O(k/ε 4 ) columns || G-CW k + C T || ξ ≤ || G-G k || ξ + ε Σ i=1 n G ii 2, both in expectation and with high probability, for both ξ = 2, F, and for all k: 0 ≤ k ≤ rank (W). This approximation can be computed using O(n) additional space and time, after making two passes over the data from external storage. The relationships between this algorithm, other related matrix decompositions, and the Nyström method from integral equation theory are discussed. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

SODA Conference 2003 Conference Paper

Pass efficient algorithms for approximating large matrices

• Petros Drineas
• Ravindran Kannan

STOC Conference 2002 Conference Paper

Competitive recommendation systems

• Petros Drineas
• Iordanis Kerenidis
• Prabhakar Raghavan

A recommendation system tracks past purchases of a group of users to make product recommendations to individual members of the group. In this paper we present a notion of competitive recommendation systems, building on recent theoretical work on this subject. We reduce the problem of achieving competitiveness to a problem in matrix reconstruction. We then present a matrix reconstruction scheme that is competitive: it requires a small overhead in the number of users and products to be sampled, delivering in the process a net utility that closely approximates the best possible with full knowledge of all user-product preferences.

FOCS Conference 2001 Conference Paper

Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication

• Petros Drineas
• Ravindran Kannan

Given an m x n matrix A and an n x p matrix B, we present 2 simple and intuitive algorithms to compute an approximation P to the pr oductA·B, with provable bounds for the norm of the err or matrix "P- A·B. Both algorithms run in O(mp+mn+np) time. In both algorithms, we randomly pick s = O(1) columns of A to form an m x s matrix S and the corresponding rows of B to form an s x p matrix R. After scaling the columns of S and the rows of R, we multiply them together to obtain our approximation P. The choice of the probability distribution we use for picking the columns of A and the scaling are the crucial features which enable us to give fairly elementary proofs of the error bounds. Our first algorithm can be implemented without storing the matrices A and B in Random Access Memory, provided we can make two passes through the matrices (stored in external memory). The second algorithm has a smaller bound on the 2-norm of the error matrix, but requires storage of A and B in RAM. We also present a fast algorithm that "describes" P as a sum of rank one matrices if B = A T.

SODA Conference 1999 Conference Paper

Clustering in Large Graphs and Matrices

• Petros Drineas
• Alan M. Frieze
• Ravindran Kannan
• Santosh S. Vempala
• V. Vinay