Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We want to select one out of a given set of (continuous) functions that best matches a set of observations $\{(s_i,c_i) \mid 1 \leq i \leq N\} \subseteq\mathbb{N} \times \mathbb{N}$ (input size and counter) of unknown distribution. We have many observed counters per sizeĀ¹.

So far, we have used least-square fitting on the average values per size. This obviously neglects any asymmetry in the data distribution (for a fixed size). Consider this example:

enter image description here

The blue blobs are the actually observed counters (one desaturated fleck per measurement, creating something like a violin plot), the red dots are the averages (per size) and the blue line is our estimation. Apparently, the actual measurements have some asymmetric distribution around the average.

Now we think that we can improve the result by fitting against all observations. This would increase the amount of data to be stored, transmitted and computed with a lot, so we would like to get around this. So this is our question:

Is there a statistic that can replace all observations per size without changing the result of least-square fitting, i.e. is there an $S : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ such that

$\qquad \displaystyle \arg\min \sum_{i=0}^N (c_i - f(s_i))^2 \ =\ \arg\min \sum_{i=0}^{\max_j s_j} (S(C_i) - f(i))^2$

with $C_i = \{c_j \mid s_j = i\}$ for all (reasonable) functions $f$?

We would also be fine with using another criterion but least-square on the right hand side, as long as it is (about) equivalent (given $S$). Also, approximate equality is fine as long as we have equality in the limit (for $N$ and/or $\max_j s_j$ to $\infty$).

  1. We count how often a given algorithm hits a given basic block when executed on inputs of certain sizes. For an average case estimation, we run the algorithm on random sample of inputs per size.
share|improve this question
Actually, we no longer think fitting against all points instead of the average is better for us since we want to fit the average runtime (in order to guess the expected runtime). It's still an interesting question. – Raphael Jul 27 '12 at 12:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.