# Ruppert-Polyak averaging for Stochastic Order Oracle

arXiv: https://arxiv.org/abs/2411.15866 · HTML: https://mlsanity.com/paper/2411.15866/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 14 references that are in the map.
- First posted on arXiv 24 Nov 2024.

## Builds on (most cited first, 7 of 7)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points](https://mlsanity.com/paper/1711.05224/) (2017)
- [Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values](https://mlsanity.com/paper/2402.09014/) (2024)

## Abstract (arXiv)

Black-box optimization, a rapidly growing field, faces challenges due to limited knowledge of the objective function's internal mechanisms. One promising approach to address this is the Stochastic Order Oracle Concept. This concept, similar to other Order Oracle Concepts, relies solely on relative comparisons of function values without requiring access to the exact values. This paper presents a novel, improved estimation of the covariance matrix for the asymptotic convergence of the Stochastic Order Oracle Concept. Our work surpasses existing research in this domain by offering a more accurate estimation of asymptotic convergence rate. Finally, numerical experiments validate our theoretical findings, providing strong empirical support for our proposed approach.