Sparse Quadratic Logistic Regression in Sub-quadratic Time
We consider support recovery in the quadratic logistic regression setting - where the target depends on both p linear terms $x_i$ and up to $p^2$ quadratic terms $x_i x_j$. Quadratic terms enable prediction/modeling of higher-order effects between features and the target, but when incorporated naively may involve solving a very large regression problem. We consider the sparse case, where at most $s$ terms (linear or quadratic) are non-zero, and provide a new faster algorithm. It involves (a) identifying the weak support (i.e. all relevant variables) and (b) standard logistic regression optimization only on these chosen variables. The first step relies on a novel insight about correlation tests in the presence of non-linearity, and takes $O(pn)$ time for $n$ samples - giving potentially huge computational gains over the naive approach. Motivated by insights from the boolean case, we propose a non-linear correlation test for non-binary finite support case that involves hashing a variable and then correlating with the output variable. We also provide experimental results to demonstrate the effectiveness of our methods.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Multinomial Logistic Regression Algorithms via Quadratic Gradient
Multinomial logistic regression, also known by other names such as multiclass logistic regression and softmax regression, is a fundamental classification method that generalizes binary logistic regression to multiclass p…
regressionQuantum Algorithm for Sparse Online Learning with Truncated Gradient Descent
Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on …
regressionPrivacy-Preserving Logistic Regression Training with A Faster Gradient Variant
Training logistic regression over encrypted data has been a compelling approach in addressing security concerns for several years. In this paper, we introduce an efficient gradient variant, called $quadratic$ $gradient$,…
Privacy PreservingregressionInteraction Hard Thresholding: Consistent Sparse Quadratic Regression in Sub-quadratic Time and Space
Quadratic regression involves modeling the response as a (generalized) linear function of not only the features $x^{j_1}$ but also of quadratic terms $x^{j_1}x^{j_2}$. The inclusion of such higher-order "interaction term…
regressionFast Sparse Classification for Generalized Linear and Additive Models
We present fast classification techniques for sparse generalized linear and additive models. These techniques can handle thousands of features and thousands of observations in minutes, even in the presence of many highly…
Additive modelsClassification