Noisy Pairwise-Comparison Random Search for Smooth Nonconvex Optimization

Omar Saadi; Qiuyi Zhang; Rayane Bouftini; Taha El Bakkali

REVIEW 3 major objections 3 minor 28 references

Noisy Pairwise-Comparison Random Search for Smooth Nonconvex Optimization

T0 review · 3 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A comparison-only random search can reach approximate first-order stationarity in smooth nonconvex ridge objectives with a number of noisy pairwise comparisons that scales with the intrinsic dimension k, not the ambient dimension d.

desk verdict The central O(k/ε²) squared-gradient claim is not supported by the paper's own lemmas; the paper is promising but needs a major fix before it can be cited. read the letter →

arxiv 2601.21166 v2 pith:5ATCG3ST submitted 2026-01-29 math.OC

Taha El Bakkali , Rayane Bouftini , Qiuyi Zhang , Omar Saadi This is my paper

classification math.OC MSC 90C5690C26

keywords noisypairwisecomparisonsrandomsearchnonconvexoptimizationintrinsicdimensionactivesubspacederivative-freeduelingstationarity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies minimizing smooth nonconvex functions when the only feedback is a noisy pairwise comparison ('is candidate A better than candidate B?'). It introduces NCRS, a direct-search method that samples a random direction and accepts or rejects the step based on one comparison. For objectives of the form f(x)=g(Ax) with a k-dimensional active subspace, the paper proves that NCRS reaches ε-stationarity with O(k/(p²ε²)) comparisons under a uniform-margin noise model, and that a confidence-weighted majority-vote variant reaches ε-stationarity with O(k²/ε⁴) total comparisons under a tie-aware confidence model. The point is that comparison-based methods, despite receiving only one bit per query, can escape dependence on the ambient dimension d when the objective has low intrinsic structure. The paper validates the direction experimentally on language-model fine-tuning and preference-based reinforcement learning.

What carries the argument

The orthogonal projector P=A^T(AA^T)^{-1}A onto the active subspace range(A^T). Its role is to show that the accept/reject decision for f(x)=g(Ax) depends only on Ps_t; since E||Ps_t||² = tr(P) = k, all d-dimensional Gaussian moments in the analysis collapse to k. The proof is carried by a one-step descent inequality for the improve-or-stay update, summed with step size α_t=α0/√(kT); in the confidence model, Bernstein's inequality on the aggregated vote supplies the exponential error control.

What would settle it

On a synthetic ridge family f(x)=||Ax−b||² with fixed k and growing d, run NCRS with the paper's true-k schedule and measure (1/T)Σ||∇f(θ_t)||². If the average squared gradient does not decay as O(√(k/T)) with a prefactor independent of d, Theorem 2.2 fails. A second, more subtle check: run the same algorithm with a k-agnostic schedule (e.g., α_t=1/√t); if the rate then degrades with d, the claim that NCRS adapts without knowing k is refuted.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that accept-or-stay random search driven by a single noisy comparison inherits the intrinsic dimension of a ridge objective. Because f(x+αs) = g(Ax+αAPs) = f(x+αPs) when f(x)=g(Ax), the comparison and the accept/reject decision depend only on the projected direction Ps; the algorithm therefore behaves as a random line search on the k-dimensional active subspace. The one-step descent inequality p α sqrt(2/π) E||∇f(θ_t)||² ≤ E[f(θ_t)-f(θ_{t+1})] + L_f k α_t²/2 turns this into a stationarity bound whose dominant term is O(√(k/T)). For the confidence oracle, the same inequality holds with a majority vote, and the wrong-decision probability decays li

Load-bearing premise

The load-bearing premise is that the optimizer knows the intrinsic dimension k (and, in the uniform-margin rate, the horizon T) so it can set the step sizes α_t=α0/√(kT) and the vote size N=O(k/ε²); without that knowledge, the paper does not establish the stated O(k/ε²) and O(k²/ε⁴) rates.

Editorial extensions

If this is right

For a smooth nonconvex ridge objective with a k-dimensional active subspace, ε-first-order stationarity is achieved with O(k/(p²ε²)) comparisons; in the deterministic case p=1/2 this is O(k/ε²), independent of d.
Under the tie-aware confidence oracle, the same guarantee holds with O(k²/ε⁴) total comparisons once the vote size is at least O(L k/ε²), even though the oracle is allowed to become uninformative at near-ties.
A bounded nuisance gradient outside the active subspace (size τ, living in an m-dimensional subspace) adds only a τ√m/p term, so the stationarity guarantee degrades gracefully under misspecification rather than collapsing.
The empirical results on masked language modeling fine-tuning show both NCRS and the two-point baseline RSGF improving as intrinsic dimension drops, with NCRS the more sensitive of the two; the paper interprets this as evidence for the k-dependent convergence theory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's proved schedules require k (and, in Theorem 2.2, T) as inputs, even though the algorithm itself does not observe k; a parameter-free version that estimates k online is the natural next step and is not supplied here.
Because the descent analysis only uses E||Ps_t||²=tr(P)=k and the Gaussian identity E|⟨∇f,s_t⟩|=sqrt(2/π)||∇f||, the same rate should hold for any direction distribution with those moments; this suggests compressed or adaptive sampling directions could reproduce the guarantee with fewer random bits.
A controlled synthetic experiment on f(x)=||Ax−b||² with fixed k and varying d would separate the d-independence claim from the real-model confounds in the paper's experiments; the theory predicts flat iteration counts as d grows.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Thanks for the notes. I read the paper alongside your report, and I think the stress-test note lands harder than the reader's own conditional verdict. The two are related, but the norm-vs-squared issue is the load-bearing one.

What's genuinely here: NCRS is a clean idea, and the ridge model with active subspace k is the right way to get dimension-independent rates for comparison-based random search. The descent lemma (Lemma 2.1) is correct, as far as I can tell, and the proof is standard but careful. The tie-aware confidence oracle (Assumption 1.2) is a useful addition, and the majority-vote analysis is a reasonable attempt to handle gap-dependent noise. The empirical section is suggestive but not reproducible from the preprint — no code or data.

The problem: every headline theorem is written for the averaged squared gradient E||∇f||², but the lemmas only control E||∇f||. In Lemma 2.1 the proof uses E|⟨∇f, s⟩| = √(2/π)||∇f||, so averaging gives (1/T)Σ E||∇f_t|| = O(√(k/T)). Cauchy–Schwarz goes the wrong way: a bound on the average norm does not imply a bound on the average squared norm. So Theorem 2.2's O(k/(p²ε²)) comparison bound for E||∇f||² ≤ ε is not established. If the intended stationarity measure is E||∇f|| ≤ ε, the rate is right and standard. The same mismatch recurs in Section 3: Lemma 3.1 as printed states a squared-norm bound but its proof only yields the norm; Lemma 3.3 bounds the norm; Proposition 3.4 then mixes them and the (1−γ) coefficient is off — should be (1−2γ) if the lemmas were in the norm. This is fixable, but not by a typo: the theorems, Table 1, and abstract need to be restated.

On the adaptation claim: the step-size schedule α0/√(kT) requires knowing k and T, so the claim that NCRS adapts without knowing k is overstated as written. A doubling trick might fix it, but it's not in the paper.

So the paper is not ready as is. But it's worth engaging: the model is natural, the descent analysis is mostly sound at the norm level, and the corrections seem within reach. I'd send it to peer review with the clear expectation of a major revision rather than desk-reject. I wouldn't cite it yet.

Referee Report

3 major / 3 minor

Summary. The paper proposes Noisy-Comparison Random Search (NCRS), a direct-search method that uses one noisy pairwise comparison per iteration, and a variant with a confidence-weighted majority vote for a gap-dependent comparison oracle. For smooth nonconvex objectives with a k-dimensional active subspace, it claims that NCRS attains averaged squared-gradient stationarity with O(k/(p^2 ε^2)) comparisons under a uniform-margin oracle, and that the vote variant attains O(k^2/ε^4) total comparisons under a confidence model. The paper also includes a nearly-ridge robustness extension, a comparison with existing methods, and experiments on language-model fine-tuning and preference-based RL.

Significance. If the stated rates were correct, this would be a notable advance: it would give the first intrinsic-dimension dependence for noisy comparison-based nonconvex optimization and would justify a simple, gradient-free method on low-rank objectives. The algorithmic idea is clean, and the nearly-ridge model is a reasonable way to capture misspecification. However, the manuscript currently proves only a first-order stationarity bound in the gradient norm, not the squared norm used in the theorems and in Table 1. The mismatch is systematic and affects the abstract, the main theorems, the corollaries, and the empirical framing; the stated O(k/(p^2 ε^2)) and O(k^2/ε^4) rates for E||∇f||^2 are not supported by the analysis.

major comments (3)

[Section 2, Lemma 2.1 / Theorem 2.2; Appendix C] The proof of Lemma 2.1 establishes p α sqrt(2/π) E||∇f(θ_t)|| ≤ E[f(θ_t)-f(θ_{t+1})] + L_f k α_t^2/2. The key identity is E|⟨∇f(θ_t), s_t⟩| = sqrt(2/π)||∇f(θ_t)||, not a squared norm. Averaging with α_t = α_0/√(kT) gives (1/T)Σ E||∇f(θ_t)|| = O((1/p)√(k/T)), i.e., stationarity in the norm sense. Theorem 2.2 states (1/T)Σ E||∇f(θ_t)||^2 ≤ ε at T=O(k/(p^2 ε^2)); this does not follow. The abstract and Table 1 inherit the same unsupported claim. The statements must be corrected to E||∇f||≤ε or a separate argument for the squared-norm measure must be supplied.
[Section 3, Lemma 3.1, Lemma 3.3, Proposition 3.4] There is an algebraic error in the combination of Lemmas 3.1 and 3.3. Lemma 3.1 contributes -α_t/√(2π) E||∇f(θ_t)||, while Lemma 3.3 contributes +γ_{N,r} α_t √(2/π) E||∇f(θ_t)|| = 2γ_{N,r} α_t/√(2π) E||∇f(θ_t)||. The combined coefficient is therefore (1-2γ_{N,r}), not (1-γ_{N,r}). Proposition 3.4, Theorem 3.5, and Remark 3.6 use the incorrect coefficient; in particular, choosing γ_{N,r} ≤ 1/2 does not guarantee a positive descent coefficient, and the claimed O(k^2/ε^4) complexity in Remark 3.6 is not established.
[Section 2.1 and Remark 3.6; adaptation claim] Theorem 2.2 requires the step size α_t = α_0/√(kT), and Remark 3.6 chooses α and N using k (and L_f, Δ_f). Algorithm 1 and Algorithm 2 do not receive k as an input, so the statement that NCRS adapts 'despite never observing A or the intrinsic dimension k' is not supported by the theorems. If k is unknown, the stated k-dependent complexity is not achieved by the algorithm as written. The authors should either state that k and T are known to the method, provide a parameter-free or adaptive schedule that preserves the k-dependence, or substantially soften the adaptation claim.

minor comments (3)

[Throughout] Cross-references are inconsistent: Lemma 2.1 is called 'Theorem 2.1' in the text following it and in Appendix C; Proposition 2.4 is called 'Theorem 2.4' in Appendix D; Section 3 has similar mismatches. Please unify the numbering.
[Table 1 and abstract] The metric in Table 1 is E||∇f||^2, but the analysis supports E||∇f||. If the authors correct the stationarity measure, the table and abstract should be updated accordingly; the current presentation is internally inconsistent.
[Remark 2.3] The remark states T=O(k/(p^2 ε^2)) for E||∇f||^2 ≤ ε, but the displayed inequality in Theorem 2.2 has the form O((1/p)√(k/T)). Please make the hidden constants and the norm/squared-norm distinction explicit.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: NCRS's convergence analysis is self-contained; the only author-overlapping citation (GLD) is background, and the k-dependent rates come from assumptions, not fitted inputs.

full rationale

The derivation chain is self-contained. Lemma 2.1 (Appendix C) proves a one-step descent inequality by conditioning on theta_t, lower-bounding the improvement via Assumption 1.1, and using the Gaussian identity E|⟨∇f(θ_t),s_t⟩| = sqrt(2/π)‖∇f(θ_t)‖; the k-dependence enters through E‖Ps_t‖² = tr(P) = k, an honest computation with the active-subspace projector. Theorem 2.2 then averages this inequality with α_t = α0/√(kT); no coefficient is fitted to the final epsilon and no oracle constant is tuned to produce the stated rate. Section 3 follows the same structure: Lemmas 3.1-3.3 bound the true-improvement and ranking-error terms under Assumption 1.2, and Theorem 3.5/Remark 3.6 aggregate them; the NT = O(k²/epsilon⁴) bound follows from the assumed local growth rho(t) ≥ ct, the second-moment bound, and Bernstein's inequality, not from an ansatz imported by citation. The only author-overlapping citation is GLD [5] (Qiuyi Zhang is a co-author), used in the introduction and Table 1 as conceptual background: 'Methods like Gradientless Descent (GLD) [5] use line search to automatically find the right step size to exploit the inherent optimization dimension.' None of NCRS's convergence theorems invokes GLD's convex result; the self-citation is therefore not load-bearing. Two caveats belong to correctness risk, not circularity: (i) the stated step sizes α_t = α0/√(kT) and vote size N require k and T as inputs, so the paper's claim that NCRS adapts despite never observing A or the intrinsic dimension k is stronger than the implementable algorithm supports; (ii) Lemma 2.1's proof bounds the gradient norm E‖∇f‖, whereas Theorems 2.2/3.5 and Table 1 are written with E‖∇f‖²; a norm bound does not imply the squared-norm bound by Jensen or Cauchy-Schwarz, so the squared-stationarity statements as printed are not established by the displayed inequalities. These are proof and implementation gaps, not reductions of the result to its own inputs.

Assumptions & free parameters 1 free parameters · 7 assumptions · 0 invented entities

The central claims rest on the stated oracle assumptions, the ridge/nearly-ridge structural assumption, and standard smoothness/Gaussian/Bernstein tools. There are no fitted parameters whose values are tuned to produce the rates, but the step-size schedule requires knowledge of the intrinsic dimension, which is a load-bearing practical assumption.

free parameters (1)

Step-size scale α0
Chosen by the user in Theorem 2.2 and Theorem 3.5; the optimal choice α0=√(2Δf/Lf) depends on the unknown function gap. It is a hand-chosen algorithm constant, not fitted to data, but it affects the constant in the convergence bound.

assumptions (7)

domain assumption Assumption 1.1: uniform-margin comparison oracle with advantage p≤1/2 for all pairs
Used in Lemma 2.1 to guarantee accept probability at least 1/2+p on improvements; central to Theorem 2.2.
domain assumption Assumption 1.2: confidence oracle with E[sign(Δ)R̃]≥ρ(|Δ|), E[R̃²]≤Cρ(|Δ|), and ρ(t)≥ct near 0
Used throughout Section 3 for the confidence-weighted vote; the linear lower bound on ρ is needed for the 1/N term in Lemma 3.3.
domain assumption Exact ridge structure f(x)=g(Ax) with rank(A)=k
Yields ∇f(x)∈range(A^T) and f(x+αs)=f(x+αPs), enabling the k-dependence; the nearly-ridge extension relaxes this but retains a low-dimensional nuisance subspace.
standard math f is L_f-smooth and bounded below
Standard smoothness is used in all descent inequalities; boundedness below is used to telescope the expected function differences.
standard math Gaussian directional sampling and Isserlis/Wick moment identities
Used to compute E||Ps||²=k and the higher moment bounds in Appendix F.
standard math Bernstein inequality for bounded random variables
Used to control the majority-vote error probability in Lemma 3.2.
ad hoc to paper Step-size schedule α_t=α0/√(kT) can be set with knowledge of k and T
The convergence theorems rely on this schedule; the paper claims NCRS does not observe k, but the schedule requires k as an input.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Noisy Pairwise-Comparison Random Search for Smooth Nonconvex Optimization." pith.science (2026). https://pith.science/paper/5ATCG3ST

@misc{pith2026260121166,
  author       = {Pith},
  title        = {Pith review of: Noisy Pairwise-Comparison Random Search for Smooth Nonconvex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5ATCG3ST}},
  note         = {Machine review of arXiv:2601.21166}
}

abstract

We study smooth nonconvex optimization using only noisy pairwise comparisons, without access to gradients or function values. We propose Noisy-Comparison Random Search (NCRS), a simple direct-search method that samples random directions and performs accept/reject updates from comparison feedback. Under a low-dimensional active-subspace structure, NCRS adapts to the intrinsic dimension $k\le d$ rather than the ambient dimension $d$. For a uniform-margin comparison oracle with advantage $p$, NCRS achieves $\epsilon$-first-order stationarity with comparison complexity $\mathcal{O}(k/(p^2\epsilon^2))$. We also introduce a gap-dependent confidence model, where comparison reliability decreases as the objective-value gap between the two candidates becomes small, and analyze a confidence-weighted voting variant of NCRS. For this oracle, the method achieves $\epsilon$-first-order stationarity with total comparison complexity $\mathcal{O}(k^2/\epsilon^4)$. These results provide intrinsic-dimension convergence guarantees for noisy comparison-based random search in smooth nonconvex optimization.

Figures

Figures reproduced from arXiv: 2601.21166 by the authors.

**Figure 1.** Zeroth-order methods adapt to intrinsic dimension. Number of iterations required to reach a fixed target accuracy across different language models fine-tuning settings with decreasing intrinsic dimension. Shaded areas represent the 95% CI over 5 runs. We investigate the effect of intrinsic dimension on convergence using medium-sized masked language models. Despite having hundreds of millions of parameters, these mod… view at source ↗

**Figure 2.** Environments. We evaluate preference-based reinforcement learning algorithms on six locomotion tasks [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

**Figure 3.** Comparison between preference learning algorithms on DM Control Suite tasks. Results show the mean ground truth reward and standard error (y-axis) over 600 episodes (x-axis) for 5 random seeds where each algorithm collects 64 trajectories per episode. budgets, we evaluate them under the same query budget, with additional hyperparameter details found in Appendix B.2. In [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Learning rate sweep. Validation loss for different models on the MRPC task for SGD and NCRS. B.2 Preference-Based RL Policies are parametrized by a neural network with two hidden layers of 256 units and tanh activations. The network outputs the mean of a Gaussian distr…

**Figure 5.** Figure 5: 2D parameter sweep. Validation loss for different models on the MRPC task for RSGF with varying learning rate α and perturbation µ. C Convergence analysis of NCRS algorithm Lemma C.1 (Theorem 2.1). Assume that f admits a ridge representation f(x) = g(Ax) for some matri…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

28 extracted references · 6 linked inside Pith

[1]

Intrinsic dimensionality explains the effectiveness of language model fine-tuning

Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. InProceedings of the 59th annual meeting of the association for computational linguistics and the 11th international joint conference on natural language processing, pages 7319–7328, 2021

2021
[2]

Dueling optimization with a monotone adversary

Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, and Yuanyuan Yang. Dueling optimization with a monotone adversary. InInternational Conference on Algorithmic Learning Theory, pages 221–243. PMLR, 2024

2024
[3]

Deep reinforcement learning from human preferences.Advances in neural information processing systems, 30, 2017

Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences.Advances in neural information processing systems, 30, 2017

2017
[4]

Stochastic first-and zeroth-order methods for nonconvex stochastic programming.SIAM journal on optimization, 23(4):2341–2368, 2013

Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming.SIAM journal on optimization, 23(4):2341–2368, 2013

2013
[5]

Gradientless descent: High-dimensional zeroth-order optimization

Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gradientless descent: High-dimensional zeroth-order optimization. InInternational Conference on Learning Representations, 2020

2020
[6]

Direct language model alignment from online ai feedback.arXiv preprint arXiv:2402.04792, 2024

Shangmin Guo, Biao Zhang, Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Rame, Thomas Mesnard, Yao Zhao, Bilal Piot, et al. Direct language model alignment from online ai feedback.arXiv preprint arXiv:2402.04792, 2024. 13

arXiv 2024
[7]

Query complexity of derivative-free optimization.Advances in Neural Information Processing Systems, 25, 2012

Kevin G Jamieson, Robert Nowak, and Ben Recht. Query complexity of derivative-free optimization.Advances in Neural Information Processing Systems, 25, 2012

2012
[8]

Margin matching preference optimization: Enhanced model alignment with granular feedback.arXiv preprint arXiv:2410.03145, 2024

Kyuyoung Kim, Ah Jeong Seo, Hao Liu, Jinwoo Shin, and Kimin Lee. Margin matching preference optimization: Enhanced model alignment with granular feedback.arXiv preprint arXiv:2410.03145, 2024

arXiv 2024

Show all 28 references

[9]

Kingma and Jimmy Ba

Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors,ICLR (Poster), 2015

2015
[10]

B-pref: Benchmarking preference- based reinforcement learning.arXiv preprint arXiv:2111.03026, 2021

Kimin Lee, Laura Smith, Anca Dragan, and Pieter Abbeel. B-pref: Benchmarking preference- based reinforcement learning.arXiv preprint arXiv:2111.03026, 2021

2021 arXiv
[11]

Fine-tuning language models with just forward passes.Advances in Neural Information Processing Systems, 36:53038–53075, 2023

Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes.Advances in Neural Information Processing Systems, 36:53038–53075, 2023

2023
[12]

Direct preference optimization: Your language model is secretly a reward model

Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in neural information processing systems, 36:53728–53741, 2023

2023
[13]

Dueling convex optimization

Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 9245–9254. PMLR, 18–24 Jul 2021

2021
[14]

Faster convergence with multiway preferences

Aadirupa Saha, Vitaly Feldman, Yishay Mansour, and Tomer Koren. Faster convergence with multiway preferences. InInternational Conference on Artificial Intelligence and Statistics, pages 433–441. PMLR, 2024

2024
[15]

Dueling convex optimization with general preferences

Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization with general preferences. InForty-second International Conference on Machine Learning, 2025

2025
[16]

Proximal policy optimization algorithms.arXiv preprint arXiv:1707.06347, 2017

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms.arXiv preprint arXiv:1707.06347, 2017

2017 arXiv
[17]

Zeroth-order optimization meets human feedback: Provable learning via ranking oracles

Zhiwei Tang, Dmitry Rybin, and Tsung-Hui Chang. Zeroth-order optimization meets human feedback: Provable learning via ranking oracles. InThe Twelfth International Conference on Learning Representations, 2024

2024
[18]

Deepmind control suite

Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint arXiv:1801.00690, 2018

2018 arXiv
[19]

Llama 2: Open foundation and fine-tuned chat models.arXiv preprint arXiv:2307.09288, 2023

Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models.arXiv preprint arXiv:2307.09288, 2023

2023 arXiv
[20]

dm control: Software and tasks for continuous control.Software Impacts, 6:100022, 2020

Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, Nicolas Heess, and Yuval Tassa. dm control: Software and tasks for continuous control.Software Impacts, 6:100022, 2020. 14

2020
[21]

GLUE: A multi-task benchmark and analysis platform for natural language understanding

Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Tal Linzen, Grzegorz Chrupa la, and Afra Alishahi, editors,Proceedings of the 2018 EMNLP Workshop Bla...

2018 doi
[22]

Preference-based optimization from noisy pairwise comparisons.arXiv preprint arXiv:2512.18511, 2025

Siyi Wang, Zifan Wang, and Karl Henrik Johanssson. Preference-based optimization from noisy pairwise comparisons.arXiv preprint arXiv:2512.18511, 2025

2025
[23]

Explicit and non-asymptotic query complexities of rank-based zeroth-order algorithms on smooth functions.arXiv preprint arXiv:2512.16200, 2025

Haishan Ye. Explicit and non-asymptotic query complexities of rank-based zeroth-order algorithms on smooth functions.arXiv preprint arXiv:2512.16200, 2025

2025
[24]

Zeroth-order policy gradient for reinforcement learning from human feedback without reward inference

Qining Zhang and Lei Ying. Zeroth-order policy gradient for reinforcement learning from human feedback without reward inference. InThe Thirteenth International Conference on Learning Representations, 2025. 15 A Preliminary Lemma A.1.Let f : Rd →R be differentiable and let k∈ {...

2025
[25]

(Gradient lives in a fixed k-subspace)There exists a linear subspace V⊂R d with dim(V) =ksuch that: ∀x∈R d,∇f(x)∈V
[26]

(2) ⇒ (1).Let x∈R d

(Ridge representation)There exist a full row-rank matrix A∈R k×d and a differentiable functiong:R k →Rsuch that: ∀x∈R d, f(x) =g(Ax), Proof. (2) ⇒ (1).Let x∈R d. We have ⟨∇f (x), v⟩= 0 for all v∈Ker (A). This implies that ∇f(x)∈range(A ⊤) =Ker(A) ⊥,and we have dim(range(A ⊤)) ...
[27]

(Gradient leakage outside a k-subspace)There exist a k-dimensional subspace V⊂R d and its orthogonal projectorPsatisfying: ∀x∈R d,∥(I−P)∇f(x)∥ 2 ≤τ
[28]

prefer y over x

(Nearly-ridge representation with controlled leakage)There exist a full row-rank matrix A∈R k×d, a differentiable function g : Rk →R , and a differentiable residual η : Rd →R such that, letting P denote the orthogonal projector onto V := range(A⊤), we have: ( ∀x∈R d, f(x) =g(A...

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Intrinsic dimensionality explains the effectiveness of language model fine-tuning

Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. InProceedings of the 59th annual meeting of the association for computational linguistics and the 11th international joint conference on natural language processing, pages 7319–7328, 2021

2021

[2] [2]

Dueling optimization with a monotone adversary

Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, and Yuanyuan Yang. Dueling optimization with a monotone adversary. InInternational Conference on Algorithmic Learning Theory, pages 221–243. PMLR, 2024

2024

[3] [3]

Deep reinforcement learning from human preferences.Advances in neural information processing systems, 30, 2017

Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences.Advances in neural information processing systems, 30, 2017

2017

[4] [4]

Stochastic first-and zeroth-order methods for nonconvex stochastic programming.SIAM journal on optimization, 23(4):2341–2368, 2013

Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming.SIAM journal on optimization, 23(4):2341–2368, 2013

2013

[5] [5]

Gradientless descent: High-dimensional zeroth-order optimization

Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gradientless descent: High-dimensional zeroth-order optimization. InInternational Conference on Learning Representations, 2020

2020

[6] [6]

Direct language model alignment from online ai feedback.arXiv preprint arXiv:2402.04792, 2024

Shangmin Guo, Biao Zhang, Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Rame, Thomas Mesnard, Yao Zhao, Bilal Piot, et al. Direct language model alignment from online ai feedback.arXiv preprint arXiv:2402.04792, 2024. 13

arXiv 2024

[7] [7]

Query complexity of derivative-free optimization.Advances in Neural Information Processing Systems, 25, 2012

Kevin G Jamieson, Robert Nowak, and Ben Recht. Query complexity of derivative-free optimization.Advances in Neural Information Processing Systems, 25, 2012

2012

[8] [8]

Margin matching preference optimization: Enhanced model alignment with granular feedback.arXiv preprint arXiv:2410.03145, 2024

Kyuyoung Kim, Ah Jeong Seo, Hao Liu, Jinwoo Shin, and Kimin Lee. Margin matching preference optimization: Enhanced model alignment with granular feedback.arXiv preprint arXiv:2410.03145, 2024

arXiv 2024