- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper considers the stochastic fixed-point approximation problem for non-expansive maps. Here, we are given some unknown map over some domain satisfying (hence non-expansive). The map can be accessed through an oracle returning a vector for a query which in expectation takes value (conditioned on previous queries). The goal is to return an approximately fixed point such that in a small number of iterations (for small constants ).
The problem is well studied. The goal of the paper is in addressing the following problem: approaches like Halpern's iteration even with strong map-value estimates may return a fixed point with large residual, meaning that even if the difference between the true map values and the estimates observed is small, say , in iterations the final output can be away from its mapped location. This is due to the next query being expressed as a function of the previous query input and its mapping (and some anchor point), not dependent on earlier information directly. Such methods work well with no error in the access oracle, but the noise can accumulate errors from earlier iterations (this is presented by the paper on a concrete example).
With varying parameter trade-offs this can be avoided with known techniques through considering the history of the process when a new query is defined (even with simple averaging, although not optimally). The papers contribution is in showing an approach only relying only on the last two queries (hence the one edge is enough in the title). Essentially, they define an altered Halpern's iteration, where based on the movement they clip or 'correct' the estimate of to be in an large box of and complete a Halpern iteration with these clipped estimates . They show that the method obtains a final residual guarantee of O(D/k)+M (k iterations, D radius, M maximum estimation error) matching whats achievable with correction based on the whole history.
As a drawback, the authors point at out that the algorithm might preserve an old mistake indefinitely (unlike say averaging). That, is the error is initially large and then it drops to 0 the algorithm still only guarantees its approximation based on that initial error. The authors present a modificated algorithm for -contractions (for ) where old errors decay geometrically with respect and the number of iterations.
I am not familiar with this part of the literature sufficiently to be able to judge the novelty of the technical sections/proofs and did not verify their correctness.
Critical strengths
The algorithms proposed by the authors are intuitive and simple.
Critical weaknesses
My greatest concern is presentation, to an extend that I can't recommend the paper for acceptance. The paper is very difficult to parse, certain sections read as mostly AI responses. Even the abstract is difficult to understand. The main body itself is more readable albeit not sufficiently. After the main body the text becomes substantially more confusing with the typical artifacts of under-edited AI scripts. The whole paper is heavily hindered by the over use of unecessary technical terminology not defined clearly in the paper (again, typical of current AI model responses).
Lastly, while only having to focus on the 'last edge' is certainly better then the whole history, the paper does very little to underpin the importance of the question. Their tests do not exhibit consistent gains of their last edge based approach over approaches looking at the whole history.
Questions for authors
I do not have questions.