Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries

• URL: http://arxiv.org/abs/2010.10194v2
• Date: Sat, 21 Nov 2020 23:50:55 GMT
• Title: Optimistic search strategy: Change point detection for large-scale data via adaptive logarithmic queries
• Authors: Solt Kov\'acs, Housen Li, Lorenz Haubner, Axel Munk, Peter B\"uhlmann
• Abstract summary: Change point detection is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. We propose optimistic search strategies with $O(log T)$ exploiting specific structure of the gain function.
• Score: 1.3212010735248336
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As a classical and ever reviving topic, change point detection is often formulated as a search for the maximum of a gain function describing improved fits when segmenting the data. Searching through all candidate split points on the grid for finding the best one requires $O(T)$ evaluations of the gain function for an interval with $T$ observations. If each evaluation is computationally demanding (e.g. in high-dimensional models), this can become infeasible. Instead, we propose optimistic search strategies with $O(\log T)$ evaluations exploiting specific structure of the gain function. Towards solid understanding of our strategies, we investigate in detail the classical univariate Gaussian change in mean setup. For some of our proposals we prove asymptotic minimax optimality for single and multiple change point scenarios. Our search strategies generalize far beyond the theoretically analyzed univariate setup. We illustrate, as an example, massive computational speedup in change point detection for high-dimensional Gaussian graphical models. More generally, we demonstrate empirically that our optimistic search methods lead to competitive estimation performance while heavily reducing run-time.

Related papers

• Optimizing Posterior Samples for Bayesian Optimization via Rootfinding [2.94944680995069]
  We introduce an efficient global optimization strategy for posterior samples based on global rootfinding. We demonstrate remarkable improvement in both inner- and outer-loop optimization. We also propose a sample-average formulation of GP-TS, which has a parameter to explicitly control exploitation.
  arXiv  Detail & Related papers  (2024-10-29T17:57:16Z)
• Gaussian Process Thompson Sampling via Rootfinding [2.94944680995069]
  Thompson sampling (TS) is a simple, effective policy in Bayesian decision making. In continuous optimization, the posterior of the objective function is often a Gaussian process (GP), whose sample paths have numerous local optima. We introduce an efficient global optimization strategy for GP-TS that carefully selects starting points for gradient-based multi-starts.
  arXiv  Detail & Related papers  (2024-10-10T16:06:45Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  Policy Iteration (PI) algorithm alternates between greedy one-step policy improvement and policy evaluation. Recent literature shows that multi-step lookahead policy improvement leads to a better convergence rate at the expense of increased complexity per iteration. We propose for the first time to dynamically adapt the multi-step lookahead horizon as a function of the state and of the value estimate.
  arXiv  Detail & Related papers  (2022-01-28T20:26:55Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Using Distance Correlation for Efficient Bayesian Optimization [0.0]
  We propose a novel approach for Bayesian optimization, called $textsfGP-DC$. It balances exploration and exploitation automatically, and requires no manual parameter tuning. We evaluate $textsfGP-DC$ on a number of benchmark functions and observe that it outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-02-17T19:37:35Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  We develop and analyze minibatch variants of gradient algorithm for general composite objective functions with nonsmooth components. We provide complexity for constant and variable stepsize iteration policies obtaining that, for minibatch size $N$, after $mathcalO(frac1Nepsilon)$ $epsilon-$subity is attained in expected quadratic distance to optimal solution.
  arXiv  Detail & Related papers  (2020-03-30T10:43:56Z)

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.