Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e.\ problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexly-constrained problems. It is shown that, given an accuracy level $\epsilon$, a degree of highest available Lipschitz continuous derivatives $p$ and a desired optimality order $q$ between one and $p$, a conceptual regularization algorithm requires no more than $O(\epsilon^{-\frac{p+1}{p-q+1}})$ evaluations of the objective function and its derivatives to compute a suitably approximate $q$-th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$-th derivative is merely H\"older rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems, we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration
This paper studies regret minimization with randomized value functions in reinforcement learning. In tabular finite-horizon Markov Decision Processes, we introduce a clipping variant of one classical Thompson Sampling (T…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Thompson SamplingEfficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes
We study the evaluation of a policy under best- and worst-case perturbations to a Markov decision process (MDP), using transition observations from the original MDP, whether they are generated under the same or a differe…
Off-policy evaluationStochastic approximation with cone-contractive operators: Sharp $\ell_\infty$-bounds for $Q$-learning
Motivated by the study of $Q$-learning algorithms in reinforcement learning, we study a class of stochastic approximation procedures based on operators that satisfy monotonicity and quasi-contractivity conditions with re…
Q-LearningReinforcement LearningModel-Free and Model-Based Policy Evaluation when Causality is Uncertain
When decision-makers can directly intervene, policy evaluation algorithms give valid causal estimates. In off-policy evaluation (OPE), there may exist unobserved variables that both impact the dynamics and are used by th…
modelOff-policy evaluationSensitivityvalidStability, Complexity and Data-Dependent Worst-Case Generalization Bounds
Providing generalization guarantees for stochastic optimization algorithms remains a key challenge in learning theory. Recently, numerous works demonstrated the impact of the geometric properties of optimization trajecto…
Stochastic Optimization