Katkat
Back

Implement 1D convex minimization in Python

UberMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenMachine Learning

Last updated

An Uber Machine Learning Engineer technical-screen question on derivative-free 1D convex optimization: minimize a black-box convex function on a closed interval using only function evaluations. It tests method selection (golden-section vs ternary search), stopping criteria and tolerances, function-evaluation and time/space complexity analysis, and robust handling of flat regions, boundary optima, noisy evaluations, and numerical precision.

Question

Implement, in Python, an algorithm that minimizes a 1D black-box convex function F(x) over a closed interval [a, b]. Assume F is convex (hence unimodal) on [a, b], gradients are unavailable, and you may use only function evaluations.

Your answer should address all of the following:

  1. Method selection and justification. Choose an appropriate derivative-free method (e.g., golden-section search or ternary search) and justify the choice, especially with respect to the number of function evaluations each requires.
  2. Stopping criteria and tolerances. Specify your stopping rules (absolute/relative tolerance on the bracket width, an optional function-value tolerance, and a maximum-iteration / evaluation-budget guardrail).
  3. Complexity and function-evaluation count. Analyze time and space complexity and the number of function evaluations needed to reach a given tolerance.
  4. Robustness to edge cases. Explain how you handle:
  • non-strict convexity and flat regions,
  • boundary optima (the minimum at a or b),
  • noisy function evaluations,
  • numerical precision near machine epsilon, and invalid inputs.
  1. Working code. Provide a complete, runnable implementation.
  2. Testing and verification. Explain how you would test and verify correctness.