UC Berkeley

Many decision-making systems require repeatedly solving a family of optimization problems as an instance parameter 𝜆 ∈ Λ varies. Classical approaches compute this solution map by discretizing the parameter domain, solving many optimization problems, and interpolating between the resulting solutions. This thesis develops an alternative view: learn the optimizer itself as a map from problem instances to decisions. By parameterizing the solution map as 𝚽(𝜆)𝜷, the computation of an entire family of optimizers can be lifted to a single stochastic optimization problem over the coefficient vector 𝜷.The first part of the thesis studies this idea in the language of learning solution paths. Under Euclidean smoothness and strong convexity assumptions, we relate suboptimality in the lifted stochastic problem to uniform solution-path error. We show that the lifted problem satisfies a relaxed weak growth condition, which yields linear convergence of constant step-size SGD to a neighborhood determined by the approximation error of the chosen basis. When the true solution map lies in the span of the basis, this limiting error vanishes. Combining this optimization analysis with approximation theory gives explicit complexity guarantees for differentiable and analytic solution paths, showing when learning the path can require substantially fewer gradient evaluations than discretization.The second part reframes and generalizes the method as learning an optimization proxy: a fast decision rule that approximates the optimizer of a parametric optimization problem without requiring a new solve at inference time. We introduce complexity-penalized proxy error and show how regularization stabilizes the theory when strong convexity or spectral lower-bound conditions may fail. We prove proxy-performance decompositions that connect in-distribution stochastic training progress to uniform out-of-distribution optimality guarantees. The analysis identifies a fundamental approximation–optimization tradeoff: more expressive proxy classes can reduce the limiting error, but may also worsen conditioning and slow first-order training. We further extend the theory from Euclidean geometry to Bregman geometry through stochastic reference function descent, allowing the training method to respect non-Euclidean domains such as positive orthants and simplices.The final part isolates the algorithmic geometry underlying these proxy-learning methods. We study stochastic steepest descent under general norm geometries, with particular attention to ℓ𝑝 geometry. This analysis clarifies how the choice of geometry changes descent directions, stochastic noise behavior, and convergence. In Euclidean geometry, stochastic steepest descent reduces to ordinary SGD, recovering the dense update structure used in the first part of the thesis. In ℓ1 geometry, the method resembles greedy coordinate selection, making it a first step toward sparse, stagewise, and boosting-style proxy construction. The analysis shows that general norm geometries can introduce batch-size stability thresholds that are absent from the Euclidean RWGC theory, and the numerical experiments suggest that this issue is visible for ℓ1 updates. Together, the three parts of the thesis provide a theoretical framework for learning parametric optimizers, connecting approximation of solution maps, robustness of optimization proxies, and the geometry of stochastic first-order methods.