53 citations · 178 across the 24 of their papers we have counts for
27 papers
Asymptotic Lower Bounds for Continuous Optimization
Oliver Hinder, Yuntian Jiang
Nonasymptotic convergence rates for optimization problems have been extensively studied across a wide range of settings, with carefully constructed worst-case instances establishin…
An adaptive interior-point method with backtracking line search for convex constrained optimization
Fadi Hamad, Oliver Hinder
Interior-point methods (IPMs) are widely adopted due to their high practical efficiency in solving linear, convex, and nonconvex optimization problems. For convex optimization, thi…
Clipping the Price of Adaptivity at the Tail
Itai Kreisler, Yair Carmon, Oliver Hinder
Adaptive stochastic convex optimization (SCO) methods face a fundamental ``price of adaptivity'' barrier: under the standard set of assumptions, they cannot efficiently adapt to la…
The Sample Complexity of Parameter-Free Stochastic Convex Optimization
Jared Lawrence, Ari Kalinsky, Hannah Bradfield +2
We study the sample complexity of stochastic convex optimization when problem parameters such as the distance to optimality and the Lipschitz constant are unknown. We pursue two st…
PDLP: A Practical First-Order Method for Large-Scale Linear Programming
David Applegate, Mateo Díaz, Oliver Hinder +4
We present PDLP, a practical first-order method for linear programming (LP) designed to solve large-scale LP problems. PDLP is based on the primal-dual hybrid gradient (PDHG) metho…
A simple and practical adaptive trust-region method
Fadi Hamad, Oliver Hinder
We present an adaptive trust-region method for unconstrained optimization that allows inexact solutions to the trust-region subproblems. Our method is a simple variant of the class…
A consistently adaptive trust-region method
Fadi Hamad, Oliver Hinder
Adaptive trust-region methods attempt to maintain strong convergence guarantees without depending on conservative estimates of problem properties such as Lipschitz constants. Howev…
Accelerated Parameter-Free Stochastic Optimization
Itai Kreisler, Maor Ivgi, Oliver Hinder +1
We propose a method that achieves near-optimal rates for smooth stochastic convex optimization and requires essentially no prior knowledge of problem parameters. This improves on p…
The Price of Adaptivity in Stochastic Convex Optimization
Yair Carmon, Oliver Hinder
We prove impossibility results for adaptivity in non-smooth stochastic convex optimization. Given a set of problem parameters we wish to adapt to, we define a "price of adaptivity"…
Datasets and Benchmarks for Nanophotonic Structure and Parametric Design Simulations
Jungtaek Kim, Mingxuan Li, Oliver Hinder +1
Nanophotonic structures have versatile applications including solar cells, anti-reflective coatings, electromagnetic interference shielding, optical filters, and light emitting dio…
Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs
Oliver Hinder
We analyze restarted PDHG on totally unimodular linear programs. In particular, we show that restarted PDHG finds an -optimal solution in $O( H m_1^{2.5} \sqrt{\textbf{nnz}(A)}…
DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule
Maor Ivgi, Oliver Hinder, Yair Carmon
We propose a tuning-free dynamic SGD step size formula, which we call Distance over Gradients (DoG). The DoG step sizes depend on simple empirical quantities (distance from the ini…
Optimal Diagonal Preconditioning
Zhaonan Qu, Wenzhi Gao, Oliver Hinder +2
Preconditioning has long been a staple technique in optimization, often applied to reduce the condition number of a matrix and speed up the convergence of algorithms. Although ther…
Making SGD Parameter-Free
Yair Carmon, Oliver Hinder
We develop an algorithm for parameter-free stochastic convex optimization (SCO) whose rate of convergence is only a double-logarithmic factor larger than the optimal rate for the c…
Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
David Applegate, Mateo Díaz, Oliver Hinder +4
We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addit…
Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness
David Applegate, Oliver Hinder, Haihao Lu +1
First-order primal-dual methods are appealing for their low memory overhead, fast iterations, and effective parallelization. However, they are often slow at finding high accuracy s…
An efficient nonconvex reformulation of stagewise convex optimization problems
Rudy Bunel, Oliver Hinder, Srinadh Bhojanapalli +2
Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-she…
A generic adaptive restart scheme with applications to saddle point algorithms
Oliver Hinder, Miles Lubin
We provide a simple and generic adaptive restart scheme for convex optimization that is able to achieve worst-case bounds matching (up to constant multiplicative factors) optimal r…
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
Oliver Hinder, Aaron Sidford, Nimit S. Sohoni
In this paper, we provide near-optimal accelerated first-order methods for minimizing a broad class of smooth nonconvex functions that are strictly unimodal on all lines through a…
Worst-case iteration bounds for log barrier methods on problems with nonconvex constraints
Oliver Hinder, Yinyu Ye
Interior point methods (IPMs) that handle nonconvex constraints such as IPOPT, KNITRO and LOQO have had enormous practical success. We consider IPMs in the setting where the object…
Cutting plane methods can be extended into nonconvex optimization
Oliver Hinder
We show that it is possible to obtain an expected runtime --- including computational cost --- for finding -stationary points of smooth nonconvex functions using c…
A one-phase interior point method for nonconvex optimization
Oliver Hinder, Yinyu Ye
The work of Wachter and Biegler suggests that infeasible-start interior point methods (IPMs) developed for linear programming cannot be adapted to nonlinear optimization without si…
Lower Bounds for Finding Stationary Points II: First-Order Methods
Yair Carmon, John C. Duchi, Oliver Hinder +1
We establish lower bounds on the complexity of finding -stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic…
Lower Bounds for Finding Stationary Points I
Yair Carmon, John C. Duchi, Oliver Hinder +1
We prove lower bounds on the complexity of finding -stationary points (points such that ) of smooth, high-dimensional, and potentially non-convex func…