Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider online convex optimization over unbounded domains with potentially heavy-tailed subgradient estimates as feedback. Precisely they assume that the p-th(\in(1,2]) moment of the subgradient is bounded. They propose an algorithm that with high probability has regret against any fixed comparator u of order O(|u|\sqrt{T}) where T is the horizon. Furthermore, the algorithm is parameter-free in the sense that it does not need to know the norm |u|. This algorithm relies on two novel regularizers that share similarities with the Huber loss. One to deal with the fact that the domain is unbounded and the other to handle the heavy-tailed subgradient.

strengths_and_weaknesses: Contributions:
-parameter-free algorithm for (1D) supexponential stochastic subgradient estimate, novelty: medium, relevance: high.
-parameter-free algorithm for heavy-tailed stochastic subgradient estimate, novelty: medium, relevance: high.

The paper is well-written, and the intuition, in particular, is clearly described. Maybe a small description of the role of \cA_1 and \cA_2 in Algorithm 1 could make the presentation clearer. The proofs seem correct. I did not read the appendix C, D, E. Note that the writing in the appendix could be improved, see specific comments. The considered setting and the obtained results may look a bit incremental but I think that the new regularizers and the associated analyses developed to overcome the technical difficulties are a valuable contribution.
questions: Specific comments: 

-L30: Since at since point the role of \epsilon is not clear why not hide it in the \tilde{O} notation?

-L81: log factors with respect to which quantities of the problem, i.e. not log factor of exp(T) ?

-L128: G is not defined?

-L199: At this point it is not completely clear why you need two algorithms \cA_1 and \cA_2.

-L201: Maybe you should give at least one of these algorithm in then appendix.

-L208: Does the result holds with probability one?

-L266: g_1

-L281: Algorithm 3, Require, g_t instead of \hat{g}_t?

-L284: Can you discuss how the obtained bound mathc or not the lower bound you mention in the introduction? Can you also provide the overall time/space complexity of Algorithm 4?

-L427: Theorem 1 and a dot is missing. 

-L428: R instead of \mathbb{R}

-L429: parenthesis and the statement of the lemma is not very clear.

-L432: punctuation of the equations is missing.

-L435: * not at the right place.

-L444: What is \bar{G}?

-L459: Can you detail how you applied Lemma 7 (choice of G and \bar{G}?

-L462: inf over y^\star is missing.

-L466, below: it seems that the term |A|^2uH[...] is repeated.

-L470: The first sentence is not clear.

-L483: The capital for Theorem, Section, Algorithm, Appendix is a bit inconsistent. 

-L542: w_t^2\epsilon_t^2
limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes new algorithms for online convex optimization over unbounded domains. The authors provide a parameter-free regret in high probability with heavy tails. First, they introduce a parameter-free algorithm for sub-exponential $g_t$ that achieves regret $O(\epsilon+|u|\sqrt{T})$ in high probability. Then, they extend to heavy-tailed $g_t$ by employing clipping on the heavy-tail. Last, they extend the algorithms to arbitrary dimensions.


strengths_and_weaknesses: Strengths:
1. The authors present a framework for building parameter-free algorithms that achieve high probability regret bounds for heavy-tailed subgradient estimates: high probability bounds were previously unavailable even for the restricted setting of bounded subgradient estimates.
2. They use Huber loss to construct a regularizer to ensure that it achieves low regret with a high probability in Section 4, and define another regularization function (from clipped $\hat{g}_t$) for the purpose of bias cancellation in Section 5. 
3. They also extend the work to arbitrary dimensions. 

Weaknesses:
1. The paper needs proof reading: For example: In page 2 contribution and Organization: We introduce a parameter-free algorithm for supexponential->sub-exponential.... ;  "Secondly, we extend to heavy tailed "..-> heavy-tailed 
2. In Section 4,   $|g_t|\leq b$ is mentioned. Note that, this b is $O(\sqrt{T})$. It is better to use $b_t$ because $b$ is used for constant value.
3. In theorem 4, $\tau$ may be unknown because it needs the knowledge of $\sigma$. Algorithm 2 could not achieve Thm 4's regret bound if we do not know $\tau$.
questions:  Is this possible to set a appropriate $\tau$ even if we did not have any information about $\sigma$?
limitations:  1. Same as weakness #3, $\tau$ may not be known, which could be a challenge when we run the algorithm 2.
 2. Two regularization functions introduce suboptimal logarithmic factors: The first one introduces a higher logarithmic dependence on T, and the second introduces a higher logarithmic dependence on |u|.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies online convex optimization over unbounded domains and aims to provide a high-probability regret bound given access to only potentially heavy-tailed gradient information. Towards this end, the authors propose several interesting ideas to overcome the anti-concentration issue due to the heavy-tailed noise. The basic idea is to add some regularization to cancel additional term introduced by the heavy-tailed gradient. The results are new and the techniques are interesting.
strengths_and_weaknesses: The paper is generally of good quality, including the writing and presentation logic. The results for unbounded online convex optimization are new, to the best of my knowledge. I have two concerns as stated below.

1) It is acknowledged that heavy-tailed issues and parameter-free bounds are interesting to the community. But does it have practical appeals when combining the two? The authors are encouraged to motivate their paper with a concrete and practical example in real applications, such that the readers will be more convinced to believe that we indeed need to pay some effort to study this problem. The current paper presentation does not consider this, which makes the reader think of "creating" this problem to solve.

2) The solution for this problem is kind of simple. I am not saying that simplicity is a drawback, but some discussions on whether the idea can be applied in broader applications/theoretical problems would strengthen the technical contribution. Additionally, the paper lacks discussions on the computational complexity -- for example, step 5 in Algorithm 1 is like a fixed-point equation, how to solve it in an efficient way? what's the overall computational complexity? All those stuff should be discussed in the paper.
questions: no
limitations: see comments in Strengths And Weaknesses
review_title: null

Meta-review: metareview: The paper makes an interesting contribution to the literature on online convex optimization with heavy-tailed stochastic gradient including infinite variance. While two reviewers (tcgd and WCJh) were positive about the paper, one reviewer (Wska) had concerns about the motivation and the technical contributions (commenting about it at a very-high level). 

In my own reading of the paper, I find it is well-written, highlighting the main challenges and the proof strategy they use to overcome the challenges. The regret bounds obtained are also optimal in a certain sense as they achieve lower bounds obtained recently. 

Hence it is recommended for acceptance at Neurips. 
confidence: Certain
Decision: Accept