{"id":"c6510969-53cc-401e-8898-4ccebc4aaaeb","arxiv_id":"2605.26373","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"OGD achieves O(sqrt(T)) regret on hidden-convex losses via sharper algorithmic equivalence under Hessian compatibility, with a matching lower bound and O(T^{3/4}) bandit extension.","lead":"This paper proves online gradient descent achieves optimal sqrt(T) regret on nonconvex losses that become convex after reparameterization, under a new necessary-and-sufficient geometric condition. A smart generalist might read it to see how simple gradient methods can match optimal rates on a broader class of online problems.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's identification of the Hessian compatibility condition as the weakest assumption matches the paper's own emphasis and lower-bound demonstration. Because the full argument is presented with both matching upper and lower bounds, the provisional UNVERDICTED verdict does not require adjustment.","tokens_in":1808,"tokens_out":239,"duration_ms":18989,"concrete_test":"Re-derive the O(sqrt(T)) regret bound from the discrete-time equivalence (without invoking the prior diagonal-Jacobian condition) and confirm the telescoping or potential-function argument closes with only O(1) additive terms independent of T.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that a sharper discrete-time equivalence shows OGD on hidden-convex losses achieves O(sqrt(T)) regret under the stated geometric/smoothness assumptions, now with the necessary-and-sufficient Hessian compatibility condition on the reparameterization. The paper supplies both the upper bound via the refined equivalence and an explicit Omega(T) lower-bound construction when compatibility fails. No internal inconsistency, unsupported step, or hidden assumption in the equivalence argument is apparent.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1898,"tokens_out":371,"duration_ms":22913,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[],"tokens_in":1379,"tokens_out":53,"duration_ms":8943,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","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.\n\nThe 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.\n\nThe 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.\n\nThis 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.","headline":"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.","tokens_in":2398,"tokens_out":358,"would_cite":true,"duration_ms":14527,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Online gradient descent achieves optimal O(sqrt(T)) regret on hidden-convex losses under a necessary Hessian compatibility condition.","keywords":["hidden-convex losses","online gradient descent","algorithmic equivalence","regret bounds","Hessian compatibility","bandit feedback","adversarial online learning"],"falsifier":"Construct a smooth reparameterization violating Hessian compatibility together with an adversarial sequence of hidden-convex losses and check whether OGD regret grows linearly.","tokens_in":2733,"feed_emoji":"📉","tokens_out":638,"duration_ms":22653,"temperature":0.7,"pith_summary":"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.","feed_headline":"OGD reaches optimal sqrt(T) regret on hidden-convex losses","feed_subtitle":"Sharper equivalence shows it matches convex rates under Hessian compatibility, with linear regret when the condition fails.","key_machinery":"Hessian compatibility condition on the reparameterization, which makes OGD on the hidden losses algorithmically equivalent to OMD on the convex losses.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["OGD achieves sqrt(T) regret on hidden-convex losses","Equivalence shows sqrt(T) regret under Hessian compatibility","OGD suffers Omega(T) regret without Hessian condition","Bandit OGD yields T^{3/4} regret on hidden-convex losses"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The nonlinear reparameterization must satisfy the Hessian compatibility condition.","fun_headline_variants_meta":{"raw":{"variants":["OGD achieves sqrt(T) regret on hidden-convex losses","Equivalence shows sqrt(T) regret under Hessian compatibility","OGD suffers Omega(T) regret without Hessian condition","Bandit OGD yields T^{3/4} regret on hidden-convex losses"]},"model":"grok-4.3","cost_usd":0.00471,"raw_usage":{"total_tokens":2377,"prompt_tokens":771,"num_sources_used":0,"completion_tokens":70,"cost_in_usd_ticks":47099500,"prompt_tokens_details":{"text_tokens":771,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1536,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":771,"tokens_out":70,"duration_ms":13443,"temperature":1.0,"reasoning_tokens":1536,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T22:11:09.433208+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Construct a smooth reparameterization violating Hessian compatibility together with an adversarial sequence of hidden-convex losses and check whether OGD regret grows linearly.","supporting_citations":[],"review_version":1}