Research map / Bandits and online learning / Online convex optimization and games
Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
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 that online Newton step on exp-concave suboptimality-based losses gives an O(n ln T) regret method for online inverse linear optimization with per-round cost independent of T, extends it to suboptimal agents via MetaGrad (O(n ln T + sqrt(Δ_T n ln T))), and proves an Ω(n) lower bound.
Problem
Online inverse linear optimization: learning an agent's hidden linear objective from sequentially observed feasible sets and (possibly suboptimal) optimal actions, with logarithmic regret and per-round complexity independent of T.
Approach
Apply online Newton step to exp-concave losses (the MetaGrad-style eta-expert loss) built from the agent's observed actions, giving O(n ln T) regret with per-round cost independent of T; for suboptimal agents, run MetaGrad on suboptimality losses and use a self-bounding argument to get sqrt(Delta_T) dependence.
Key results
- ONS-based method achieves O(n ln T) regret with per-round complexity O(tau_solve + tau_G-proj + n^2), independent of T.
- MetaGrad-based method achieves O(n ln T + sqrt(Delta_T n ln T)) regret under suboptimal agent actions.
- Lower bound of Omega(n) (Bn/4) on expected regret for any learner, showing the O(n ln T) bound is tight up to a ln T factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply ONS to exp-concave losses | Online inverse linear optimization with optimal feedback · Online inverse linear optimization | regret bound: O(n^4\ln T) -> O\prn*{Bn\ln\prn*{\frac{DKT}{Bn}}} | Helped |
| Apply MetaGrad instead of ONS to suboptimality losses | Online inverse linear optimization with possibly suboptimal feedback · Online inverse linear optimization | regret dependence on cumulative suboptimality: linear in Δ_T -> O\prn*{ Bn\ln\prn*{\frac{DKT}{Bn}} + \sqrt{ \Delta_T Bn\ln\prn*{\frac{DKT}{Bn}} } } | Helped |
| Use the ONS-based method with constant per-round updates rather than maintaining regions with O(T) constraints | Online inverse linear optimization · Online inverse linear optimization | per-round complexity: poly(n, T) -> O\prn*{\tau_\text{solve} + n^2 + \tau_\text{G-proj}} | Helped |
| Use MetaGrad for the offline online-to-batch conversion | Average prediction under bounded-suboptimality i.i.d. feedback · Offline online-to-batch conversion | excess suboptimality loss rate when Δ = 0: O\prn[\big]{\frac{1}{\sqrt{T}}} -> O\prn[\big]{\frac{\ln T}{T}} | Helped |
Surprising findings
- Their analysis suggests prior logarithmic-regret methods (Besbes et al.) have per-round cost of at least O(n^5 T^3), which is prohibitive for large T.
- Linear dependence on suboptimality (plain ONS) would give O(T) regret even for small persistent suboptimality, which MetaGrad avoids.
Limitations
- Restricted to linear agent objectives; nonlinear settings left open.
- Gap of O(ln T) between upper and lower bounds remains open.
- Lower bound construction uses line-segment feasible sets; full-dimensional case open.
Experimental setup
Metrics: regret per-round complexity
Baselines: Bärmann et al. 2017 OGD Besbes et al. 2021 Gollapudi et al. 2021 Bärmann et al. 2020 MWU
Builds on: online Newton step MetaGrad Bärmann et al. online inverse linear optimization Besbes et al. contextual recommendation
Closest papers by meaning
- Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets (ICML 2026 · similarity 0.94)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.89)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.89)
- Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets (NeurIPS 2024 · similarity 0.88)
- Fully Unconstrained Online Learning (NeurIPS 2024 · similarity 0.88)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.88)
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.