Chasing Convex Bodies and Functions with Black-Box Advice
- URL: http://arxiv.org/abs/2206.11780v1
- Date: Thu, 23 Jun 2022 15:30:55 GMT
- Title: Chasing Convex Bodies and Functions with Black-Box Advice
- Authors: Nicolas Christianson, Tinashe Handina, Adam Wierman
- Abstract summary: We consider the problem of convex function chasing with black-box advice.
An online decision-maker seeks cost comparable to the advice when it performs well, known as $textitconsistency$.
We propose two novel algorithms that bypass this limitation by exploiting the problem's convexity.
- Score: 7.895232155155041
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of convex function chasing with black-box advice,
where an online decision-maker aims to minimize the total cost of making and
switching between decisions in a normed vector space, aided by black-box advice
such as the decisions of a machine-learned algorithm. The decision-maker seeks
cost comparable to the advice when it performs well, known as
$\textit{consistency}$, while also ensuring worst-case $\textit{robustness}$
even when the advice is adversarial. We first consider the common paradigm of
algorithms that switch between the decisions of the advice and a competitive
algorithm, showing that no algorithm in this class can improve upon
3-consistency while staying robust. We then propose two novel algorithms that
bypass this limitation by exploiting the problem's convexity. The first,
INTERP, achieves $(\sqrt{2}+\epsilon)$-consistency and
$\mathcal{O}(\frac{C}{\epsilon^2})$-robustness for any $\epsilon > 0$, where
$C$ is the competitive ratio of an algorithm for convex function chasing or a
subclass thereof. The second, BDINTERP, achieves $(1+\epsilon)$-consistency and
$\mathcal{O}(\frac{CD}{\epsilon})$-robustness when the problem has bounded
diameter $D$. Further, we show that BDINTERP achieves near-optimal
consistency-robustness trade-off for the special case where cost functions are
$\alpha$-polyhedral.
Related papers
- Dueling Optimization with a Monotone Adversary [35.850072415395395]
We study the problem of dueling optimization with a monotone adversary, which is a generalization of (noiseless) dueling convex optimization.
The goal is to design an online algorithm to find a minimizer $mathbfx*$ for a function $fcolon X to mathbbRd.
arXiv Detail & Related papers (2023-11-18T23:55:59Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem.
We show that all used solvers perform very badly on a large majority of the instances.
We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
arXiv Detail & Related papers (2023-06-29T14:57:56Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
We give a statistical characterization of the $gamma$-regret for arbitrary structured bandit problems.
The $gamma$-regret emerges in structured bandit problems over a function class $mathcalF$ where finding an exact optimum of $f in mathcalF$ is intractable.
arXiv Detail & Related papers (2023-03-06T17:54:33Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
We develop two new algorithms to approximate a solution of nonlinear equations in large-scale settings.
We apply our methods to a class of large-scale finite-sum inclusions, which covers prominent applications in machine learning, statistical learning, and network optimization.
arXiv Detail & Related papers (2023-01-08T21:46:27Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
This work presents the first projection-free algorithm to solve bi-level optimization problems, where the objective function depends on another optimization problem.
The proposed $textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$) is shown to achieve a sample complexity of $mathcalO(epsilon-2)$ for convex objectives.
arXiv Detail & Related papers (2021-10-22T11:49:15Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints.
For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
arXiv Detail & Related papers (2021-01-20T04:29:18Z) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
Black-box access to a (not necessarily smooth) function $f:mathbbRn to mathbbR$ and its (sub)gradient.
Our goal is to find an $epsilon$-approximate minimum of $f$ starting from a point that is distance at most $R$ from the true minimum.
We show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved using $O(GR/epsilon)$ quantum queries.
arXiv Detail & Related papers (2020-10-05T06:32:47Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized.
This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
arXiv Detail & Related papers (2020-04-16T19:16:38Z)
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.