acceptodds
Withdrawn from ICLR 2027

WHAT SHAPE SHOULD A RULE BE? A GAUGE-THEORETIC FOUNDATION FOR ADAPTIVE ONLINE OPTIMIZATION

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Adaptive first-order methods commit, each round, to a set of admissible step directions revised from past gradients; we ask what shape that set should take, and whether it must be an ellipsoid. We cast the proximal function as the squared gauge of a convex absorbing set Ct and prove a regret bound for any monotone sequence of such sets with strongly convex squared gauge. We give a rotated- ellipsoidal instance with an AdaGrad-type O(√T ) guarantee and a consistent data-driven basis estimator, and study polytopal methods (rotated hyperrectan- gles, adaptive facets) empirically. Rotated geometries converge markedly faster than axis-aligned baselines with a line search and early in neural-network training.

Primary area:
optimization
Keywords:
ADAPTIVE ONLINE OPTIMIZATION, Gauge theory, Mirror descent, Regret bound

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_xyy4OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper provides an apparently novel way to incorporate curvature adaptivity inside the distance generating function of Bregman-divergence based methods, by encoding the kernel as a squared gauge of a sequence of sets. The paper provides convergence theory for gauges that are strongly convex, but propose a "practical" method for polytopal gauges that are not strongly convex, without accompanying theory.

Critical strengths
  1. The idea appears truly unusual. Something we don't see a lot in ML, where all papers are "LLM LLM LLM Transformer Transformer Attention", or "yet another gradient step-size rule".
  2. The rotated ellipsoid method also appears unusual and new. I am not familiar with something like this in the literatrure.
  3. Experiments provide some evidence that the idea may be useful in practice. They are parameter-tuned, in contrast to what we see a lot in the literature, so at least for this small dataset and model the empirical performance appears be sound.
Critical weaknesses
  1. The claim that the literature dominantly uses ellipsoids is not true in general. Even the classical mirror descent does not use ellipsoids - it uses entropy-based Bregman distance. In general, Bregmal proximal methods are not ellipsoid based. More generally, the parameter-free methods use the so-called linearithmic regularizer, which is also not an ellipsoid. See [3,4].
  2. The use of Minkowski-functionals is not new for distances. See, for example, [1]. And the more general idea of using non-negative positively-homogeneous functions is not new in optimization. The classical (deterministic) optimization community came up with such methods too, see [2] for example.
  3. Since there is no theory for the polytopal method, I would expect it to be tested more extensively experimentally. Alternatively, bring the rotated ellipsoid method to the front, for which you do have theory. In either case, the paper as written requires a major revision.

Overall, appears the paper needs serious work before it is ready, and the authors need to familiarize themselves with the existing literature in both stochastic, online, and deterministic optimization before revising.


[1]: Faster Rates for Convex-Concave Games. Jacob Abernethy, Kevin A. Lai, Kfir Y. Levy, Jun-Kun Wang. COLT 2018. [2]: Generalized Bundle Methods. Antonio Frangion. SIAM Journal on Optimization 2018. [3]: Parameter-free Stochastic Optimization of Variationally Coherent Functions. Francesco Orabona, David Pal. Arxiv (2018) [4]: Online Learning Without Prior Information. Ashok Cutkosky, Kwabena Boahen. COLT 2017.

Questions for authors

NA

Reviewer_7fcNOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Summary

This paper generalized the quadratic norm geometry widely employed in adaptive OCO to gauge-based geometry. A general gauge-based regret bound is given and some algorithms are derived. Experiments demonstrate the performance of the approach.

Critical strengths

Strength

The idea of using gauge to generalize quadratic norm seems interesting.

Critical weaknesses

Weaknesses

The biggest problem is that the theoretical claim and algorithm design are detached. In particular, the interesting theory (Theorem 2) requires strict convexity of ψt=12γCt2\psi_t = \frac{1}{2}\gamma_{C_t}^2, but in the algorithm development, e.g., Line 245 , it is mentioned that the γCt\gamma_{C_t} used here is not differentiable and Theorem 2 does not apply. It's confusing since it means the central theory does not correspond to the algorithm. Instead, in the appendix a separate theorem is proven for the rotated ellipsoidal variant. The bound does not seem very different from AdaGrad. This way of writing can confuse the readers.

Given the above mismatch between theory and algorithm development, I recommend rejection.

Questions for authors

Questions

  1. Could you clarify the discrepancy between Theorem 2 and the online algorithms?
  2. OCO regret bounds hold in adversarial cases and do not often assume data distributions. Why is proposition 1 relevant?
Reviewer_9DwdOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper is supposed to investigate adaptive step method for online optimization.

Critical strengths

None

Critical weaknesses

Theorem 2 which is one of the 2 main contribution of the paper seems to be false.

Indeed, consider the 1D case, with C_1=[-1,1], and psi_1=x^2/2. Let f_1=0, phi(x)=(x-1)^2, x_1=0, x^=1 and eta=2. It is then easy to see that R_phi(1)=1/2, and the right-hand side of equation () in Theorem 2 is 1/4. This implies 1/2 \leq 1/4 which is obviously false.

Since the first theorem is false, and the paper is not properly written, I have not studied it in more details.

Questions for authors

Can the authors fix their Theorem 2 ?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.