A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex
Optimization
- URL: http://arxiv.org/abs/2208.06720v1
- Date: Sat, 13 Aug 2022 19:57:04 GMT
- Title: A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex
Optimization
- Authors: Fran\c{c}ois Bachoc, Tommaso Cesari, Roberto Colomboni, Andrea Paudice
- Abstract summary: We prove near-optimal optimization error guarantees for Dy Search.
We show that the classical dependence on the global Lipschitz constant in the error bounds is an artifact of the granularity of the budget.
- Score: 4.608510640547952
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a natural generalization of the problem of minimizing a
univariate convex function $f$ by querying its values sequentially. At each
time-step $t$, the optimizer can invest a budget $b_t$ in a query point $X_t$
of their choice to obtain a fuzzy evaluation of $f$ at $X_t$ whose accuracy
depends on the amount of budget invested in $X_t$ across times. This setting is
motivated by the minimization of objectives whose values can only be determined
approximately through lengthy or expensive computations. We design an any-time
parameter-free algorithm called Dyadic Search, for which we prove near-optimal
optimization error guarantees. As a byproduct of our analysis, we show that the
classical dependence on the global Lipschitz constant in the error bounds is an
artifact of the granularity of the budget. Finally, we illustrate our
theoretical findings with numerical simulations.
Related papers
- Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
We consider the problem of unconstrained convex optimization, where the cost function changes with time.
Our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable.
Specifically, the proposed algorithms reduce computational cost from $(n3)$ to $O(n)$ per timestep.
arXiv Detail & Related papers (2024-10-19T06:45:05Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
We study the Shortest Path (SSP) problem with a linear mixture transition kernel.
An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost.
Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
arXiv Detail & Related papers (2024-02-14T07:52:00Z) - Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
We consider the problem of multi-fidelity zeroth-order optimization, where one can evaluate a function $f$ at various approximation levels.
We propose a certified variant of the MFDOO algorithm and derive a bound on its cost complexity for any Lipschitz function $f$.
We also prove an $f$-dependent lower bound showing that this algorithm has a near-optimal cost complexity.
arXiv Detail & Related papers (2023-08-02T07:20:37Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
We study the complexity of producing neither smooth nor convex points of Lipschitz objectives which are possibly using only zero-order evaluations.
Our analysis is based on a simple yet powerful.
Goldstein-subdifferential set, which allows recent advancements in.
nonsmooth non optimization.
arXiv Detail & Related papers (2023-07-10T11:56:04Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.
Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
arXiv Detail & Related papers (2023-02-16T13:57:19Z) - 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) - Efficient Minimax Optimal Global Optimization of Lipschitz Continuous
Multivariate Functions [0.0]
We show that our algorithm achieves an average regretO(LstnT-frac1n)$ for the horizon for the Lipschitz continuous functions.
arXiv Detail & Related papers (2022-06-06T06:28:38Z) - Low Regret Binary Sampling Method for Efficient Global Optimization of
Univariate Functions [0.0]
We study the cumulative regret of the algorithm instead of the simple regret between our best query and the optimal value of the objective function.
Although our approach has similar regret results with the traditional lower-bounding algorithms, it has a major computational cost advantage.
arXiv Detail & Related papers (2022-01-18T18:11:48Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary.
Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
We consider the global minimization of smooth functions based solely on function evaluations.
In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
arXiv Detail & Related papers (2020-12-22T12:59:30Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem.
We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
arXiv Detail & Related papers (2020-06-16T17:55:46Z)
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.