FastPrep
Problem · Array

Backpropagation Through Sort and Median

Learn this problem
● HardOpenAIOA

Problem statement

Consider the function f: R^n -> R^n that sorts an input vector in ascending order and divides every sorted element by the median of the input:

def f(x):
    return np.sort(x) / np.median(x)

For example, f([3, 2, 1]) = [1/2, 1, 3/2].

Gradient task

You are given the input vector x and an upstream gradient v = dL/dy, where y = f(x). Compute and return dL/dx.

A runtime that is roughly linear in n, allowing logarithmic factors such as sorting, is acceptable.

Function

backpropSortMedian(x: double[], v: double[]) → double[]

Examples

Example 1

x = [3.0,2.0,1.0]v = [1.0,1.0,1.0]return = [0.5,-1.0,0.5]

The direct contribution through sorting is 1 / 2 for each original element. The median element 2 also receives the denominator contribution -(1 + 2 + 3) / 2^2 = -3/2, so its total gradient is -1.

Constraints

  • n is odd.
  • The median is unique.

More OpenAI problems

drafts saved locally
public double[] backpropSortMedian(double[] x, double[] v) {
  // write your code here
}
x[3.0,2.0,1.0]
v[1.0,1.0,1.0]
expected[0.5,-1.0,0.5]
checking account