Research map / Learning theory and algorithms / Kernels and regression theory

Scalable Kernel Inverse Optimization

NeurIPS 2024 · Learning theory and algorithms › Kernels and regression theory · approach: RKHS kernel methods · 0 citations (OpenAlex)

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.

Extends inverse optimization to RKHS hypotheses with a kernelized suboptimality-loss SDP and proposes Sequential Selection Optimization (coordinate-descent-style block updates) to scale training on MuJoCo D4RL learning-from-demonstration tasks.

Problem

Inverse optimization learns the objective of an expert's forward optimization problem from data, but linear hypothesis classes are limited in expressiveness, and kernelized IO SDPs scale poorly (memory grows quadratically with dataset size).

Approach

Kernelize the quadratic FOP objective via a dual/LMI reformulation of the suboptimality loss so the problem becomes a finite-dimensional convex SDP over dual variables, and train it with a block coordinate method (SSO) that selects KKT-violating coordinates plus random ones, warm-started by solving sub-datasets.

Key results

• KIO with 5k-10k samples reaches normalized returns such as 109.9 on Hopper-expert and 50.2 on Hopper-medium, competitive with BC baselines in four of six tasks, while linear IO scores near zero on Walker2d and Halfcheetah.
• SSO converges to within about 1e-4 of the optimal objective (SCS) by 20 iterations on the six tasks, with errors below 0.1 by iteration 10.
• On 100k-sample medium-expert tasks, KIO reaches 79.6 (Hopper), 100.1 (Walker2d), and 46.4 (Halfcheetah) normalized return, where direct SDP solving ran out of memory.

Measured effects reported in the paper

Surprising findings

• Linear-kernel KIO performs near zero on several tasks, showing the kernel is essential for learning from demonstrations.
• Plain IO without kernels fails on Walker2d and Halfcheetah (scores near 0 or negative).

Limitations

• Adding a new data point requires all training data to compute the FOP coefficients, so cost grows with dataset size.
• No theoretical convergence rate analysis for SSO.
• Memory use remains substantial (up to 256 GB at 100k data points) and initialization strongly affects SSO.

Experimental setup

Datasets: D4RL Hopper-expert D4RL Hopper-medium D4RL Walker2d-expert D4RL Walker2d-medium D4RL Halfcheetah-expert D4RL Halfcheetah-medium D4RL Hopper-medium-expert D4RL Walker2d-medium-expert D4RL Halfcheetah-medium-expert

Benchmarks: D4RL MuJoCo (Hopper, Walker2d, Halfcheetah)

Metrics: normalized return suboptimality objective gap

Baselines: IO (linear inverse optimization) BC(TD3+BC) BC(CQL) SCS

Builds on: inverse optimization suboptimality loss representer theorem sequential minimal optimization

Closest papers by meaning

• Inverse Optimization via Learning Feasible Regions (ICML 2025 · similarity 0.86)
• Automated Kernel Discovery Towards Understanding High-dimensional Bayesian Optimization (NeurIPS 2026 · similarity 0.85)
• Inverse M-Kernels for Linear Universal Approximators of Non-Negative Functions (NeurIPS 2024 · similarity 0.85)
• Adaptive Kernel Design for Bayesian Optimization Is a Piece of CAKE with LLMs (NeurIPS 2025 · similarity 0.85)
• Conformal Inverse Optimization (NeurIPS 2024 · similarity 0.85)
• Kernel-based guarantees for nonlinear parametric models in Bayesian optimization (NeurIPS 2026 · similarity 0.84)