Parameter-free first-order gradient minimization in ℓp geometry

Fix $1<p<\infty$ and let $q=p/(p-1)$ . Given a first-order local value--gradient oracle for an objective $f:\mathbb{R}^n\to\mathbb{R}$ whose gradient is $L$ -Lipschitz from $(\mathbb{R}^n,\|\cdot\|_p)$ to $(\mathbb{R}^n,\|\cdot\|_q)$ , an initial point $x_0$ with a solution $x^*$ satisfying $\|x_0-x^*\|_p\le R$ , and a target $\varepsilon>0$ , determine whether there is a parameter-free algorithm that does not know $L$ , $R$ , or $f^*$ and returns a queried point $\widehat{x}$ satisfying $\|\nabla f(\widehat{x})\|_q\le\varepsilon$ , with dimension-free oracle complexity governed by $\overline K=\max\{1,LR/\varepsilon\}$ . Under a nondegenerate secant initialization, the claimed bounds are $O_p(\overline K^{1/2})$ post-initialization queries for $1<p\le2$ and $O_p(\overline K^{p/(p+2)})$ for $p>2$ , together with an additive calibration cost $O_p(\log(e+L/M_0))$ .

References

Primary source

arXiv

Additional references

Optimal Parameter-Free Gradient Minimization in ℓ_p Geometry — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new preprint claims a parameter-free optimization method works in every finite-dimensional geometry measured by an $ell_p$ norm, but the claim has not been independently checked.

The problem asks whether first-order optimization can minimize gradients without knowing key scale parameters in general $ell_p$ geometry for fixed $1<p<\infty$ . The latest source presents a proposed method extending parameter-free guarantees beyond previously unresolved general- $\ell_p$ settings.

Known results

Diakonikolas and Guzmán, version dated February 15, 2023: complementary minimization in general normed spaces, including a nearly optimal standard- $\ell_1$ method measured in the $\ell_\infty$ norm, but not the claimed parameter-free all- $\ell_p$ result.
A related paper claims parameter-free gradient minimization over $\mathbb{R}^n$ , without establishing the specific general- $\ell_p$ problem.

August 27, 2026 proposed all- $\ell_p$ method

An arXiv entry claims an adaptive method for every fixed $1<p<\infty$ , without prior knowledge of smoothness, initial-distance, or optimum-value scales. This is claimed progress, not a verified resolution: the retrieved abstract is truncated, leaving the exact assumptions and complexity guarantees unchecked.

Current status (as of August 2026): A preprint claims progress for every fixed $1<p<\infty$ , but its assumptions and guarantees remain to be verified; no independently confirmed complete solution was found.

Sources

No solutions have been posted yet.