Unknown Narrator
Well-Conditioned Log-Concave Sampling Needs Fewer Than Any Power of Dimension
An OpenAI preprint argues that sampling from a well-conditioned, strongly log-concave distribution to fixed total-variation accuracy requires at most \(C_\epsilon d^\epsilon\) value-and-gradient queries for every \(\epsilon>0\). The bound holds in the worst case, but its constants and algorithm may depend on \(\epsilon\); it is not a runtime guarantee or a polylogarithmic upper bound. The paper also proves a logarithmic query lower bound, so the query count cannot be constant.
Subquadratic Memory Requires More Samples for Exact Gaussian Direction Estimation
An OpenAI manuscript on Gaussian regression argues that exact, noiseless measurements do not eliminate the sample cost of learning when a learner has limited memory. For a learner that processes each sample once and retains fewer than order \(d^2\) bits, the paper proves that estimating a random direction in \(d\) dimensions to angular error \(\varepsilon\) requires at least order \(d\log(1/\varepsilon)\) samples. Its proof uses independent draws from the posterior distribution to track how much information the learner’s finite state retains.
A Nonspectrahedral Hyperbolicity Cone Has an Exact 307-Variable Semidefinite Lift
An OpenAI preprint gives an exact semidefinite lift for a hyperbolicity cone that a companion paper shows cannot be represented directly by a positive semidefinite matrix in its original coordinates. The authors add 307 auxiliary variables and impose one 100-by-100 matrix inequality; projecting away those variables recovers the cone, including its singular boundary points. The construction establishes that the obstruction is to a direct representation, not to semidefinite representation by lifting.