Efficient Strongly Polynomial Algorithms for Quantile Regression
- URL: http://arxiv.org/abs/2307.08706v1
- Date: Fri, 14 Jul 2023 03:07:42 GMT
- Title: Efficient Strongly Polynomial Algorithms for Quantile Regression
- Authors: Suraj Shetiya, Shohedul Hasan, Abolfazl Asudeh, and Gautam Das
- Abstract summary: We revisit the classical technique of Quantile Regression (QR)
This paper proposes several strongly efficient classical algorithms for QR for various settings.
For two dimensional QR, making a connection to the geometric concept of $k$-set, we propose an algorithm with a worst-case time complexity of $mathcalO(n4/3 polylog(n))$.
We also propose a randomized divide-and-conquer algorithm -- RandomizedQR with an expected time complexity of $mathcalO(nlog2(n))$ for two dimensional
- Score: 12.772027028644041
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear Regression is a seminal technique in statistics and machine learning,
where the objective is to build linear predictive models between a response
(i.e., dependent) variable and one or more predictor (i.e., independent)
variables. In this paper, we revisit the classical technique of Quantile
Regression (QR), which is statistically a more robust alternative to the other
classical technique of Ordinary Least Square Regression (OLS). However, while
there exist efficient algorithms for OLS, almost all of the known results for
QR are only weakly polynomial. Towards filling this gap, this paper proposes
several efficient strongly polynomial algorithms for QR for various settings.
For two dimensional QR, making a connection to the geometric concept of
$k$-set, we propose an algorithm with a deterministic worst-case time
complexity of $\mathcal{O}(n^{4/3} polylog(n))$ and an expected time complexity
of $\mathcal{O}(n^{4/3})$ for the randomized version. We also propose a
randomized divide-and-conquer algorithm -- RandomizedQR with an expected time
complexity of $\mathcal{O}(n\log^2{(n)})$ for two dimensional QR problem. For
the general case with more than two dimensions, our RandomizedQR algorithm has
an expected time complexity of $\mathcal{O}(n^{d-1}\log^2{(n)})$.
Related papers
- Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it.
In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
arXiv Detail & Related papers (2023-11-18T04:41:07Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Feature Adaptation for Sparse Linear Regression [20.923321050404827]
Sparse linear regression is a central problem in high-dimensional statistics.
We provide an algorithm that adapts to tolerate a small number of approximate dependencies.
Our framework fits into a broader framework of feature adaptation for sparse linear regression.
arXiv Detail & Related papers (2023-05-26T12:53:13Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
General tools for designing efficient private estimation algorithms.
First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
arXiv Detail & Related papers (2023-01-11T09:12:28Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
We develop an exact and scalable algorithm for one-dimensional Gaussian process regression with Mat'ern correlations.
The proposed algorithm is significantly superior to the existing alternatives in both the computational time and predictive accuracy.
arXiv Detail & Related papers (2022-03-07T03:30:35Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
We propose an iterative algorithm that provably computes a solution to a logistic regression problem regularized by an elastic net penalty.
This result improves on the known complexity bound of $O(min(m2n,mn2)log (1/epsilon))$ for first-order optimization methods.
arXiv Detail & Related papers (2021-11-30T14:16:48Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning.
The Gromov-Wasserstein (GW) formalism can help tackle this problem.
arXiv Detail & Related papers (2021-06-02T12:50:56Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret.
We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
arXiv Detail & Related papers (2020-11-19T10:00:54Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
We consider sparse regression from the view of correlation, and propose the formula of conditional uncorrelation.
By the proposed method, the computational complexity is reduced from $O(frac16k3+mk2+mkd)$ to $O(frac16k3+frac12mk2)$ for each candidate subset in sparse regression.
arXiv Detail & Related papers (2020-09-08T20:32:26Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
We describe a series of algorithms that efficiently implement Gaussian model-X knockoffs to control the false discovery rate on large scale feature selection problems.
We test our methods on problems with $p$ as large as $500,000$.
arXiv Detail & Related papers (2020-06-15T21:55:34Z) - Subgradient Regularized Multivariate Convex Regression at Scale [21.55988846648753]
We present new large-scale algorithms for fitting a subgradient regularized convex regression function to $n$ samples in $d$ dimensions.
We show that our framework can approximately solve instances of the subgradient regularized convex regression problem with $n=105$ and $d=10$ within minutes.
arXiv Detail & Related papers (2020-05-23T19:08:39Z)
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.