Research map / Optimization / Nonconvex and smooth optimization
Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes optimization algorithms that use only an Order Oracle (comparisons of function values, with bounded noise) by embedding golden-ratio line search into coordinate descent, including the first accelerated order-oracle method (OrderACDM) and a stochastic order-oracle normalized-SGD method with asymptotic convergence.
Problem
Black-box optimization where only comparisons between objective function values (order access, possibly noisy) are available rather than the values themselves; prior order-oracle methods lack acceleration.
Approach
Integrate the Order Oracle into random coordinate descent via golden-ratio linear search so the search determines both step size and coordinate gradient; extend ACDM with a second linear search to obtain the first accelerated order-oracle method under strong convexity, and use a sign-based normalized SGD with random sphere directions for the stochastic order oracle.
Key results
- OrderRCD matches the iteration complexity of first-order RCD up to a log factor in non-convex, convex and strongly convex settings, with oracle complexity Õ(S_α F0/ε²) non-convex and Õ(S_α/μ log 1/ε) strongly convex.
- OrderACDM achieves linear rate (1 - sqrt(μ)/(2S_{α/2}))^N, i.e. oracle complexity Õ(S_{α/2}/sqrt(μ) log 1/ε), which the authors present as the first accelerated order-oracle method.
- In quadratic experiments with d=100, OrderACDM (with one golden-ratio search per iteration) outpaces GD, RCD and OrderRCD outperforms first-order RCD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OrderACDM instead of non-accelerated OrderRCD | Order Oracle optimization · Strongly convex optimization | oracle complexity: ˜O\left(\frac{S_\alpha}{\mu^{1-\alpha}}\log\frac{1}{\varepsilon}\right) -> ˜O\left(\frac{S_{\alpha/2}}{\sqrt{\mu^{1-\alp | Helped |
| Use one golden-ratio line search per iteration rather than two (ablation) | OrderACDM · Quadratic optimization experiment | convergence | Helped |
| Increase adversarial oracle noise level (ablation) | OrderRCD · Quadratic optimization experiment, d = 100 | convergence: ∆= {0.5, 0.1, 0.0001} | Hurt |
| Use OrderRCD rather than first-order RCD | Coordinate descent on the quadratic experiment · Quadratic optimization experiment | convergence | Helped |
| Use OrderACDM rather than non-accelerated GD, RCD, or OrderRCD | Coordinate descent on the quadratic experiment · Quadratic optimization experiment | convergence | Helped |
| Use two golden-ratio searches per iteration rather than one (ablation) | OrderACDM · Quadratic optimization experiment | convergence | Hurt |
Surprising findings
- OrderRCD even outperforms its first-order counterpart RCD in the quadratic experiments.
- Using the golden-ratio search twice per iteration in OrderACDM causes delayed momentum and lags behind ACDM; a single search works better in practice.
Limitations
- OrderACDM is not fully adaptive: it requires knowledge of the strong convexity constant and smoothness constants.
- Oracle complexity carries an extra logarithmic factor from golden-ratio search, and the accelerated result is only shown for strongly convex functions with zero noise.
- Experiments are limited to synthetic quadratic problems on a single small CPU machine.
Experimental setup
Benchmarks: randomly generated quadratic minimization problems (d=100)
Metrics: function value gap vs iterations wall-clock time
Baselines: RCD gradient descent Stochastic Three Points Method Saha et al. (2021) order-oracle method ACDM
Builds on: Nesterov (2012) random coordinate descent Nesterov and Stich (2017) accelerated coordinate descent Lee and Sidford (2013) ACDM Stochastic Three Points Method
Closest papers by meaning
- The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization (NeurIPS 2022 · similarity 0.91)
- The power of first-order smooth optimization for black-box non-smooth problems (ICML 2022 · similarity 0.89)
- A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles (ICML 2024 · similarity 0.88)
- A Study of First-Order Methods with a Deterministic Relative-Error Gradient Oracle (ICML 2024 · similarity 0.87)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.86)
- Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.