Kernel Methods for Refined Prophet Inequalities

• URL: http://arxiv.org/abs/2608.08662v1
• Date: Sun, 09 Aug 2026 12:08:57 GMT
• Title: Kernel Methods for Refined Prophet Inequalities
• Abstract summary: Single-selection prophet inequality is a canonical online selection problem in which independent nonnegative values arrive sequentially.<n>We develop a general kernel method for single-threshold prophet inequalities.
• Score: 27.407082709350707
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irrevocably select at most one. Classical single-threshold guarantees are tight in the worst case, but the hard instances that prove tightness are highly irregular: the prophet's advantage is driven by rare, very large realizations of the maximum. We refine this worst-case picture by imposing a bound on the relative variance of the prophet's value, $\mathrm{Var}(\max_{i\in[n]}X_i)/\mathbb E[\max_{i\in[n]}X_i]^2$. This yields a nonparametric complexity measure that interpolates between deterministic instances, where the full prophet value can be recovered, and the unrestricted worst-case regime. Our main technical contribution is a general kernel method for single-threshold prophet inequalities. The method represents an instance by the quantile function of the maximum and rewrites the payoff of a threshold as a linear kernel functional of this quantile. This turns the worst-case analysis into an infinite-dimensional convex program, restores strong minimax duality in quantile space, and reduces the bounded-variance adversary's problem to a one-parameter variational family. Applying this framework, we obtain an exact characterization of the IID bounded-variance curve and asymptotically optimal finite-horizon thresholds, a closed-form expression for the fixed-order non-identical model, and a prophet-secretary lower-bound program together with a strict separation from the IID benchmark at every positive finite variance constraint. As a further application of the same kernel viewpoint, we derive an exact formula for IID random horizons under a convexity condition on the horizon pgf, which includes monotone-hazard-rate horizons, highlighting the broad applicability of this new technique for single threshold settings.

Related papers

• A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition [39.146761527401424]
  This work introduces a proximal subgradient method for minimizing the sum of an expected cost.<n>We use the Kurdyka-Lojasiewicz (KL) property to guarantee convergence of the whole trajectory to a single stationary point.
  arXiv  Detail & Related papers  (2026-08-05T23:07:27Z)
• Quadratic Objective Perturbation: Curvature-Based Differential Privacy [0.14323566945483496]
  We introduce Quadratic Objective Perturbation (QOP), which perturbs the objective with a random quadratic form.<n>This perturbation induces strong convexity and enforces stability of the problem through curvature.<n>We extend the analysis to account for approximate solutions, showing that privacy guarantees are preserved under inexact solves.
  arXiv  Detail & Related papers  (2026-05-07T09:16:53Z)
• Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints [3.567855687957749]
  This work provides the first finite-time convergence guarantees for linearly constrained bilevel optimization using only first-order methods.<n>We address the unprecedented challenge of simultaneously handling linear constraints, noise, and finite-time analysis in bilevel optimization.
  arXiv  Detail & Related papers  (2025-11-13T00:59:20Z)
• Derivative-Free Sequential Quadratic Programming for Equality-Constrained Stochastic Optimization [3.2489082010225485]
  We consider solving nonlinear optimization problems with an objective and deterministic equality constraints.<n>We propose a Derivative-Free Sequential Quadratic Programming (DF-SSQP) method.<n>Under standard assumptions, we establish the global almost-sure convergence of the proposed DF-SSQP method.
  arXiv  Detail & Related papers  (2025-10-25T23:51:20Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  We consider monotone inclusion problems where the operators may be expectation-valued. A direct application of splitting schemes is complicated by the need to resolve problems with expectation-valued maps at each step. We propose an avenue for addressing uncertainty in the mapping: Variance-reduced modified forward-backward splitting scheme.
  arXiv  Detail & Related papers  (2020-08-26T02:33:27Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.