Implement 1D convex minimization in Python
Company: Uber
Role: Machine Learning Engineer
Category: Machine Learning
Difficulty: medium
Interview Round: Technical Screen
##### 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.
5. **Working code.** Provide a complete, runnable implementation.
6. **Testing and verification.** Explain how you would test and verify correctness.
Quick Answer: 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.