arXiv research

The paper analyzes the efficiency of gradient estimation methods in noisy function evaluations.

New algorithm optimizes convex functions with noisy evaluations in one dimension.

A new gradient estimator for online optimization with two function evaluations.

Paper tackles dynamic pricing in a geometrically decaying environment, achieving better occupancy with lower rates.

Study optimizes zero-order strongly convex function minimization with higher order smoothness.

Improved analysis and new algorithm for gradient-free optimization of smooth functions.

We consider the case of derivative-free algorithms for non-convex optimization, also known as zero order algorithms, that use only function evaluations rather than gradients. For a wide variety of gradient approximators based on finite differences, we establish asymptotic convergence to second order stationary points u…

CyBeR-0 optimizes federated learning with Byzantine resilience and reduced communication costs.

We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and analysis which is optimal for convex Lipschitz functions. This improves on \cite{dujww13}, which only p…

The problem of resource allocation of nonlinear networked control systems is investigated, where, unlike the well discussed case of triggering for stability, the objective is optimal triggering. An approximate dynamic programming approach is developed for solving problems with fixed final times initially and then it is…

A new method for distributed optimization with noisy function evaluations.

We study derivative-free methods for policy optimization over the class of linear policies. We focus on characterizing the convergence rate of these methods when applied to linear-quadratic systems, and study various settings of driving noise and reward feedback. We show that these methods provably converge to within a…

We describe a conjectural formula via intersection numbers for the Masur-Veech volumes of strata of quadratic differentials with prescribed zero orders, and we prove the formula for the case when the zero orders are odd. For the principal strata of quadratic differentials with simple zeros, the formula reduces to compu…

We show that the eigenvalues of the intrinsic Dirac operator on the boundary of a Euclidean domain can be obtained as the limits of eigenvalues of Euclidean Dirac operators, either in the domain with a MIT-bag type boundary condition or in the whole space, with a suitably chosen zero order mass term.

Derivative-free method solves stochastic optimization problems with noisy objectives and constraints.

This paper tackles the computational complexity of finding approximate stationary points in non-convex optimization.

A stochastic model for pure-jump diffusion (the compound renewal process) can be used as a zero-order approximation and as a phenomenological description of tick-by-tick price fluctuations. This leads to an exact and explicit general formula for the martingale price of a European call option. A complete derivation of t…

We propose a novel interpretation of the collapsed variational Bayes inference with a zero-order Taylor expansion approximation, called CVB0 inference, for latent Dirichlet allocation (LDA). We clarify the properties of the CVB0 inference by using the alpha-divergence. We show that the CVB0 inference is composed of two…

In this small note we use results derived in Berestycki et al. to correct the celebrated formulae of Hagan et al. We derive explicitly the correct zero order term in the expansion of the implied volatility in time to maturity. The new term is consistent as $β\to 1$. Furthermore, numerical simulations show that it reduc…

Gradient-free optimization for additive models achieves optimal error.

The purpose of this paper is to prove the a priori estimates for constant scalar curvature Kaehler metrics with conic singularities along normal crossing divisors. The zero order estimates are proved by a reformulated version of Alexandrov's maximum principle. The higher order estimates follow from Chen-Cheng's frame …

The superior interpretability and uncertainty modeling ability of Takagi-Sugeno-Kang fuzzy system (TSK FS) make it possible to describe complex nonlinear systems intuitively and efficiently. However, classical TSK FS usually adopts the whole feature space of the data for model construction, which can result in lengthy …

We consider stochastic zero-order optimization problems, which arise in settings from simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We emplo…

We consider spaces of smooth immersed plane curves (modulo translations and/or rotations), equipped with reparameterization invariant weak Riemannian metrics involving second derivatives. This includes the full $H^2$-metric without zero order terms. We find isometries (called $R$-transforms) from some of these spaces i…

Unified algorithm for stochastic optimization with time-varying momentum converges under general conditions.

Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.

New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.

New algorithms sample convex bodies using Markov chains and restricted Gaussian oracles.

MAMBA learns policies competitive with multiple conflicting oracles.

We study the problem of interactively learning a binary classifier using noisy labeling and pairwise comparison oracles, where the comparison oracle answers which one in the given two instances is more likely to be positive. Learning from such oracles has multiple applications where obtaining direct labels is harder bu…

Let $M$ be a complete Riemannian manifold and let $Ω^*(M)$ denote the space of differential forms on $M$. Let $d:Ω^*(M) \to Ω^{*+1}(M)$ be the exterior differential operator and let $\Del=dd^*+d^*d$ be the Laplacian. We establish a sufficient condition for the Schroedinger operator $H=\Del+V(x)$ (where the potential $V…

New oracle uses uncertainty for active classification with noisy feedback.

Quantum oracles help identify counterfactuals better than classical ones.

SoQal reduces oracle label requests in active learning by up to 35%.

Paper addresses online alignment of large language models under uncertain preference feedback.

We consider the problem of minimizing the sum of submodular set functions assuming minimization oracles of each summand function. Most existing approaches reformulate the problem as the convex minimization of the sum of the corresponding Lovász extensions and the squared Euclidean norm, leading to algorithms requiring …

Algorithm solves online binary classification and infinite games using ERM oracle.

The paper calculates option prices using Mellin transform for stochastic volatility models.

New algorithm learns efficiently with a simple 'yes/no' oracle.

New study shows Gaussian samplers struggle with heavy-tailed targets, while stable samplers excel.

Average Oracle outperforms DCC+NLS in portfolio optimization.

New lower bounds for bilevel optimization with first-order oracles.

John Lott has computed an integer-valued signature for the orbit space of a compact orientable $(4k+1)$ manifold with a semi-free $S^1$-action, which is a homotopy invariant of that space, but he did not construct a Dirac type operator which has this signature as its index. In this Thesis, we construct such operator on…

Study on tradeoffs between mistakes and ERM oracle calls in online and transductive learning.

Panoptic trades options without oracles on Ethereum.

In this paper, we propose to combine imitation and reinforcement learning via the idea of reward shaping using an oracle. We study the effectiveness of the near-optimal cost-to-go oracle on the planning horizon and demonstrate that the cost-to-go oracle shortens the learner's planning horizon as function of its accurac…

Semi-supervised active clustering (SSAC) utilizes the knowledge of a domain expert to cluster data points by interactively making pairwise "same-cluster" queries. However, it is impractical to ask human oracles to answer every pairwise query. In this paper, we study the influence of allowing "not-sure" answers from a w…

Three new oracle-efficient algorithms for private synthetic data release.