Solving Stochastic Root-Finding with adaptive d-ary search
Bibliographic record
Abstract
The most fundamental problem encountered in the field of stochastic optimization, is the Stochastic Root Finding (SRF) problem where the task is to locate an unknown point x* for which g(x*) = 0 for a given function g that can only be observed in the presence of noise [13]. The vast majority of the state-of-the-art solutions to the SRF problem involve the theory of stochastic approximation. The premise of the latter family of algorithms is to operate by means of so-called “small-step” processes that explore the search space in a conservative manner. Using this paradigm, the point investigated at any time instant is in the proximity of the point investigated at the previous time instant, rendering the convergence towards the optimal point, x*, to be sluggish. The unfortunate thing about such a search paradigm is that although g() contains information using which large sections of the search space can be eliminated, this information is unutilized. This paper provides a pioneering and novel scheme to discover and utilize this information. Our solution recursively shrinks the search space by, at least, a factor of 2d/3 at each epoch, where d ≥ 2 is a user-defined parameter of the algorithm. This enhances the convergence significantly. Conceptually, this is achieved through a subtle re-formulation of SRF problem in terms of a continuous-space generalization of the Stochastic Point Location (SPL) problem originally proposed by Oommen in [8]. Our scheme is based, in part, on the Continuous Point Location with Adaptive d-ary Search (CPL-AdS), originally presented in [12]. The solution to the CPL-AdS [12], however, is not applicable in our particular domain because of the inherent asymmetry of the SRF problem. Our solution invokes a CPL-AdS-like solution to partition the search interval into d subintervals, evaluates the location of the unknown root x* with respect to these sub-intervals using learning automata, and prunes the search space in each iteration by eliminating at least one partition. Our scheme, the CPL-AdS algorithm for SRF, denoted as SRF-AdS, is shown to converge to the unknown root x* with an arbitrary large degree of accuracy, i.e., with a probability as close to unity as desired. Unlike the classical formulation of the SPL problem proposed by Oommen et al [8], [12], in our setting, the probability, p, of the “environment” suggesting an accurate response is non-constant. In fact, the latter probability depends of the point x being examined and the region that is a candidate to be pruned. The fact that p is not constant renders the analysis much more involved than in [12]. The decision rules for pruning are also different from those encountered when p is constant [12].
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".