An official website of the United States government
Functionally constrained stochastic optimization problems, where neither the objective function nor the constraint functions are analytically available, arise frequently in machine learning applications. In this work, assuming we only have access to the noisy evaluations of the objective and constraint functions, we propose and analyze stochastic zeroth-order algorithms for solving this class of stochastic optimization problem. When the domain of the functions is [Formula: see text], assuming there are m constraint functions, we establish oracle complexities of order [Formula: see text] and [Formula: see text] in the convex and nonconvex settings, respectively, where ϵ represents the accuracy of the solutions required in appropriately defined metrics. The established oracle complexities are, to our knowledge, the first such results in the literature for functionally constrained stochastic zeroth-order optimization problems. We demonstrate the applicability of our algorithms by illustrating their superior performance on the problem of hyperparameter tuning for sampling algorithms and neural network training. Funding: K. Balasubramanian was partially supported by a seed grant from the Center for Data Science and Artificial Intelligence Research, University of California–Davis, and the National Science Foundation [Grant DMS-2053918].
more »
« less
This content will become publicly available on February 1, 2026
Uniform-in-time bounds for a stochastic hybrid system with fast periodic sampling and small white-noise
We study the asymptotic behavior, uniform-in-time, of a nonlinear dynamical system under the combined effects of fast periodic sampling with period [Formula: see text] and small white noise of size [Formula: see text]. The dynamics depend on both the current and recent measurements of the state, and as such it is not Markovian. Our main results can be interpreted as Law of Large Numbers (LLN) and Central Limit Theorem (CLT) type results. LLN type result shows that the resulting stochastic process is close to an ordinary differential equation (ODE) uniformly in time as [Formula: see text] Further, in regards to CLT, we provide quantitative and uniform-in-time control of the fluctuations process. The interaction of the small parameters provides an additional drift term in the limiting fluctuations, which captures both the sampling and noise effects. As a consequence, we obtain a first-order perturbation expansion of the stochastic process along with time-independent estimates on the remainder. The zeroth- and first-order terms in the expansion are given by an ODE and SDE, respectively. Simulation studies that illustrate and supplement the theoretical results are also provided.
more »
« less
- PAR ID:
- 10587919
- Publisher / Repository:
- world scientific
- Date Published:
- Journal Name:
- Stochastics and Dynamics
- Volume:
- 25
- Issue:
- 01
- ISSN:
- 0219-4937
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The fundamental problem in the study of parallel-server systems is that of finding and analyzing routing policies of arriving jobs to the servers that efficiently balance the load on the servers. The most well-studied policies are (in decreasing order of efficiency) join the shortest workload (JSW), which assigns arrivals to the server with the least workload; join the shortest queue (JSQ), which assigns arrivals to the smallest queue; the power-of-[Formula: see text] (PW([Formula: see text])), which assigns arrivals to the shortest among [Formula: see text] queues that are sampled from the total of [Formula: see text] queues uniformly at random; and uniform routing, under which arrivals are routed to one of the [Formula: see text] queues uniformly at random. In this paper we study the stability problem of parallel-server systems, assuming that routing errors may occur, so that arrivals may be routed to the wrong queue (not the smallest among the relevant queues) with a positive probability. We treat this routing mechanism as a probabilistic routing policy, named a [Formula: see text]-allocation policy, that generalizes the PW([Formula: see text]) policy, and thus also the JSQ and uniform routing, where [Formula: see text] is an [Formula: see text]-dimensional vector whose components are the routing probabilities. Our goal is to study the (in)stability problem of the system under this routing mechanism, and under its “nonidling” version, which assigns new arrivals to an idle server, if such a server is available, and otherwise routes according to the [Formula: see text]-allocation rule. We characterize a sufficient condition for stability, and prove that the stability region, as a function of the system’s primitives and [Formula: see text], is in general smaller than the set [Formula: see text]. Our analyses build on representing the queue process as a continuous-time Markov chain in an ordered space of [Formula: see text]-dimensional real-valued vectors, and using a generalized form of the Schur-convex order.more » « less
-
null (Ed.)Consider a fractional Brownian motion (fBM) [Formula: see text] with Hurst index [Formula: see text]. We construct a probability space supporting both B H and a fully simulatable process [Formula: see text] such that[Formula: see text] with probability one for any user-specified error bound [Formula: see text]. When [Formula: see text], we further enhance our error guarantee to the α-Hölder norm for any [Formula: see text]. This enables us to extend our algorithm to the simulation of fBM-driven stochastic differential equations [Formula: see text]. Under mild regularity conditions on the drift and diffusion coefficients of Y, we construct a probability space supporting both Y and a fully simulatable process [Formula: see text] such that[Formula: see text] with probability one. Our algorithms enjoy the tolerance-enforcement feature, under which the error bounds can be updated sequentially in an efficient way. Thus, the algorithms can be readily combined with other advanced simulation techniques to estimate the expectations of functionals of fBMs efficiently.more » « less
-
We study optimal design problems in which the goal is to choose a set of linear measurements to obtain the most accurate estimate of an unknown vector. We study the [Formula: see text]-optimal design variant where the objective is to minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. We introduce the proportional volume sampling algorithm to obtain nearly optimal bounds in the asymptotic regime when the number [Formula: see text] of measurements made is significantly larger than the dimension [Formula: see text] and obtain the first approximation algorithms whose approximation factor does not degrade with the number of possible measurements when [Formula: see text] is small. The algorithm also gives approximation guarantees for other optimal design objectives such as [Formula: see text]-optimality and the generalized ratio objective, matching or improving the previously best-known results. We further show that bounds similar to ours cannot be obtained for [Formula: see text]-optimal design and that [Formula: see text]-optimal design is NP-hard to approximate within a fixed constant when [Formula: see text].more » « less
-
This paper is a sequel to [Monatsh. Math. 194 (2021) 523–554] in which results of that paper are generalized so that they hold in the setting of inhomogeneous Diophantine approximation. Given any integers [Formula: see text] and [Formula: see text], any [Formula: see text], and any homogeneous function [Formula: see text] that satisfies a certain nonsingularity assumption, we obtain a biconditional criterion on the approximating function [Formula: see text] for a generic element [Formula: see text] in the [Formula: see text]-orbit of [Formula: see text] to be (respectively, not to be) [Formula: see text]-approximable at [Formula: see text]: that is, for there to exist infinitely many (respectively, only finitely many) [Formula: see text] such that [Formula: see text] for each [Formula: see text]. In this setting, we also obtain a sufficient condition for uniform approximation. We also consider some examples of [Formula: see text] that do not satisfy our nonsingularity assumptions and prove similar results for these examples. Moreover, one can replace [Formula: see text] above by any closed subgroup of [Formula: see text] that satisfies certain integrability axioms (being of Siegel and Rogers type) introduced by the authors in the aforementioned previous paper.more » « less
