Research map / Optimization / Nonconvex and smooth optimization
A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles
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.
Shows a black-box reduction that turns any convex optimization first-order algorithm with exact oracle information into one that works with eta-approximate function/subgradient oracles, via online construction of Lipschitz (and smooth, via localized randomized smoothing) convex extensions of the inexact information, extended to approximate separation oracles.
Problem
Convex optimization (possibly nonsmooth, with structured ground sets such as mixed-integer) where first-order oracles return only approximate function values and subgradients; existing analyses cover only specific algorithms like (accelerated) gradient descent.
Approach
Given any exact first-order algorithm, feed it online-constructed first-order pairs (via a max-of-affine-functions extension with shifts, and for smooth objectives localized randomized smoothing) that are exactly consistent with some Lipschitz (or smooth) convex function F uniformly close to f; the algorithm then effectively optimizes F, treated as a black box.
Key results
- For Lipschitz convex functions, the transfer yields error O(MR/sqrt(T)) + O((M R+eta)/sqrt(T)) + 2T*eta for subgradient methods, and O(eps) accuracy with eta = eps^3/(M^2R^2), T = M^2R^2/eps^2.
- For smooth objectives, applying the transfer to accelerated methods yields error O(alpha R^2 sqrt(d)/T^1.5 + eta T), recovering a significant part of acceleration rather than full Nesterov rate.
- Cutting-plane methods with inexact oracles achieve O(eps) error with eta = O(eps/(poly(d) log(MR/eps))) and T = O(poly(d) log(MR/eps)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an η-approximate first-order oracle instead of exact first-order information | Any first-order algorithm for Lipschitz convex objectives · Convex optimization, Lipschitz objectives | optimization error: err(T, M', R) + 4ηT | Hurt |
| Use an η-approximate first-order oracle instead of exact first-order information | Any first-order algorithm for smooth convex objectives · Convex optimization, smooth objectives | optimization error: err(T, M', α', R) + 5 η · (T+2) | Hurt |
| Use the transfer wrapper with η-approximate information | Subgradient method · Unconstrained convex optimization, subgradient method | optimization error: O\big(\frac{MR}{\sqrt{T}}\big) -> O\Big(\frac{M R + \eta}{\sqrt{T}}\Big) + 2T\eta | Hurt |
| Use the transfer wrapper with η-approximate information | Accelerated algorithm · Unconstrained smooth convex optimization, accelerated algorithm | optimization error: O(\frac{\alpha R^2}{T^2}) -> O(\frac{\alpha R^2\sqrt{d}}{T^{1.5}} + \eta T) | Hurt |
Surprising findings
- Approximate function values and subgradients of a convex function generally do not admit any convex extension with those exact values and slopes, so inexact information cannot be used directly.
Limitations
- Smooth-case transfer recovers only part of Nesterov acceleration (error T^-1.5 rather than T^-2).
- Requires storing all historical oracle responses and an O(T^2 d) overhead.
- Constrained (separation oracle) results for smooth objectives and strongly convex cases are omitted from the manuscript.
Experimental setup
Metrics: optimization error bound
Baselines: gradient descent with inexact oracles accelerated gradient descent with inexact oracles
Builds on: Nesterov accelerated gradient randomized smoothing cutting-plane methods
Closest papers by meaning
- Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier (ICML 2016 · similarity 0.88)
- The power of first-order smooth optimization for black-box non-smooth problems (ICML 2022 · similarity 0.88)
- Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values (NeurIPS 2024 · similarity 0.88)
- A Study of First-Order Methods with a Deterministic Relative-Error Gradient Oracle (ICML 2024 · similarity 0.87)
- Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.87)
- Barrier Algorithms for Constrained Non-Convex Optimization (ICML 2024 · similarity 0.86)
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.