Research map / Optimization / Nonconvex and smooth optimization
A Study of First-Order Methods with a Deterministic Relative-Error Gradient Oracle
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.
Analyzes projected gradient and conditional gradient methods under deterministic relative-error (norm-condition and coordinate-wise) gradient oracles for constrained smooth optimization, giving convergence guarantees across box, general convex, sign-preserving, and Euclidean-ball settings.
Problem
Constrained smooth optimization where gradients come from biased oracles with multiplicative (relative) error, as arises in gradient compression, quantization, and finite-difference derivative-free methods; prior guarantees were largely unconstrained or required PL/KL conditions.
Approach
Shows conditional gradient is invariant to relative error over boxes with coordinate-wise oracles (LMO depends only on sign), derives relative-error-dependent guarantees for erroneous CG and PG under general oracles, and introduces a rescaled CG variant that achieves a (1-ε)/(1+ε) relative guarantee for convex problems over balls and sign-preserving sets.
Key results
- On the box with a coordinate-wise erroneous oracle, the ECG generates the same iterates as exact CG for any ε (Theorem 4.2), so its guarantees are preserved.
- EPG on nonconvex box problems achieves min_t ||q_{t+1}+∇f(w_{t+1})||^2 ≤ 8L(f0-fopt)/T + ϵ with η=1/(3L) under a coordinate-wise oracle (Theorem 5.6 / Section 4.2).
- RECG achieves f(w̄_T) - θ f_opt ≤ 8L(R^2/θ)/(T+1) with θ=(1-ε)/(1+ε) for convex objectives over balls and sign-preserving sets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a coordinate-wise erroneous oracle instead of an exact gradient | ECG on the box · Box | convergence guarantee | No clear effect |
| Use a coordinate-wise erroneous oracle instead of an exact gradient | EPG on the box · Box, nonconvex objective | convergence guarantee | No clear effect |
| Use a general relative-error oracle instead of an exact gradient | ECG · General convex set, nonconvex objective | conditional-gradient optimality gap: −2ε/(1−ε)MR | Hurt |
| Use a general relative-error oracle instead of an exact gradient | ECG · General convex set, convex objective | suboptimality: 2εMR + 4LR2/(t+2) | Hurt |
| Use a general relative-error oracle instead of an exact gradient | EPG · General convex set, nonconvex objective | squared stationarity measure: 8L(f 0−fopt)/T + ϵ | Hurt |
| Use only gradient signs rather than gradient magnitudes | SCG · Box | convergence guarantee | No clear effect |
| Apply rescaling with θ = (1 − ε)/(1 + ε) | RECG with a general erroneous oracle · Euclidean ball, convex objective | suboptimality relative to θfopt: 8L(R2/θ)/(T + 1) | Helped |
| Use a coordinate-wise erroneous oracle on a sign-preserving set | RECG · Sign-preserving set, convex objective | suboptimality relative to θfopt: 8L(R2/θ)/(T + 1) | Helped |
Surprising findings
- Conditional gradient is fully robust to arbitrary relative error on box sets with a coordinate-wise oracle, since only the sign of the gradient matters for the linear minimization oracle.
- Under a general relative-error oracle, the convex projected gradient guarantee remains open without PL-type assumptions, whereas CG degrades only additively in ε.
Limitations
- Convergence rates for projected gradient on general convex constrained problems without PL assumptions remain unestablished.
- General-oracle guarantees for ECG and EPG depend on ε additively (through M and R), and the rescaled CG relative guarantee for general oracles requires a Euclidean ball.
- Analysis is deterministic; random or stochastic error oracles are left to future work.
Experimental setup
Metrics: suboptimality f(w_T)-f_opt stationarity gap / conditional gradient norm
Baselines: projected gradient with erroneous oracle Ajalloeian & Stich (2020) Condat et al. (2022)
Builds on: Frank-Wolfe method norm condition (Polyak, Carter) Ajalloeian & Stich 2020 biased gradient analysis descent lemma
Closest papers by meaning
- UnderGrad: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees (ICML 2022 · similarity 0.90)
- A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates (ICML 2017 · similarity 0.89)
- Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities (AAAI 2021 · similarity 0.89)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.88)
- A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles (ICML 2024 · similarity 0.87)
- Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values (NeurIPS 2024 · similarity 0.87)
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.