Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

Anas Barakat; Andreas Kontogiannis; Antonios Varvitsiotis; Ioannis Panageas; Vasilis Pollatos

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

T0 review · 0 major / 2 minor · reviewed 2026-06-29 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Online gradient descent achieves optimal O(sqrt(T)) regret on hidden-convex losses under a necessary Hessian compatibility condition.

desk verdict They recover the optimal sqrt(T) regret for OGD on hidden-convex losses via a tighter discrete-time equivalence and a necessary-and-sufficient Hessian condition that replaces the earlier diagonal-Jacobian requirement. read the letter →

arxiv 2605.26373 v1 pith:NX4IW2W2 submitted 2026-05-25 cs.LG math.OCstat.ML

Anas Barakat , Andreas Kontogiannis , Vasilis Pollatos , Ioannis Panageas , Antonios Varvitsiotis This is my paper · ORCID

classification cs.LGmath.OCstat.ML

keywords hidden-convexlossesonlinegradientdescentalgorithmicequivalenceregretboundsHessiancompatibilitybanditfeedbackadversariallearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that online gradient descent applied directly to nonconvex but hidden-convex losses attains the optimal adversarial regret rate of O(sqrt(T)) when the reparameterization satisfies a geometric condition. This closes the gap left by prior work that obtained only the slower O(T^{2/3}) rate. The argument relies on a refined discrete-time equivalence showing that OGD on the hidden losses behaves like online mirror descent on the underlying convex losses. The authors replace an earlier sufficient condition with a necessary-and-sufficient Hessian compatibility condition and prove that violating it permits constructions where regret becomes linear in T.

What carries the argument

Hessian compatibility condition on the reparameterization, which makes OGD on the hidden losses algorithmically equivalent to OMD on the convex losses.

What would settle it

Construct a smooth reparameterization violating Hessian compatibility together with an adversarial sequence of hidden-convex losses and check whether OGD regret grows linearly.

Watch

Extended reading notes

Core claim

Via a sharper discrete-time algorithmic equivalence argument, online gradient descent achieves O(sqrt(T)) regret on hidden-convex losses under the Hessian compatibility condition, matching the optimal worst-case rate for adversarial online convex optimization. The condition is necessary: its violation allows smooth reparameterizations and adversarial loss sequences for which OGD suffers Omega(T) regret. The same analysis yields an O(T^{3/4}) expected-regret bound for one-point bandit feedback with spherical smoothing.

Load-bearing premise

The nonlinear reparameterization must satisfy the Hessian compatibility condition.

Editorial extensions

If this is right

OGD attains the optimal Theta(sqrt(T)) regret rate for this class of losses.
The set of admissible reparameterizations is strictly larger than those obeying the earlier diagonal-Jacobian condition.
Bandit OGD with spherical smoothing attains the classical O(T^{3/4}) expected regret rate.
Hessian compatibility is essential, since its absence permits Omega(T) regret constructions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Similar equivalence arguments may recover optimal rates for other families of nonconvex losses once appropriate geometric conditions are identified.
Practical implementations that already use OGD could be applied without change to problems whose losses admit a hidden-convex representation.
The necessity result suggests that geometry-aware algorithm design is required even inside the hidden-convex regime.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The paper closes the main open question from Ghai et al. by showing OGD gets O(sqrt(T)) regret on hidden-convex losses, matching the convex case. It also gives a necessary-and-sufficient Hessian compatibility condition on the reparameterization, which widens the admissible class, and backs this with an explicit Omega(T) lower bound when the condition fails. The bandit extension to O(T^{3/4}) is a clean add-on that matches the known convex rate.

The sharper discrete-time argument is the real technical step; it avoids the earlier T^{2/3} loss from the continuous-time approximation. The lower-bound construction is useful because it shows the geometry is tight rather than just sufficient. Both results sit on top of the prior algorithmic equivalence framework without circularity.

The main limitation is that the setting still requires a specific nonlinear reparameterization with the Hessian property plus smoothness; this is not a route to general nonconvex online learning. The proofs are only sketched in the abstract, so the error terms and exact discrete-time handling would need checking in the full text, but nothing in the stated claims looks internally inconsistent.

This is for people working on structured nonconvex online learning or algorithmic equivalences. It deserves a serious referee because it resolves two stated open questions with matching upper and lower bounds and a natural bandit extension.

Referee Report

0 major / 2 minor

Summary. The manuscript claims that, for adversarial online learning with hidden-convex losses (nonconvex losses that are convex after a nonlinear reparameterization), a sharper discrete-time algorithmic equivalence argument shows that online gradient descent (OGD) achieves the optimal O(sqrt(T)) regret under geometric and smoothness assumptions. It replaces the prior diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition on the reparameterization, supplies an explicit Omega(T) lower-bound construction when compatibility fails, and extends the analysis to one-point bandit feedback, obtaining O(T^{3/4}) expected regret for bandit OGD with spherical smoothing.

Significance. If the derivations hold, the work is significant because it affirmatively resolves the open question left by Ghai, Lu and Hazan (2022) on recovering the optimal Theta(sqrt(T)) rate in the hidden-convex setting and supplies both an upper bound via refined equivalence and a matching lower-bound construction that demonstrates necessity of the new geometric condition. The explicit construction of the Omega(T) counterexample and the bandit extension (matching the classical convex rate) are concrete strengths that advance the algorithmic-equivalence approach to nonconvex online learning.

minor comments (2)

[Abstract] The abstract refers to 'the same assumptions' without restating the geometric and smoothness conditions; a one-sentence recap in the abstract or introduction would improve accessibility.
Notation for the reparameterization map, its Jacobian, and Hessian should be introduced once with a single consistent symbol set to prevent minor confusion when the Hessian compatibility condition is stated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of resolving the open question from Ghai et al. (2022), and the recommendation to accept.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper's central result is an improved discrete-time algorithmic equivalence between OGD on hidden-convex losses and OMD on the underlying convex losses, yielding an O(sqrt(T)) regret bound under a new necessary-and-sufficient Hessian compatibility condition. This equivalence is derived directly from the paper's analysis rather than by fitting parameters or redefining inputs; the necessity of the condition is established via an explicit adversarial construction that produces Omega(T) regret when compatibility fails. The argument builds on but sharpens a prior external result (Ghai et al. 2022) without reducing the claimed bound to a self-referential definition or self-citation chain. The bandit extension similarly follows from the same equivalence applied to smoothed feedback. No load-bearing step collapses to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The central claims rest on geometric and smoothness assumptions inherited from prior work plus the newly stated Hessian compatibility condition; no free parameters or invented entities are introduced.

assumptions (1)

domain assumption Geometric and smoothness assumptions on the nonlinear reparameterization (inherited from Ghai et al. 2022)
Required for the algorithmic equivalence between OGD on hidden-convex losses and OMD on the underlying convex losses.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback." pith.science (2026). https://pith.science/paper/NX4IW2W2

@misc{pith2026260526373,
  author       = {Pith},
  title        = {Pith review of: Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NX4IW2W2}},
  note         = {Machine review of arXiv:2605.26373}
}

abstract

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding $\mathcal{O}(T^{2/3})$ regret. They left open whether the optimal $\Theta(\sqrt{T})$ regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves $\mathcal{O}(\sqrt{T})$ regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers $\Omega(T)$ regret. Finally, we extend our analysis to one-point bandit feedback and prove a $\mathcal{O}(T^{3/4})$ expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 4 canonical work pages

[1]

Stochastic optimization under hidden convexity.SIAM Journal on Optimization, 35(4):2544–2571, 2025a

Ilyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden convexity.SIAM Journal on Optimization, 35(4):2544–2571, 2025a. Ilyas Fatkhullin, Niao He, Guanghui Lan, and Florian Wolf. Global solutions to non-convex functional constrained problems with hidden convexity.arXiv preprint arXiv:2511.10626, 2025b. Abraham D. Flaxman, Adam Tauman...

work page arXiv
[2]

arXiv preprint arXiv:2402.06535 , year=

Tor Lattimore. Bandit convex optimisation.arXiv preprint arXiv:2402.06535,

work page arXiv
[3]

Online Learning: A Modern Introduction Using Convex Optimization

Francesco Orabona. A modern introduction to online learning.arXiv preprint arXiv:1912.13213,

work page Pith review arXiv 1912
[4]

Unveiling hidden convexity in deep learning: A sparse signal processing perspective.arXiv preprint arXiv:2603.23831,

Emi Zeger and Mert Pilanci. Unveiling hidden convexity in deep learning: A sparse signal processing perspective.arXiv preprint arXiv:2603.23831,

work page arXiv
[5]

Using Assumption 2, we obtain: ∥Jεq t (q(xt+1))∥=∥J q−1(q(xt+1))−J q−1(yt)∥ ≤G∥q(x t+1)−y t∥ ≤ηG 2 ˆGF , where the last step uses the first estimate (i) proved above

(31) 22 Proof of (ii).Recall from (16) that for anyy=q(x), x∈ X, εq t (y) =q −1(y)−q −1(yt)−J q−1(yt)(y−y t).(32) Differentiating w.r.t.yyields: Jεq t (q(xt+1)) =J q−1(q(xt+1))−J q−1(yt). Using Assumption 2, we obtain: ∥Jεq t (q(xt+1))∥=∥J q−1(q(xt+1))−J q−1(yt)∥ ≤G∥q(x t+1)−y t∥ ≤ηG 2 ˆGF , where the last step uses the first estimate (i) proved above. Pr...

2022
[6]

We now control the norm of the bias∥bt∥ for any t

and the second one uses the definition of the diameter ofXsupposed to be finite. We now control the norm of the bias∥bt∥ for any t. Define for anyx∈ X the smoothed loss: ¯ℓt(x) :=E v∼U(B) [ℓt(x+δv)] where v is a random variable with uniform distributionU(B)on the unit ball B. It is known from Flaxman et al. [2005, Lemma 1] that the conditional expectation...

2005

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.

[1] [1]

Stochastic optimization under hidden convexity.SIAM Journal on Optimization, 35(4):2544–2571, 2025a

Ilyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden convexity.SIAM Journal on Optimization, 35(4):2544–2571, 2025a. Ilyas Fatkhullin, Niao He, Guanghui Lan, and Florian Wolf. Global solutions to non-convex functional constrained problems with hidden convexity.arXiv preprint arXiv:2511.10626, 2025b. Abraham D. Flaxman, Adam Tauman...

work page arXiv

[2] [2]

arXiv preprint arXiv:2402.06535 , year=

Tor Lattimore. Bandit convex optimisation.arXiv preprint arXiv:2402.06535,

work page arXiv

[3] [3]

Online Learning: A Modern Introduction Using Convex Optimization

Francesco Orabona. A modern introduction to online learning.arXiv preprint arXiv:1912.13213,

work page Pith review arXiv 1912

[4] [4]

Unveiling hidden convexity in deep learning: A sparse signal processing perspective.arXiv preprint arXiv:2603.23831,

Emi Zeger and Mert Pilanci. Unveiling hidden convexity in deep learning: A sparse signal processing perspective.arXiv preprint arXiv:2603.23831,

work page arXiv

[5] [5]

Using Assumption 2, we obtain: ∥Jεq t (q(xt+1))∥=∥J q−1(q(xt+1))−J q−1(yt)∥ ≤G∥q(x t+1)−y t∥ ≤ηG 2 ˆGF , where the last step uses the first estimate (i) proved above

(31) 22 Proof of (ii).Recall from (16) that for anyy=q(x), x∈ X, εq t (y) =q −1(y)−q −1(yt)−J q−1(yt)(y−y t).(32) Differentiating w.r.t.yyields: Jεq t (q(xt+1)) =J q−1(q(xt+1))−J q−1(yt). Using Assumption 2, we obtain: ∥Jεq t (q(xt+1))∥=∥J q−1(q(xt+1))−J q−1(yt)∥ ≤G∥q(x t+1)−y t∥ ≤ηG 2 ˆGF , where the last step uses the first estimate (i) proved above. Pr...

2022

[6] [6]

We now control the norm of the bias∥bt∥ for any t

and the second one uses the definition of the diameter ofXsupposed to be finite. We now control the norm of the bias∥bt∥ for any t. Define for anyx∈ X the smoothed loss: ¯ℓt(x) :=E v∼U(B) [ℓt(x+δv)] where v is a random variable with uniform distributionU(B)on the unit ball B. It is known from Flaxman et al. [2005, Lemma 1] that the conditional expectation...

2005