Katkat
Back

Find constant minimizing absolute error

CitadelData Scientist · Technical Screen
EasyData ScientistTechnical ScreenStatistics & Math

Last updated

This question tests the understanding of L1 loss minimization and the statistical property that the median is the optimal point estimator under absolute error loss.

Problem Statement

Given a set of $N$ real-valued observations $X = [x_1, x_2, ..., x_n]$, we want to find a single constant $c$ that minimizes the total absolute error defined by the function:

f(c) = Σ |x_i - c| for i = 1 to n

Task

  1. Prove or explain mathematically which value of $c$ minimizes f(c).
  2. Write a function find_optimal_constant(data) that returns the value of $c$ for a given list of numbers.

Constraints

  • $n$ is a positive integer.
  • The values in $X$ can be negative, zero, or positive.
  • The function should handle both even and odd values of $n$ correctly.

Examples

Example 1: Input: [1, 2, 9] Output: 2 Explanation: |1-2| + |2-2| + |9-2| = 1 + 0 + 7 = 8. Any other value will result in a higher sum.

Example 2: Input: [1, 2, 3, 100] Output: 2.5 (or any value in the range [2, 3]) Explanation: For an even number of elements, any value between the two middle elements (inclusive) minimizes the sum of absolute deviations.

Edge Cases

  • Single element lists.
  • Lists with duplicate values.
  • Lists where all elements are identical.

Hints

Hint 1

Consider the derivative of the absolute value function |x - c| with respect to c, keeping in mind it is not differentiable at x = c.

Hint 2

Think about what happens to the sum as you move the constant c slightly to the left or right of a specific data point.

Hint 3

Recall the relationship between the sum of distances to points on a line and the median of those points.

Follow-up questions

  • How does the optimal constant change if we minimize the squared error instead of the absolute error?
  • What are the implications of using the median vs. the mean as a measure of central tendency when the dataset contains significant outliers?
  • If we were to add a weight w_i to each observation x_i, how would you find the value c that minimizes Σ w_i * |x_i - c|?