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
-
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
-
Assume [Formula: see text]. If [Formula: see text] is an ordinal and X is a set of ordinals, then [Formula: see text] is the collection of order-preserving functions [Formula: see text] which have uniform cofinality [Formula: see text] and discontinuous everywhere. The weak partition properties on [Formula: see text] and [Formula: see text] yield partition measures on [Formula: see text] when [Formula: see text] and [Formula: see text] when [Formula: see text]. The following almost everywhere continuity properties for functions on partition spaces with respect to these partition measures will be shown. For every [Formula: see text] and function [Formula: see text], there is a club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. For every [Formula: see text] and function [Formula: see text], there is an [Formula: see text]-club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. The previous two continuity results will be used to distinguish the cardinalities of some important subsets of [Formula: see text]. [Formula: see text]. [Formula: see text]. [Formula: see text]. It will also be shown that [Formula: see text] has the Jónsson property: For every [Formula: see text], there is an [Formula: see text] with [Formula: see text] so that [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
