arXiv research

BioBO optimizes gene perturbation design using Bayesian optimization with biological priors.

We investigate the optimality of perturbation based algorithms in the stochastic and adversarial multi-armed bandit problems. For the stochastic case, we provide a unified regret analysis for both sub-Weibull and bounded perturbations when rewards are sub-Gaussian. Our bounds are instance optimal for sub-Weibull pertur…

Paper develops robust estimators and strategies for stochastic MABs with heavy-tailed rewards.

Improved FTPL algorithm reduces regret in predictable minimax games.

SGD converges with perturbed forward-backward passes, explained by geometric amplification.

New approach reduces unconstrained linear bandits to simpler optimization problems.

Study optimal strategies for insurer's dividends, investments, and liabilities.

New algorithm optimizes multi-armed bandits with low computational cost.

Classical matrix perturbation results, such as Weyl's theorem for eigenvalues and the Davis-Kahan theorem for eigenvectors, are general purpose. These classical bounds are tight in the worst case, but in many settings sub-optimal in the typical case. In this paper, we present perturbation bounds which consider the natu…

SGD generalization bounds derived from information theory.

Study spectral learning for odeco tensors, addressing initialization bottlenecks.

The problem of attribution is concerned with identifying the parts of an input that are responsible for a model's output. An important family of attribution methods is based on measuring the effect of perturbations applied to the input. In this paper, we discuss some of the shortcomings of existing approaches to pertur…

The scalability of submodular optimization methods is critical for their usability in practice. In this paper, we study the reducibility of submodular functions, a property that enables us to reduce the solution space of submodular optimization problems without performance loss. We introduce the concept of reducibility…

Paper addresses eigenvector perturbation in small eigen-gap scenarios.

The paper examines fair pricing and hedging stability under small numéraire perturbations.

New method UADs improves transferability of adversarial perturbations.

Automates perturbation analysis for neural networks, enabling certified robustness on complex architectures.

We consider in this work a system of two stochastic differential equations named the perturbed compositional gradient flow. By introducing a separation of fast and slow scales of the two equations, we show that the limit of the slow motion is given by an averaged ordinary differential equation. We then demonstrate that…

We propose a new input perturbation mechanism for publishing a covariance matrix to achieve $(ε,0)$-differential privacy. Our mechanism uses a Wishart distribution to generate matrix noise. In particular, We apply this mechanism to principal component analysis. Our mechanism is able to keep the positive semi-definitene…

We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyze asynchronous implementations of stochastic optimization algorithms.In this framework, asynchronous stochastic optim…

We propose an online algorithm for cumulative regret minimization in a stochastic multi-armed bandit. The algorithm adds $O(t)$ i.i.d. pseudo-rewards to its history in round $t$ and then pulls the arm with the highest average reward in its perturbed history. Therefore, we call it perturbed-history exploration (PHE). Th…

Optimizes decision-making with uncertain variables using auxiliary observations.

DBPA assesses LLM perturbations using frequentist hypothesis testing.

Paper examines stability of Bayesian posterior measures using integral probability metrics.

This paper analyzes adversarial attacks methods and their effectiveness.

New algorithm optimizes robust estimation under mixed local and global corruptions.

Paper establishes lower bounds for Gaussian process bandit optimization under various perturbation models.

New method creates universal perturbations to fool neural network interpretations.

Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.

The inverse statistical problem of finding direct interactions in complex networks is difficult. In the natural sciences, well-controlled perturbation experiments are widely used to probe the structure of complex networks. However, our understanding of how and why perturbations aid inference remains heuristic, and we l…

Proposes a stability evaluation criterion for learning models using distributional perturbations.

Improved online Lasso reduces regret in sparse linear contextual bandits.

Constructing an efficient parameterization of a large, noisy data set of points lying close to a smooth manifold in high dimension remains a fundamental problem. One approach consists in recovering a local parameterization using the local tangent plane. Principal component analysis (PCA) is often the tool of choice, as…

Study of regularized least squares in RKKS with indefinite kernels.

We consider the problem of maximizing a non-concave Lipschitz multivariate function over a compact domain by sequentially querying its (possibly perturbed) values. We study a natural algorithm designed originally by Piyavskii and Shubert in 1972, for which we prove new bounds on the number of evaluations of the functio…

The higher order singular value decomposition (HOSVD) of tensors is a generalization of matrix SVD. The perturbation analysis of HOSVD under random noise is more delicate than its matrix counterpart. Recently, polynomial time algorithms have been proposed where statistically optimal estimates of the singular subspaces …

Study analyzes perturbations in singular subspaces under random noise.

Study robust estimation of principal components under adversarial perturbations.

Refined theorem on linear perturbations with applications in singularity theory and optimization.

We employ perturbation analysis technique to study multi-asset portfolio optimisation with transaction cost. We allow for correlations in risky assets and obtain optimal trading methods for general utility functions. Our analytical results are supported by numerical simulations in the context of the Long Term Growth Mo…

Deep networks have recently been shown to be vulnerable to universal perturbations: there exist very small image-agnostic perturbations that cause most natural images to be misclassified by such classifiers. In this paper, we propose the first quantitative analysis of the robustness of classifiers to universal perturba…

New method proves inequalities for self-shrinkers using perturbation.

This study benchmarks transcriptomics models for perturbation analysis, finding scVI and PCA superior.

New bounds for KANs trained with DP-SGD, addressing correlated noise.

Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.

We consider semidefinite programs (SDPs) of size n with equality constraints. In order to overcome scalability issues, Burer and Monteiro proposed a factorized approach based on optimizing over a matrix Y of size $n$ by $k$ such that $X = YY^*$ is the SDP variable. The advantages of such formulation are twofold: the di…

Gradient perturbation, widely used for differentially private optimization, injects noise at every iterative update to guarantee differential privacy. Previous work first determines the noise level that can satisfy the privacy requirement and then analyzes the utility of noisy gradient updates as in the non-private cas…

Method differentiates diffusion model training to predict sample sensitivity.