First Order Stochastic Optimization with Oblivious Noise

Summary

This paper initiates the study of stochastic optimization with oblivious noise that might be biased and have unbounded variance, which is a generalization of the heavy-tailed noise setup. The key assumption regarding the oblivious noise is that it assumes a value of $0$ with a probability within the range of $0 \leq \alpha \leq 1$, which can be interpreted as the fraction of inliers. Notably, when $\alpha \leq 1/2$, it is proven to be information-theoretically impossible to find an approximate stationary point of the function. To address this challenge, the authors incorporate the concept of list-decoding into the framework of stochastic optimization, and focus instead on identifying a list of points where at least one of them is an approximate stationary point. Technically, this paper presents an equivalence between list-decodable stochastic optimization with oblivious noise and list-decodable mean estimation problem leveraging a technique known as noisy location estimation. The analysis of list-decodable stochastic optimization with oblivious noise is conducted by examining the list-decodable mean estimation problem.

Strengths

This paper investigates an important setting of stochastic optimization introduces a fresh perspective by introducing the concept of list-decodable stochastic optimization. The definition of this new framework is not only intuitive and well-motivated by practical problems but also exhibits elegance from a theoretical standpoint, given how weak the assumptions on the noise model are. The algorithms presented in the paper, along with their corresponding proofs, are intricate and highly nontrivial from a technical standpoint. Nevertheless, the authors have succeeded in presenting the analyses in a well-organized manner, ensuring that they are generally not hard to follow.

Weaknesses

1. As pointed out in the paper, an exponential dependence on $1/\eta$ is necessary in the list-size, which can mildly impact the overall appeal of the results. This dependency may introduce some considerations regarding scalability and practicality. 2. The framework presented in this paper is inherently abstract, and there is a lack of clarity concerning the algorithm's performance in concrete examples, including scenarios with more specific theoretical settings that incorporate additional assumptions, as well as practical problem domains.

Questions

Correspondingly, I have the following questions that could possibly make the results even stronger if addressed: 1. Can the exponential dependence on $\eta$ be mitigated by making slight adjustments to the original definition of list-decodable stochastic optimization? For instance, are there additional assumptions that can be incorporated or specific parameter regimes that can be adjusted to reduce this exponential dependency? 2. Are there more concrete applications of list-decodable stochastic optimization methods? 3. Minor comment: I saw the term "convex" in the caption of Algorithm 2. I assume this is a typo and convexity is not needed in the proof, right?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Not relevant in my opinion.

Summary

The paper presents an algorithm for first-order stochastic optimization where the algorithm has access to an oracle that returns a noisy version of the gradient of the objective function. The considered noise model includes two components: A bounded-variance observation noise (which is the typical well-studied type of noise), and oblivious outliers noise $\xi$ satisfying $Pr[\xi = 0] >= \alpha$. Furthermore, the distribution of the oblivious noise \xi does not need to be symmetric. It is shown that if the fraction of inliers is below 1/2, it is information-theoretically impossible to give a unique solution. This is why the authors consider a list-decodable learner where the learner returns a list of solutions, one of which is guaranteed to be good. The authors show that if the fraction of inliers is sufficiently close to 1, then the algorithm can recover a single solution.

Strengths

Designing learning algorithms which are robust against adversarial or semi-adversarial type of noise is very important. The setup that is considered in this paper is original (as far as I can tell).

Weaknesses

I found the paper to be generally not very well written. The notation is a bit confusing in several places (e.g., check the question regarding line 203 below), and the writing style can be sometimes too informal. One thing that I found crucially missing is the clear and formal statement of the problem and the clear statements of the assumptions. For example, what are the properties of the function $f(\gamma,x)$? The only property that I found is that $f(x) = E_{\gamma}[f(\gamma,x)]$ must be $L$-smooth. However, this is clearly not enough to even guarantee the existence of a stationary point. For example, consider $x\in \mathbb{R}$ (i.e., one dimension) and define $f(\gamma,x) = x$. In this case, we have $f(x) = x$ and hence $\nabla f(x) = 1$ fo all $x$ and there is no stationary point. Typos: - Page 4, line 175: "we can a generate list" -> "we can generate a list"

Questions

- What are the properties of the function $f(\gamma,x)$ which are needed for the main result to hold? - Page 4, line 203: Is $\xi$ in $\xi + y' + t$ the same as the $\xi$ in $\xi + y$, or is it an independent instance? It seems from the following discussion that the authors consider an independent instance. If this is the case, please write $\xi' + y' + t$. - Page 7, line 309: What is $L$? Is it the same as the $L$ of Section 2? But in Section 3 we don't have a parameter $L$ for location estimation. - There doesn't seem to be a proof for Claim 3.3 (even in the appendices).

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

1 poor

Contribution

2 fair

Limitations

No concerns regarding potential societal impact of this work.

Summary

The paper considers the problem of stochastic optimization with oblivious noise. Here, one receives noisy gradients of a non-convex function $f(x) = \mathbb{E} [f(x, \gamma)]$ (where $\gamma$ is bounded variance observational noise) and the noisy gradient samples are generated as follows $\nabla_x f(x, \gamma) + \xi$ where $\xi$ is generated independently of $\gamma$ and $x$ with the only restriction that $\mathbb{P} (\xi = 0) \geq \alpha$. The paper specifically focuses on the setting where $\alpha \ll 1 / 2$. Under such mild restrictions on $\xi$, it is impossible to recover a single point which is guaranteed to be near-stationary. However, in line with recent results on list-decodable robust estimation, the paper shows that one can recover a list of estimates one of which is approximately stationary. Technically, the paper builds on two recent results on robust estimation. The first is SEVER which is a robust stochastic estimation algorithm focusing on the setting when $\alpha \to 1$. In this setting, it is possible to leverage recent robust estimation algorithms to clean the observed gradients and recover a good approximation to the true gradient (up to the degree determined by $1 - \alpha$) and then utilize this approximate gradient to find a stationary point. The second is a recent line of work on list-decodable mean estimation. Here, one receives corrupted samples from a high-dimensional distribution where $\alpha$ fraction of points are from the true distribution and the goal is to estimate its mean. While producing a single estimate is impossible, these algorithms return a list of size $1 / \alpha$, one of which is guaranteed to be accurate. In this paper, the authors essentially extend the SEVER framework to the list-decodable setting. However, this requires some novel technical contributions. A naive implementation would lead to exponential growth in the number of estimates (a list of size $l$ would have $l / \alpha$ many elements in the next iteration if each of its elements were queried and updated with the $1 / \alpha$ resulting gradients). Instead the authors introduce a novel technical tool that they term location estimation which when given samples from $z + \xi$ and $z' + t + \xi$ for some unknown $t$ (and $z$ and $z'$ have bounded covariance) can estimate $t$. With this tool, the algorithm starts by first generating $1/\alpha$ gradients at $0$ and initializing $1 / \alpha$ candidates each corresponding to one of the estimates. Then, each element of the list, $x$, is queried to produce gradient estimates. The location estimate procedure is then run on gradient estimates from $x$ and $0$ to essentially estimate $\nabla f(x) - \nabla f(0)$. Finally, from this each candidate is updated by estimating $\nabla f(x)$ using the particular estimate of $\nabla f(0)$ it corresponds to. Overall, this is a really nice paper studying an interesting problem. My one concern is in the assumptions made in the paper. For instance, the assumptions don't capture the canonical estimation problem of list-decodable mean estimation. Here, one assumes that the true distribution has covariance bounded in spectral norm whereas this paper essentially assumes a bound on the expected squared length of a data point which could be larger by a factor of $d$. It would be interesting to see if these results could be extended to setting with weaker assumptions. Can we obtain similar results with $\mathbb{E} [(\nabla f(x, \gamma) - \nabla f(x)) (\nabla f(x, \gamma) - \nabla f(x))^\top] \prec \sigma^2 I$ as opposed to the stronger assumption in this paper of $\mathbb{E} [\|\nabla f(x, \gamma) - \nabla f(x)\|^2] \prec \sigma^2$ used here.

Strengths

See main review

Weaknesses

See main review

Questions

See main review

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This paper studies robust first order optimization in a challenging setting where noise may be unbounded, a setting that arises often for real world optimization problems. Because this problem is intractable in general, one needs to make plausible assumptions on the noise, that are realistic on one hand but allow for efficient analysis. The noise model proposed here allows for noise to be unbounded, and introduces two simple constraints: 1. The unbounded noise when computing a gradient is *oblivious* in the following sense: there are two noise components, one that is well-behaved (zero mean and bounded variation), and one that is unbounded but oblivious/indpendent of both the location in which gradient is computed and the value of the well-behaved part of the noise.</li> 2. We assume the unbounded noise has probability bounded away from 0 to be equal to zero (i.e., to not exist at all). It turns out that these two relatively weak conditions allow for efficient robust first order optimization. Specifically, these conditions allow for list-decodable robust optimization, where the goal is to output a list of candidate outputs where at least one should be a good approximation of the correct optimization outcome. The main technical result shows how to solve this problem by reducing it to list-decodable mean estimation, a problem that enjoyed substantial progress in recent years. The authors also show a reduction in the opposite direction. A substantial component in the technical analysis is a procedure that the authors develop for location estimation in an appropriate noisy setting.

Strengths

1. Interesting and important goal, of better understanding the beyond worst case landscape for (first order) optimization. 2. Writing is very clear and relatively easy to follow for me (a non-expert outsider). 3. The assumptions required for the analysis are weak and seemingly realistic.

Weaknesses

1. The technical novelty is perhaps somewhat limited, the work relies heavily on reductions to existing results in robust mean estimation.

Questions

Comment: my review is a low-confidence one (as a non expert in the field) and I may have missed central points in the paper, so may update the score after subsequent reviewers and authors discussions.

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.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

This paper introduces a new setup for stochastic optimization, where in addition to random observation noise, the stochastic gradient may be subject to independent oblivious noise. This noise might not have bounded moments and isn't necessarily centered. The authors propose a Noisy Location Estimation approach that estimates the gradient difference between two points, specifically \nabla f(x_t)-\nabla f(x_0). As such, they maintain robust estimations of the gradient at all points {x_t} as long as there is a reliable estimation of \nabla f(x_0).

Strengths

The new setup for oblivious noise introduced in the work is plausible, and the authors effectively discuss its relation to existing research. The Noisy Location Estimation proposed by the authors provides an innovative way to estimate gradient differences accurately, reducing the stochastic optimization problem to a mean estimation problem, which seems simpler in the setting. Also, as shown by the authors, the reverse of the reduction holds by simple arguments.

Weaknesses

The paper's presentation, particularly in the technical sections, lacks clarity. 1. Definitions should be more precise and self-contained. For instance, the work seems to require that oblivious noise be independent of the noisy gradient, but Definition 1.1 doesn't explicitly state this. In Definition 1.3, phrases like "sufficiently small constant" are too vague. 2. The methodology for mean estimation (Fact 2.1), isn't discussed in the main body. A brief discussion may be helpful. 3. The "Rejection Sampling" discussion on page 5 is difficult to follow and potentially misleading. From my understanding, the core intuition is to identify a large enough domain of size $i$, such that $i$ times the conditional expectation is robust and stable upon shifting the domain.

Questions

1. In Line 227, it appears that [i- 4 · 12, i + 4 · 12) almost fully contains [i - 4 · 12, -i + 4 · 12)]. If that's the case, why is there a need for a \cup operation? 2. In Section 5, why is the exponential dependence on 1/\eta for the size of the list unavoidable? 3. Is it a requirement for the Noisy Location Estimation that alpha > 0? I didn't delve into the proof details, but it seems that if you're considering the conditional expectation, it might not require alpha > 0. Can you clarify this?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

As discussed in Weakness.