R.I.P.
👻
Ghosted
On the Turing model complexity of interior point methods for semidefinite programming
July 13, 2015 · Declared Dead · 🏛 SIAM Journal on Optimization
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Etienne de Klerk, Frank Vallentin
arXiv ID
1507.03549
Category
math.OC: Optimization & Control
Cross-listed
cs.DS
Citations
38
Venue
SIAM Journal on Optimization
Last Checked
2 months ago
Abstract
It is known that one can solve semidefinite programs to within fixed accuracy in polynomial time using the ellipsoid method (under some assumptions). In this paper it is shown that the same holds true when one uses the short-step, primal interior point method. The main idea of the proof is to employ Diophantine approximation at each iteration to bound the intermediate bit-sizes of iterates.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
📜 Similar Papers
In the same crypt — Optimization & Control
R.I.P.
👻
Ghosted
Local SGD Converges Fast and Communicates Little
R.I.P.
👻
Ghosted
On Lazy Training in Differentiable Programming
R.I.P.
👻
Ghosted
A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications
R.I.P.
👻
Ghosted
Learned Primal-dual Reconstruction
R.I.P.
👻
Ghosted
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport
Died the same way — 👻 Ghosted
R.I.P.
👻
Ghosted
Language Models are Few-Shot Learners
R.I.P.
👻
Ghosted
PyTorch: An Imperative Style, High-Performance Deep Learning Library
R.I.P.
👻
Ghosted
XGBoost: A Scalable Tree Boosting System
R.I.P.
👻
Ghosted