Stochastic optimization with arbitrary recurrent data sampling

• URL: http://arxiv.org/abs/2401.07694v2
• Date: Sat, 20 Jul 2024 18:56:48 GMT
• Title: Stochastic optimization with arbitrary recurrent data sampling
• Authors: William G. Powell, Hanbaek Lyu,
• Abstract summary: Most commonly used data sampling algorithms are under mild assumptions. We show that for a particular class of recurrent optimization algorithms, we do not need any other property. We show that convergence can be accelerated by selecting sampling algorithms that cover the data set.
• Score: 2.1485350418225244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For obtaining optimal first-order convergence guarantee for stochastic optimization, it is necessary to use a recurrent data sampling algorithm that samples every data point with sufficient frequency. Most commonly used data sampling algorithms (e.g., i.i.d., MCMC, random reshuffling) are indeed recurrent under mild assumptions. In this work, we show that for a particular class of stochastic optimization algorithms, we do not need any other property (e.g., independence, exponential mixing, and reshuffling) than recurrence in data sampling algorithms to guarantee the optimal rate of first-order convergence. Namely, using regularized versions of Minimization by Incremental Surrogate Optimization (MISO), we show that for non-convex and possibly non-smooth objective functions, the expected optimality gap converges at an optimal rate $O(n^{-1/2})$ under general recurrent sampling schemes. Furthermore, the implied constant depends explicitly on the `speed of recurrence', measured by the expected amount of time to visit a given data point either averaged (`target time') or supremized (`hitting time') over the current location. We demonstrate theoretically and empirically that convergence can be accelerated by selecting sampling algorithms that cover the data set most effectively. We discuss applications of our general framework to decentralized optimization and distributed non-negative matrix factorization.

Related papers

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization [12.794526174053134]
  We analyze convergence rates of gradient algorithms for smooth finite-sum minimax optimization. We show that, for many such algorithms, sampling points without replacement leads to faster convergence compared to sampling with replacement.
  arXiv  Detail & Related papers  (2022-06-07T00:37:37Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  We show that the first optimality gap of the proposed algorithm decays at the rate of the expected loss for various methods under nontens dependent data setting. We obtain first convergence point for various methods under nontens dependent data setting.
  arXiv  Detail & Related papers  (2022-01-05T15:17:35Z)
• 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)
• Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory [6.696267547013535]
  We propose a novel distributed adaptive NN classifier for which the number of nearest neighbors is a tuning parameterally chosen by a data-driven criterion. An early stopping rule is proposed when searching for the optimal tuning parameter, which improves the finite sample performance. In particular, we show that when the sub-sample sizes are sufficiently large, the proposed classifier achieves the nearly optimal convergence rate.
  arXiv  Detail & Related papers  (2021-05-20T14:38:41Z)
• On the Comparison between Cyclic Sampling and Random Reshuffling [27.27774034428748]
  Cyclic sampling draws the samples in a fixed, cyclic order, which is less robust than reshuffling the samples periodically. Existing works have established worst case convergence rates for cyclic sampling, which are generally worse than that of random reshuffling. In this paper, we found a certain cyclic order can be much faster than reshuffling and one can discover it at a low cost.
  arXiv  Detail & Related papers  (2021-04-25T09:29:43Z)
• Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
  We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage linear programs. The proposed algorithm can be stopped in finite-time to return a solution endowed with a probabilistic guarantee on quality.
  arXiv  Detail & Related papers  (2020-12-07T14:58:16Z)
• 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)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

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.