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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 views

What is the time complexity one-to-many LSTM? [closed]

What is the time complexity one-to-many LSTM ?
ati's user avatar
  • 1
4 votes
0 answers
65 views

Does training time increase more if I add a layer at the beginning of a neural network or at the end?

Let's consider a fixed NN architecture, dataset and hardware. We add a layer, either at the beginning or at the end of the NN. In which case the training time will increase more? Intuitively, I ...
DeltaIV's user avatar
  • 17.7k
2 votes
0 answers
37 views

Estimating test error from $X^TX$ and $X^Ty$

Suppose we've got a dataset with a very large number of samples (say, billions), and a smaller number of features (say, hundreds). To calculate the coefficients of a single a ridge regression model, ...
Michael's user avatar
  • 21
8 votes
1 answer
95 views

What is the complexity to compute the sample entropy of a time series of length N?

background Some algorithms are linear in operations, so the number of operations to complete is $O \left(N\right)$, while others are quadratic $O\left(N^2\right)$, cubic $O \left(N^3\right)$, or non-...
EngrStudent's user avatar
  • 9,165
1 vote
0 answers
32 views

Fast algorithm of ARIMA-GARCH model selection

I use ARFIMA(p, x, q)-GARCH(P, Q) models for time series forecasting and when I calibrate models for selection the best via BIC criteria, I use "slow" approach when I calculate BIC for every ...
Dmitriy's user avatar
  • 234
0 votes
0 answers
32 views

Time complexity of Bayesian Ridge Regression

What is the training and inference time complexity of Bayesian Ridge Regression (e.g. as implemented in sklearn) in terms of the number of samples n and the number of features d?
PascalIv's user avatar
  • 809
0 votes
0 answers
100 views

Time Complexity of using the kernel trick on polynomial basis expansion

I have read that: If we have two feature vectors ${x = (x_1,x_2,…,x_D)}$ and $y=(y_1,y_2,…,y_D)$ and we do a degree d polynomial basis expansion to get $f(x)$ and $f(y)$, then to calculate the inner ...
revision's user avatar
0 votes
0 answers
9 views

Time complexity of ranked batch-mode sampling query strategy

I am performing different Active Learning experiments using several query strategies. One of the query strategies is the "Ranked batch-mode sampling" from Python's modAL library, which is an ...
pabvvv's user avatar
  • 31
0 votes
0 answers
76 views

Computational complexity of L1 LASSO

I am interest in the constrained L1 Lasso problem: $$\min_{\beta\in \mathbb{R}^p:\sum_{i\in[p]}|\beta_i|=1} \|X\beta -s\|^2, (1)$$ for design matrix $X\in \mathbb{R}^{n \times p}$ and target $s\in \...
user6952886's user avatar
4 votes
1 answer
455 views

Why exactly do some Decision Tree Algorithms sort the features before finding the best split?

I read about the time complexity of Decision Tree Algorithms like CART, and understand why the time complexity, with sorting, can be approximated as $O(m n^2 \log n)$. I will try to go through the ...
kklaw's user avatar
  • 515
1 vote
1 answer
336 views

Time complexity of Metropolis-Hastings and potential speed-up?

The MH algorithm essentially involves generating a sample destination state from a proposal distribution, computing the acceptance probability as a function of that sample, and checking whether a ...
Tanishq Kumar's user avatar
1 vote
1 answer
26 views

A question on computational complexity of a numerical differentiation (equation (5.77)) in Bishop's Pattern Recognition and Machine Learning

In page 249 of Christopher M. Bishop's book "Pattern Recognition and Machine Learning", it is said Again, the implementation of such algorithms can be checked by using numerical ...
zzzhhh's user avatar
  • 323
0 votes
1 answer
120 views

Computational Complexity of Marginalization

Suppose you have a joint probability distribution with M variables, each sampled from a set of cardinality N. Now, suppose you want to marginalize one of the variables. My guess right now about the ...
mathlete42's user avatar
3 votes
0 answers
33 views

Check if growth rate is worse than quadratic?

I was asked to move the question here (https://stackoverflow.com/questions/72692849/check-if-growth-rate-is-worse-than-quadratic) Let's say I have collected a dataset for estimating algorithmic ...
Ricky Han's user avatar
  • 131
0 votes
0 answers
73 views

Learning Algorithm Time & Sample Complexity

Let $X=R^{2}$. Let $u=\left(\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ w=\left(-\frac{\sqrt{3}}{2},-\frac{1}{2}\right),\ v=\left(0,1\right)$ and $C=H=\left\{h\left(r\right)=\left\{\left(x_{1},x_{2\ }\...
MathCurious's user avatar
1 vote
1 answer
336 views

Stepwise model selection by AIC

I am learning about performing stepwise model selection by AIC and having some questions: What is the regularization parameter for step-AIC? In what way is forward step-AIC an evolution of univariate ...
tcxrp's user avatar
  • 51
1 vote
0 answers
46 views

How to estimate the time and memory requirement for Sparse and variational Gaussian Process (SVGP) with minibatch approach

I'm implementing Sparse and variational Gaussian Process (SVGP) using GPflow library using minibatches. I've been trying to search for details regarding the time and memory complexities e.g. from this ...
jjepsuomi's user avatar
  • 5,777
2 votes
0 answers
69 views

What are some well-known unbiased estimator of regression coefficient besides OLS estimator?

Is there any other unbiased estimator of regression coefficient than OLS? For instance, one might consider using unbiased estimator with less computational cost (since OLS involves matrix inversion)?
user808843's user avatar
0 votes
0 answers
41 views

The sum of $n$ zero-mean values is of $O(\sqrt{n})$ at max

Why is the sum of $n$ zero-mean values is of $O(\sqrt{n})$ at max? If $X$ is a random variable with a standard deviation $\sigma$, the standard deviation of $n$ such i.i.d. random variables is $\sqrt{...
CWC's user avatar
  • 281
4 votes
1 answer
1k views

Why Are Neural Networks Considered "Expensive" to Train?

Recently, I was looking at the optimization functions required in training Kernel Based Methods compared to Neural Networks. 1) Kernel Methods: For instance, I was looking at the optimization in ...
Uk rain troll's user avatar
3 votes
2 answers
341 views

Time complexity of training SVM and C

I always though that a big (high) C will lead to a lower svm training complexity due to lower number of support vectors. I was very surprised to read a paper that states the opposite - aka, big Cs ...
LOOL's user avatar
  • 31
1 vote
0 answers
241 views

FLOPS calculation for deep architectures [duplicate]

Pleas guide me as I have exhausted all my efforts to do so. I need to have the FLOPS value for DeepID2+ which is an FR model and maybe a few more (DeepID, Deep Id2). No publication mentions it and I ...
Asad's user avatar
  • 11
2 votes
0 answers
36 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,...
Betterthan Kwora's user avatar
5 votes
2 answers
3k views

Do deep neural networks learn slower with the addition of more hidden layers?

The number of hidden layers increases the number of weights, also increases the terms in the back-propagation algorithm, i.e. more derivatives, hence more computation. Can we say that neural networks ...
The Limit Breaker's user avatar
5 votes
1 answer
262 views

When does complexity in machine learning algorithms actually become an issue?

I keep seeing complexities for machine learning algorithms e.g. Gaussian process implementation requires inversion of an nxn matrix so complexity is $O(n^3)$. When does complexity actually become an ...
stochasticmrfox's user avatar
2 votes
1 answer
182 views

Cost of Nested Cross-Validation

What is the cost of nested cross-validation in terms of the number of times the algorithm needs to perform a fit-evaluate step? Based on this description of the algorithm, I think the answer is: $n \...
Colm Bhandal's user avatar
2 votes
1 answer
3k views

What is Big-O complexity of classifying an image using CNN?

If i have an image consisting of n pixels what will be the complexity of classifying it using a convolutional neural network, expressed in big-o notation? (assuming my cnn is already trained)
Studyinghard 's user avatar
0 votes
1 answer
3k views

KNN Complexity (Big O notation)

I need to show the Big O Notation for KNN algorithm. So I wanted to know the complexity of brute force KNN algorithm; and to make the graph do we have x-axis: input size, y-axis: the speed.
thbrain's user avatar
1 vote
0 answers
68 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_*$$ ...
rando's user avatar
  • 236
0 votes
1 answer
308 views

Run time complexity of nearest neighbor

A paper titled, "Efficient Neighbor Searching in Nonlinear Time Series Analysis (1996)" download link mentions that the time complexity for the naive NN approach is $N^2/2$ i.e., $O(N^2/2)$ ...
Sm1's user avatar
  • 231
1 vote
0 answers
172 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 ...
Ditlev Jørgensen's user avatar
1 vote
0 answers
825 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 ...
john price's user avatar
1 vote
0 answers
70 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}...
Arnaud Mégret's user avatar
2 votes
1 answer
568 views

How to find the time complexity of an MLE based algorithm

How to calculate or what is the time complexity (big-Oh) for this method? Based on my understanding, MLE depends on number of datapoints, $N$ so time complexity for MLE is O(N). However, there are ...
Sm1's user avatar
  • 231
3 votes
1 answer
1k views

Why does forward selection only take $O(p^2)$ calls to the learning algorithm?

In http://cs229.stanford.edu/notes/cs229-notes-all/cs229-notes5.pdf pg 5, it states that forward search takes $O(p^2)$ (note the notes uses $n$ instead of $p$ for the number if independent variables). ...
David's user avatar
  • 705
0 votes
0 answers
167 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.
Reza Rawassizadeh's user avatar
0 votes
0 answers
39 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 \...
Talking Puppet's user avatar
1 vote
0 answers
60 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 ...
user88914's user avatar
  • 111
1 vote
0 answers
16 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 ...
ABIM's user avatar
  • 544
0 votes
0 answers
1k 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 * ...
qalis's user avatar
  • 239
1 vote
2 answers
36 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 ...
Johnny's user avatar
  • 111
1 vote
1 answer
4k views

Why does R take so much time to run auto.arima(). How can I shorten the calculation time? [duplicate]

I have been trying to run analysis and model a ts series of Natural Gas spot prices. With data provided by the Qandl API. The whole analysis was working fine, however, I experiences issues with the ...
Sofiane's user avatar
  • 13
0 votes
0 answers
66 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 ...
ABK's user avatar
  • 476
6 votes
1 answer
8k views

What is the computational complexity of a 1D convolutional layer?

What is the complexity of a 1D convolutional layer?. I'm getting $\mathcal{O}(n \cdot k \cdot d)$, but in Attention Is All You Need, Vaswani et al. report that it is $\mathcal{O}(k \cdot n \cdot d^2 )$...
Antoine's user avatar
  • 6,129
3 votes
1 answer
288 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 ...
azure31's user avatar
  • 31
2 votes
2 answers
456 views

Computational complexity in practice: predict execution time for a dataset

Suppose I know that the computational complexity of an algorithm is $\mathcal{O}(f(n))$ where $n$ is the sample size. Suppose I have two data sets with sizes $n_1$ and $n_2$. The data sets have no ...
Richard Hardy's user avatar
3 votes
0 answers
51 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 ...
2 votes
1 answer
48 views

Neural Networks and a catalogue of the number of floating point operations in various types of statistical and time series models

I recently came across this paper Green AI. In the paper they discussed using floating point operation (FPO) count during testing and implementation of Neural Networks (NNs) to compare the ...
Alex's user avatar
  • 2,011
1 vote
0 answers
88 views

How to compute largest values of random variables? [closed]

Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF. We know that max of two independent random variables is: if Z = max(X,Y) ...
nauok's user avatar
  • 11
1 vote
0 answers
1k 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 ...
newbie's user avatar
  • 215