Questions tagged [time-complexity]

Computational complexity (aka time complexity) of an algorithm is the amount of time it needs to run as a function of the input size.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
123 views

What is the feasibility to run linear model for large amount of data?

I am looking for empirical approximations and guidelines on how many operations are required to run a linear model on a given amount of data, or if it's even feasible. Let's assume we use QR ...
3
votes
0answers
42 views

(Teaching) references for computational complexity

Background: I am going to teach computational complexity (time complexity) within an introductory course in machine learning. I would like to gently introduce the notion of computational complexity ...
3
votes
0answers
181 views

Why is matrix notation in linear regression best way to compute coefficients?

I would to find the parameters for $y_i=\beta_0+\beta_1x_{1i}+\beta_2x_{2i}$ using the least squares concept and want to prove that matrix notation is computationally more convenient than my way below ...
3
votes
0answers
342 views

How to determine time complexity of EM algorithm of probabilistic PCA?

I was studying probabilistic PCA from Bishop's book. There an EM algorithm is provided to calculate principal subspace: Here $\mathbf M$ is $M\times M$ matrix, $\mathbf W$ is $D\times M$ matrix and $...
3
votes
0answers
289 views

Which non-parametric multiple-regression methods are computationally efficient with respect to the number of regressors?

I did some regression in R with random forests and got some decent results, $1-\sum{|e_i|}/\sum{|y_i-\bar{y}|}=0.692$, but I want to do better than this. Through my research, I have concluded that the ...
2
votes
0answers
13 views

Reference Request: Ratio of Computational Complexity to Predictive Quality

I remember coming across a "performance metric" which was the ratio between the MSE and the computational time. However, I can't seem to recall the name of this metric or a reference. Does anyone ...
2
votes
0answers
32 views

"Wrong polarity" of SVM in Bottou & Lin (2006)

I am reading the paper "Support Vector Machine Solvers" by Bottou and Lin (2006). On page 10, the authors engage in a discussion about the asymptotic number of support vectors as a function of the ...
2
votes
0answers
41 views

Algorithmic Complexity of Estimators

I am interested in evaluating the algorithmic complexity of an estimator of the form: $$\hat{\theta} = \text{argmin}_{\theta} \;\; Q_n (\theta)$$ where $Q_n(\theta)$ denotes some objective function ...
2
votes
0answers
86 views

How is it computationally possible to calculate ANOVA of microarrays with interactions of 4000 genes and 7 times

M. Kerr and G. Churchill use ANOVA to separate changes in gene expressions from effects due to the used arrays or dye using the interaction terms time*gene As they are dealing with yeast which has ...
1
vote
0answers
40 views

Computational advantage for soft-impute method over other methods

I am reading in the soft-imputing paper for low-rank-based matrix completion. They suggested another solution for $$\hat{Z} = \text{argmin}_Z\lVert X - Z \rVert_F^2 + \lambda \lVert Z \rVert_*$$ ...
1
vote
0answers
57 views

A custom loss function which weights the loss depending on the age of data used

I was wondering if it is possible to weight the loss so that old data are evaluated less than new data. Lets say I have a product which has a trend in value spanning across decades, I want the model ...
1
vote
0answers
230 views

what are the main differences between parametric and non-parametric machine learning algorithms?

I am interested in parametric and non-parametric machine learning algorithms, their advantages and disadvantages and also their main differences regarding computational complexities. In particular I ...
1
vote
0answers
61 views

Fast marginalizations of a large Probability Mass Distribution

I will explain my problem through a simple example. Imagine that I am given a probability mass function over a system of 10 3-states discrete random variables ($V_1,V_2,...,V_{10}$). So, I have $3^{10}...
1
vote
0answers
40 views

sample complexity vs training cost (time complexity)

I have a question about the complexities. Consider two regression problems A, B and assume that A has lower sample complexity than B. A and B share the same target function but the loses are slightly ...
1
vote
2answers
23 views

Issues with training on a sample of training set?

I am training an SVM on highly imbalanced data. I have rectified this issue and my ML pipeline works just fine. I have allocated 70% of my dataset for training, however this takes an infeasible amount ...
1
vote
1answer
84 views

Complexity associated with decision trees

According to the sklearn documentation on decision trees: The cost of using the tree (i.e., predicting data) is logarithmic in the number of data points used to train the tree. Could somebody ...
1
vote
0answers
996 views

Time complexity of batch gradient descent

I am read http://papers.nips.cc/paper/4937-accelerating-stochastic-gradient-descent-using-predictive-variance-reduction.pdf paper. It states that "Due to the poor condition number, the standard batch ...
1
vote
0answers
207 views

Real using of the "Realized GARCH" for 1 minute forecast

I would like to ask someone who has an experience with the "Realized GARH" by Peter Hansen. I have 2 questions: Is there a logical purpose to use realGARCH for 1 minute forecast? How long could it ...
1
vote
0answers
223 views

What are the computational complexities of Linear One-vs-One, Bayesian Multivariate, and k-NN algorithms?

What are the computational complexities of Linear One-vs-One Committe, Bayesian multivariate with the class independence assumption, and k-NN algorithm with k=3? In $\mathcal{O}$ (Big-O) notation?...
0
votes
0answers
8 views

Handling densely observed functional data with R package fda in reasonable time

I am trying to use the fda package to analyze functional data that is densely observed; for example, for one function I have ~25,000 samples of that function. (To be more precise, I observe $f(t_i), 1 ...
0
votes
0answers
16 views

Expected value of log-likelihood and KL divergence

Background: Let $x_t = Ax_{t-1} + w_t$ be a discrete linear time invariant system where: $x_t \in \mathbb{R}^d$ for all time samples $t$ corresponds to the state vector $A\in \mathbb{R}^{d\times d}$ ...
0
votes
0answers
6 views

KPIs for complexity-accuracy trade-off

I am working with a deep learning based system where complexity has to be reduced to a minimal. However, this is having some impact on the accuracy. I am having to ask the question in somewhat ...
0
votes
0answers
7 views

Why do faster (eg sparse) versions of Transformers focus on the query-key product?

A lot of recent research on Transformers has been devoted to reducing the cost of the self-attention mechanism: $ softmax(\frac{Q K^T}{\sqrt{d}}) V $, As I understand it, the runtime, assuming $\{Q, K,...
0
votes
0answers
9 views

What does the order of the quantity $r^Tr$ have to do with the magnitude of this error?

Working through a section of paper https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2756108/ .(page 5 but question is pretty much self-contained) Setup: The error is given by $$e=-\frac{\alpha f(\Delta t)}...
0
votes
0answers
16 views

What is the order a randomized membership algorithm?

Suppose we have two sets $S$ and $I$, where $|S|=n$ and $|I|=0$. I use a randomized algorithm to add all of the members of $S$ to another set $I$. Each iteration of the algorithm has two steps. In the ...
0
votes
0answers
32 views

question about time complexity of split finding for Column Block in xgboost

I read the Xgboost paper and I have several questions in the 4.1 section Column Block for Parallel Learning 1.the third paragraph of which says The block structure also helps when using the ...
0
votes
0answers
7 views

Best (quality/time) undersampling technique

I am working on a very unbilanced dataset (90% to 10%) with around 350.000 records, and am trying various classification methods. I bagan with SMOTE, which was quite fast, improved performance on tree ...
0
votes
0answers
19 views

About the efficiency of MobileNet v1 architecture

The salient feature, which was said to make MobileNet v1 efficient in terms of computational complexity, is the usage of depthwise convolutions, which is in essence ...
0
votes
0answers
54 views

How calculate computational complexity (BigO) of ML techniques using Weka?

I'm trying to get the bigO notation from these algorithms: Alternating Model Tree, SMOreg, LSTM, Multilayer Perceptron, LeastMedSq, and M5Rules. Since BigO notations are represented as following ...
0
votes
0answers
70 views

Computational Complexity of SPADE, GSP and others

Does anybody know the computational complexity of SPADE, GSP, FreeSpan and PrefixSpan algorithm. I would like to have a comparisson in between these algorithms.
0
votes
0answers
35 views

A question on time complexity

Suppose I have a sequence of i.i.d. Bernoulli random variable $X_i$ with mean $0$ and variance $1$. For each $X_i$, it is $1$ w.p $1/2$ and $-1$ w.p $1/2$. My goal is to show $X_1+X_2+\cdots+X_n \...
0
votes
0answers
640 views

Time complexity of bagging and random forest

Most sources and books state that time complexity of a single decision tree for n points and d dimensions (features) is $O(d * n^2 * log(n))$, with clever caching and one time sorting it’s $O(d * n * ...
0
votes
0answers
63 views

complexity of empirical estimator

Assume we have i.i.d. data $x_{1}, \dots, x_{n}$ from discrete distribution. Then, let's us consider empirical estimator: $$ \hat{p}_{i} = \frac{ \sum_{j=1}^{n}1(x_{j}=i)}{n} $$ What is the ...
0
votes
1answer
652 views

How to inform the space and time complexity of K-means, SOM and Hierachical clustering

In the paper I am writing, one of the reviewers asked for an "a simple computational complexity analysis or time computational demands of their method" My question is : Can I simply report the ...
0
votes
0answers
217 views

Computational complexity of MaxiEnt classifier

I know that the time complexity of logistic regression can be as low as linear when the optimizer/solver is assumed to be linear, such as L-BFGS (this link) I know that multinomial logistic regression ...
0
votes
0answers
670 views

Time complexity of the EM algorithm

this is Fuzzy Relational Eigenvector Centrality-based Clustering Algorithm (FRECCA). Here, N = total number of data, C is the number of clusters. Link of this algorithm is here For line 1-10, time ...
0
votes
0answers
103 views

The relation of time-series signals complexity and other statistical and signals processing concepts

What is the relation between correlation and time-series signal complexity? For example, I was reading a paper that is talking about the Multi scale entropy (MSE) and its advantages over the Shannon ...
0
votes
0answers
28 views

weighing of probabilities in a multi horizon framework

I shall start with an example so it's clear what I'd like to explore: I have to decide how many sigarettes to smoke in a day. One person tells me they will me kill should it rain. his credibility ...
0
votes
0answers
105 views

Parametrizing a matrix (and algorithm) by its orthogonal complement

Given a large orthonormal matrix $U$, say $p\times p-k$ (with $k$ much smaller than $p$), is there an effficient way to parametrize $U$ by any matrix orthogonal complement (any orthonormal matrix ...