CS Paper Radar

Optimal and Efficient Online Inverse Optimization

Anupam Gupta, Guru Guruganesh, Honghao Lin, Vahab Mirrokni, Renato Paes Leme, David P. Woodruff

cs.LG cs.DS ·submitted 2026-10-06 17:37 UTC · v1

Abstract

In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on $\mathbb{R}^{d}$; the goal is to learn to optimize this objective without observing it. Sakaue recently obtained the optimal regret $O(\sqrt d)$ with a randomized algorithm making $(dT)^{O(d)}$ linear optimizations per round, and asked whether it can be attained in polynomial time. We answer positively: our deterministic algorithm has regret $O(\sqrt d)$ for every horizon $T$ and runs in time polynomial in $d$ and $T$. It is a variant of the variable-metric algorithms of Sakaue et al.\ and Cai et al., in which a metric update is revoked once the query point moves far enough from where the update was made.

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Online Inverse Optimization with $O(d)$ Regret

cs.LG cs.DS ·2026-09-11 ·Yang Cai, Anupam Gupta, Vineet Gupta, Guru Guruganesh, Yanchen Jiang +5 more
highly cited similarity 0.80
Abstract

We give a deterministic algorithm for online inverse linear optimization with regret $O(d)$, uniform in the horizon and $O(d^{2})$ time per round. A bound of this order was obtained recently by Dewasurendra, settling a question of Gollapudi et al.\ and of Oki and Sakaue, but by an improper rule that enumerates covers at every scale and costs $T^{Θ(d)}$ a round; ours is the first efficient such bound and the first proper one. We build on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and we replace the $\log\det$ potential by the trace power $\tr(H^{-1/2})$, which is bounded outright and removes the $\ln T$. The bound also holds against an expert that does not optimize, and we give corruption-robust and rank-adaptive variants, and an application to convex minimization.

0.45

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

cs.DS stat.MLcs.LG ·2026-09-22 ·Shinsaku Sakaue
theoryhighly cited similarity 0.78
Abstract

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $Ω(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

0.41

Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes

cs.LG cs.DSmath.OC ·2026-09-09 ·Akira Kitaoka
theory similarity 0.73
Abstract · 56 pages

In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of $\log T$ between the regret upper bound $O(d \log T)$ and the lower bound $Ω(d)$ is unresolved (here $T$ is the total number of rounds and $d$ is the dimension). When the action set is M-convex, the regret is known to be bounded by $O(d \log d)$, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake, and applies it to online gradient descent, the online Newton step, and MetaGrad. When the forward problem is an integer linear program with a unique optimal solution, the number of mistakes is bounded, for all three, by a quantity independent of $T$; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes $O(d^2)$, that is, the factor $\log T$ is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.

0.49

Tracking a Small Set of Experts in Online Convex Optimization

cs.LG math.OCstat.ML ·2026-10-14 ·Angelos Assos, Anand Brahmbhatt, Elad Hazan
similarity 0.70
Abstract

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches $k$ times among only $m$ experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of $\widetilde{O}(md+k)$, while the best known efficient algorithm for this problem has regret $\widetilde{O}(dk)$. We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least $(k\sqrt d)^{1-o(1)}$ regret.

0.19

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

cs.LG stat.ML ·2026-08-25 ·Mengxiao Zhang
theory similarity 0.69
Abstract

In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$ by providing both a lower bound and an algorithm achieving a matching upper bound. This significantly improves upon the $O(T^{1/3}\log^{2/3} d)$ established by [HLLZ25]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the $O((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by [CCK+23,HLLZ25]. As a direct implication, our alternating dynamics achieve $O(\frac{\log d}{T})$ convergence to Nash equilibrium in two-player zero-sum games, matching the state of the art, and give the first such convergence rate to coarse correlated equilibrium in two-player general-sum games. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the construction for the expert problem repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.

0.26

Strongly Adaptive Online Learning with Time-Varying Movement Costs

cs.LG stat.ML ·2026-10-23 ·Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang
top venue similarity 0.68
Abstract · v2: NeurIPS 2026 camera-ready

We study online convex optimization (OCO) with time-varying movement costs, where the learner incurs both a loss and a time-dependent penalty for changing its decisions. While previous work has established dynamic regret guarantees for this setting, obtaining strongly adaptive guarantees that hold simultaneously over arbitrary intervals remains an open challenge. We address this by developing a new algorithm which, for every interval $[a,b]\subseteq[T]$ and arbitrary comparator sequence, achieves a data-dependent regret bound of $ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right) $, where $D$ is the diameter of the decision domain, $P_{[a,b]}$ is the path length of the comparator sequence over $[a,b]$, $g_t$ is the gradient of the loss, and $λ_t$ is the movement-cost coefficient at round~$t$. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of our development, we further obtain strongly-adaptive dynamic regret guarantees under arbitrary delayed feedback with a refined dependence on interval-restricted cumulative delays. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.

0.41

Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning

cs.LG math.OC ·2026-10-14 ·Yanyi Li, Wendao Wu, Haihan Zhang, Qinshi Wang, Chenheng Zhang +4 more
theory similarity 0.68
Abstract

Tracking changing comparators is a central problem in online learning. For exp-concave losses, previous work established the $T^{1/3}P_T^{2/3}$ dependence on the horizon $T$ and Euclidean path length $P_T$ for fixed dimension, while the optimal cost of dimension remained unresolved. We resolve this question by establishing a sharp $d^{1/3}$ curved dimension factor, improving the $d^{2/3}$ factor of recent switching and interval reductions [1, 2]. To achieve this improvement, we develop a proper, full-information learner on compact convex subsets of $\mathbb{R}^d$ that adapts to the unknown path length and, under fixed dimension-independent diameter, gradient, and curvature parameters, guarantees $$\operatorname{Reg}_T(u_{1:T}) \le \widetilde{O}\left(d+\min\left\{d^{1/3}T^{1/3}P_T^{2/3},\sqrt{TP_T},T\right\}\right).$$ A matching lower bound on a diameter-one Euclidean ball establishes the minimax frontier up to logarithmic factors when $T\gtrsim d^2$, including the transition from the curved rate to larger path budgets. The lower bound already holds for losses that depend on only one coordinate per round, isolating an unavoidable cost of learning across directions. Our upper bound follows from square-root Gaussian KL control of comparator movement and a cancellation argument that pays for history restarts. The curved learner maintains $O(\log^2 T)$ Gaussian states, uses one gradient per round, and runs in time near-linear in $T$ under a Mahalanobis-projection oracle.

0.14

When Is Tracking Affordable? A Movement-Budget Feasibility Threshold for Dynamic Regret

cs.LG eess.SYmath.OCstat.ML ·2026-11-02 ·Ridham Patel
publishedtheory similarity 0.67
Abstract · Accepted at NeurIPS 2026 FMTS Workshop

Dynamic regret measures an online learner against a moving comparator, and standard analyses assume the learner may move freely at every round. We study what happens when it may not: the learner is given a hard budget $S$ on its total movement $\sum_t \|x_t - x_{t-1}\|$. Our main result is that a movement budget creates a feasibility barrier. On a domain of diameter $D$ with $G$-Lipschitz convex losses, for every comparator path length $P_T \in [D, DT]$ we exhibit a deterministic adversary that forces $R_d = Ω(GDT)$ on every budget-feasible algorithm whenever $S \le c P_T$ for a universal constant $c>0$. This barrier is caused by the budget rather than by a volatile environment: for fixed $D$, it applies when $P_T = o(T)$, where the unconstrained minimax rate $Θ(G\sqrt{D(D+P_T)T})$ is sublinear, so the same instances are learnable with an unbounded budget and unlearnable without one. Conversely, projected online gradient descent with a budget-aware step size is budget-feasible and attains $o(GDT)$ once $S = ω(D + P_T)$. Thus the critical movement scale is $D+P_T$: linear regret is unavoidable below a sufficiently small constant multiple of $P_T$, while sublinear regret is achievable when $S/(D+P_T)\to\infty$ in the learnable regime. The construction rests on a distinction we make explicit: what makes a comparator expensive to track under a movement budget is the distance it forces the learner to travel, not its path length. Above the threshold we give a budget-dependent upper bound and identify the tight minimax rate in this region as an open problem rather than claiming a product law. Experiments support the predicted transition location and the $1/S$ decay.

0.32