Optimization and Search Problems

Neueste Paper

• Compressing Value Predictions for Learning-Augmented Metrical Task Systems

  Sizhe Li, Yecheng Li, Kun He · 29. September 2026

  Learning-augmented algorithms for metrical task systems (MTS) can exploit predictions of canonical dual values, but existing formulations typically require a prediction for every state. We study whether these predictions can be compressed to a small set of representative states while retaining their…

• Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

  Naram Mhaisen, George Iosifidis · 28. September 2026

  We study dynamic regret in online convex optimization with an \emph{indicator switching cost}: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-…

• Transductive Off-policy Proximal Policy Optimization

  Yaozhong Gan, Renye Yan, Xiaoyang Tan, Zhe Wu, Junliang Xing · 25. September 2026

  Proximal Policy Optimization (PPO) is a popular model-free reinforcement learning algorithm, esteemed for its simplicity and efficacy. However, due to its inherent on-policy nature, its proficiency in harnessing data from disparate policies is constrained. This paper introduces a novel off-policy ex…

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

  Shinsaku Sakaue · 24. September 2026

  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 …

• Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

  Jiameng Lyu · 24. September 2026

  The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm …

• Optimal Randomized Proper Online Learning

  Zachary Chase, Idan Mehalel · 21. September 2026

  We prove that the optimal expected mistake bound of online learning a function class $\mathcal{H}$ by a randomized proper learning algorithm is $O(\mathtt{L}(\mathcal{H}) \log T)$, where $\mathtt{L}(\mathcal{H})$ is the Littlestone dimension of $\mathcal{H}$ and $T$ is the time horizon. Our result i…

• Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions

  Rahul Vaze · 11. September 2026

  Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function \(f\) remains fixed but the feasible region evolves over time as a nested sequence \(S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T\). The goal of an online algorithm is …

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

  Akira Kitaoka · 10. September 2026

  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 $\Omega(d)$ is unresolved (here $T$ i…

• Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader

  Ashkan Soleymani, Gabriele Farina, Patrick Jaillet · 10. September 2026

  Online gradient descent is usually studied through external regret, where the learner competes with fixed alternatives. Recent work shows that first-order methods control richer action-dependent deviations. We ask for a geometric characterization of the deviations with respect to which online gradie…

• Constrained Online Learning with Noisy Constraint Values

  Vaneet Aggarwal · 9. September 2026

  We study constrained online convex optimization with adversarial constraints when constraint values and gradients are observed through unbiased noise. Gaussian value noise of standard deviation $\sigma$ yields a worst-case lower bound of $\Omega(\min\{\sigma,1\}T/\log^7T)$ on the maximum of expected…

• Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications

  Hailiang Zhao, Peng Chen, Xueyan Tang, Jianwei Yin, Shuiguang Deng · 7. September 2026

  Learning-augmented algorithms use fallible predictions while retaining formal performance guarantees. This survey synthesizes prediction interfaces, error measures, consistency--robustness trade-offs, and five representative construction mechanisms across online optimization, caching, learned data s…

• Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

  Cheung Hao Lee, Patrick Wong · 2. September 2026

  A multi-model language service must route each request while preserving workload-level budgets for compute, latency, memory, or monetary cost. Two features make this problem materially harder than static model selection. Prompt representations are high dimensional, so only a small subset of embeddin…

• Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift

  Fredy Pokou (MRE, CRIStAL) · 28. August 2026

  Learning-augmented algorithms improve online decisions using predictions, but unreliable advice may harm efficiency and fairness. We study an online allocation problem with finite candidate sets, irreversible decisions, and exposure constraints. We propose a robust and fair rule combining advice wit…

• On the convergence of optimistic policy iteration for stochastic shortest path problem

  Yuanlong Chen · 21. August 2026

  In this paper, we prove some convergence results of a special case of optimistic policy iteration algorithm for stochastic shortest path problem. We consider both Monte Carlo and $TD(\lambda)$ methods for the policy evaluation step under the condition that the termination state will eventually be re…

• Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and a Tight Univariate Rate

  Huibo Xu, Shi Fu, Qixin Zhang, Dacheng Tao · 19. August 2026

  In high-dimensional online prediction, the best predictor may depend on only a few features, so regret should scale with sparsity rather than the ambient dimension. Feature priming pursues this goal by estimating feature weights from past data and refitting a minimum-norm predictor on the rescaled d…

• A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving

  Ian D'Ambrosio · 18. August 2026

  Huang, Lou, and Xiao introduced Dynamic Mixture-of-Experts Serving and gave an O(sqrt(log k))-competitive randomized algorithm for its integral primal problem, where k is the number of replica GPUs beyond the mandatory copy of each expert. Their matching lower barrier applies to an auxiliary dual an…

• Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$-norms

  Sami Davies, Benjamin Moseley, Heather Newman · 14. August 2026

  The $\ell_p$-norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the $\ell_1$-norm) and ensuring fairness to individual nodes (the $\ell_\infty$-norm). Surprisingly, in the offline setting it is possible to simultaneously approximate all…

• Defensive Boosting for Online Probabilistic Forecasting

  Georgy Noarov, Aaron Roth · 14. August 2026

  We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradie…

• High-Dimensional Calibration from Swap Regret

  Maxwell Fishelson, Noah Golowich, Mehryar Mohri, Jon Schneider · 12. August 2026

  We study online calibration of multi-dimensional forecasts over an arbitrary convex set $P \subset \mathbb{R}^d$ relative to an arbitrary norm $|\cdot|$. We connect this to external regret minimization for online linear optimization (OLO): if one can guarantee $O(\sqrt{\rho T})$ worst-case regret af…

• Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws

  Zijun Wang, Yuchen Miao, Yifan Hu, Huanmin Liu · 4. August 2026

  This paper answers the one-dimensional local root anti-concentration questions posed by Balcan, Pegden, and Sharma in the context of online optimization of piecewise-Lipschitz functions. For a homogeneous feature curve and coefficients whose density relative to the uniform law on a symmetric convex …

• Online Algorithms via Minimax and Posterior Matching

  Thomas Kesselheim, Marco Molinaro, Kalen Patton, Sahil Singla · 4. August 2026

  Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary c…

• Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction

  Rahul Vaze · 30. Juli 2026

  Adaptive conformal inference (ACI) of Gibbs and Cand{\`e}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations. First, their guarantees control only the \emph{signed} long-run coverage error: persisten…

• Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise

  Vaneet Aggarwal · 30. Juli 2026

  We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise, where the stochastic gradient oracle admits only a finite $p$-th central moment for some $p \in (1, 2]$. While static regret is well-understood, achieving universal dynamic regret in a parameter-free m…

• Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

  Wentao Zhang · 29. Juli 2026

  Constrained online convex optimization requires minimizing regret against adversarial convex costs while satisfying a convex constraint at every round, as needed in safety-critical applications. A computationally efficient method combines online gradient descent with a Polyak feasibility step, using…

• Autonomous Collaborative Learning Among an Ensemble of Tsetlin Machines with Consensus-Based Inference

  Yehuda Rudin, Osnat Keren, Michal Yemini, Alexander Fish · 23. Juli 2026

  Tsetlin Machine (TM) is a rule-based machine-learning algorithm comprising collectives of two-action Tsetlin Automata (TAs) that cooperatively form conjunctive logical clauses from Boolean inputs through stochastic feedback. Although few recent studies have examined TM Federated Learning, the broade…