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
0answers
3 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
34 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
1answer
35 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.
0
votes
0answers
11 views

LARS/GLMNET/Coordinate descent - computational speed vs complexity - a confusing result

The computational complexity of LASSO via LARS is $\mathcal{O}(K^3 + K^2 n)$ see stackexchange post for a $K$ features and $n$ data points. (The derivation in Efron et al., 2004 make sense to me ...
1
vote
0answers
33 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_*$$ ...
0
votes
1answer
22 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)$ ...
1
vote
0answers
13 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
82 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
60 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}...
2
votes
1answer
33 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 ...
0
votes
0answers
15 views

time complexity of sampling from multivariate hypergeometric distribuiton

numpy has an implementation and the doc is here. It says it is "roughly" equivalent to: ...
0
votes
0answers
24 views

time complexity of neural network and other machine learning algorithm on testing phase

Is there someone has found some useful material, papers of books about the time computation complexity of neural network and other machine learning method(SVM, RF, logistic regression .etc). I just ...
2
votes
1answer
31 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). ...
0
votes
0answers
38 views

Complexity comparison of XGBoost, Logistic Regression and SVM

Suppose that for a multi-class classification problem I am getting the same performance from these three classifiers. From the complexity perspective, which one should I choose (i.e. in terms of their ...
0
votes
0answers
38 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
32 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 \...
1
vote
0answers
18 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 ...
2
votes
0answers
10 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 ...
0
votes
0answers
219 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 * ...
1
vote
2answers
17 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 ...
0
votes
1answer
512 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 ...
0
votes
0answers
270 views

What is time complexity big O for 2D filters and 1D filters in image convolution Neural networks.?

I went through this link to understand, but was not able to grasp the concept. What is the computational complexity of a 1D convolutional layer? Consider a more general case: ...
0
votes
0answers
61 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
0answers
56 views

What is the time and space complexity of a standard SOM algorithm?

I am trying to understand the time complexity of a standard SOM algorithm. Given D dimensional Input, a total of N inputs, over a set of E epochs and for an M*M sized map, what would be the complexity?...
2
votes
1answer
1k 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 )$...
1
vote
1answer
34 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
2answers
107 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 ...
3
votes
0answers
37 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 ...
1
vote
1answer
19 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 ...
1
vote
0answers
81 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) ...
1
vote
0answers
758 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 ...
0
votes
1answer
151 views

knn asymptotic complexity vs svm [duplicate]

I'm doing a little report about the KNN complexity vs SVM.. I would like to know your opinions.. I built this text according to my perspective searching in papers, websites, ppts etc: The reason ...
0
votes
1answer
311 views

Who is more complex computationally knn or SVM? [closed]

I have trained two models using sklearn library in python.. My dataset was about 750 features, 250 features per class (three classes), I trained only one feature dimension (1-D array). This are the ...
4
votes
2answers
6k views

What is the computational cost of gradient descent vs linear regression?

I know the computational costs for the closed form of linear regression is $O(n^3)$, but I can't find a similar cost comparison to gradient descent. There are some similar questions here with people "...
1
vote
1answer
1k views

What does it mean for K mean problem to be NP hard and why?

Given a decision problem (a problem with yes or no answer), the problem is said to be NP-hard if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time. Recall that NP-...
0
votes
1answer
443 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
1answer
608 views

K means clustering time fluctuates with increased value of K

I have written k means clustering code in c#. I am clustering random 99 text articles of Sports Area which I downloaded from Github for different values of K i.e.3,4,5,6,7. I want to analyze the time ...
4
votes
0answers
411 views

Computational complexity of sampling from discrete and continuous distributions?

What is the computational complexity of sampling from any of these cases? I mean the computational complexity of the most efficient existing algorithm, not a possible algorithm or a lower bound. ...
7
votes
2answers
8k views

Why does my LSTM take so much time to train?

I am trying to train a bidirectional LSTM to do a sequential text-tagging task (particularly, I want to do automatic punctuation). I use letters as the building-blocks: I represent each input letter ...
0
votes
0answers
191 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 ...
2
votes
1answer
94 views

Clustering: Clique vs. Agglomerative with Complete-Link

In my data, I have a defined a symmetrical relation $R$ where $R(i,j)=R(j,i)$ indicates that $i$ and $j$ are closed each other. I need to find cliques $C_1,C_2,\dots,C_n$ where $C_k\cap C_l=\...
2
votes
1answer
2k views

What is the time complexity of spectral clustering and why is it so?

What is the time complexity of spectral clustering and why (mathematically speaking) is it so? What are possible existing alternatives to speed up the computations required by the algorithm?
9
votes
1answer
2k views

XGBoost paper - time complexity analysis

I'm reading through the XGBoost paper and I'm confused by the subsection of 4.1 titled "Time Complexity Analysis". Here the authors assert that the exact greedy algorithm with $K$ trees, a maximum ...
0
votes
1answer
155 views

What all does the training time for a neural network include?

I recently developed a DNN model and I want to know what exactly is training time and what all steps are included in it? For ex I carried out the following steps: Determined best Network ...
3
votes
3answers
1k views

GMM EM algorithm complexity per iteration

I was fitting GMM clusters with diagonal covariance on my data using EM with $n$ (=5e6) points, each having $m$ (=160) ...
2
votes
1answer
224 views

Dimension reduction methods: overview of complexity

For classical dimension reduction methods (PMF, PCA, SVD, t-SNE...) or some others, I need to know the complexity of efficient implementations: with $N$ vectors in dimension $d$ reduced to dimension ...
2
votes
0answers
166 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 ...
1
vote
2answers
2k views

How can the xor function be formed with a single hidden layer of neural network?

I was recently viewing Andrew Ng's deep learning specialization lectures and I came forward to the following image It is pretty obvious how the above function( x1 XOR x2 XOR x3..... XOR xn) can be ...
1
vote
1answer
242 views

Where does the exponential time complexity in LDA's posterior of topics arise?

In Finding scientific topics (PNAS 2004) the authors derive the (marginalized) posterior distribution of topic assignments given the observed word and arrive at equation (4). Then, immediately after, ...
1
vote
0answers
177 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 ...