Optimal Stochastic Nonconvex Optimization with Bandit Feedback

• URL: http://arxiv.org/abs/2103.16082v1
• Date: Tue, 30 Mar 2021 05:21:12 GMT
• Title: Optimal Stochastic Nonconvex Optimization with Bandit Feedback
• Authors: Puning Zhao and Lifeng Lai
• Abstract summary: We analyze continuous armed bandit problems for non cost functions under certain smoothness and sublevel set assumptions. We then propose an adaptive splitting method, which can significantly improve the performance.
• Score: 45.675080529219365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we analyze the continuous armed bandit problems for nonconvex cost functions under certain smoothness and sublevel set assumptions. We first derive an upper bound on the expected cumulative regret of a simple bin splitting method. We then propose an adaptive bin splitting method, which can significantly improve the performance. Furthermore, a minimax lower bound is derived, which shows that our new adaptive method achieves locally minimax optimal expected cumulative regret.

Related papers

• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand. We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• Optimal Rates for Robust Stochastic Convex Optimization [12.620782629498812]
  We develop novel algorithms that achieve minimax-optimal excess risk under the $epsilon$-contamination model. Our algorithms do not require restrictive assumptions, and can handle nonsmooth but Lipschitz population loss functions.
  arXiv  Detail & Related papers  (2024-12-15T00:52:08Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  This paper develops a dimensionality reduction method that allows us to move the optimization to a finite-dimensional setting with an explicit bound on the dimension. In order to make progress on the problem, we restrict ourselves to Bayesian risks induced by a relatively large class of loss functions, namely Bregman divergences.
  arXiv  Detail & Related papers  (2022-02-23T16:22:28Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization [14.848525762485872]
  Making the gradients small is a fundamental optimization problem that has eluded unifying and simple convergence arguments. We introduce a novel potential function-based framework to study the convergence of standard methods for making the gradients small.
  arXiv  Detail & Related papers  (2021-01-28T16:41:00Z)
• Incremental Without Replacement Sampling in Nonconvex Optimization [0.0]
  Minibatch decomposition methods for empirical risk are commonly analysed in an approximation setting, also known as sampling with replacement. On the other hands modern implementations of such techniques are incremental: they rely on sampling without replacement, for which available analysis are much scarcer. We provide convergence guaranties for the latter variant by analysing a versatile incremental gradient scheme.
  arXiv  Detail & Related papers  (2020-07-15T09:17:29Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

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.