# Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization

arXiv: https://arxiv.org/abs/1811.07677 · HTML: https://mlsanity.com/paper/1811.07677/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2018.

## Built on by (most cited first, 3 of 3)

- [A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems](https://mlsanity.com/paper/2304.14907/) (2023)
- [A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method](https://mlsanity.com/paper/2603.10230/) (2026)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)

## Abstract (arXiv)

We develop a short-step interior point method to optimize a linear function over a convex body assuming that one only knows a membership oracle for this body. The approach is based on Abernethy and Hazan's sketch of a universal interior point method using the so-called entropic barrier [arXiv 1507.02528v2, 2015]. It is well-known that the gradient and Hessian of the entropic barrier can be approximated by sampling from Boltzmann-Gibbs distributions, and the entropic barrier was shown to be self-concordant by Bubeck and Eldan [arXiv 1412.1587v3, 2015]. The analysis of our algorithm uses properties of the entropic barrier, mixing times for hit-and-run random walks by Lov'asz and Vempala [Foundations of Computer Science, 2006], approximation quality guarantees for the mean and covariance of a log-concave distribution, and results from De Klerk, Glineur and Taylor on inexact Newton-type methods [arXiv 1709.0519, 2017].