Neural networks approximate likelihood ratios for complex models.
problem Difficulty in computing likelihood ratios for modern models.
method Applying the likelihood ratio trick with neural network classifiers.
result Different neural network setups can approximate likelihood ratios with varying performance.
In this work, we propose new objective functions to train deep neural network based density ratio estimators and apply it to a change point detection problem. Existing methods use linear combinations of kernels to approximate the density ratio function by solving a convex constrained minimization problem. Approximating…
In this paper, from a theoretical perspective, we study how powerful graph neural networks (GNNs) can be for learning approximation algorithms for combinatorial problems. To this end, we first establish a new class of GNNs that can solve a strictly wider variety of problems than existing GNNs. Then, we bridge the gap b…
Divergence estimators based on direct approximation of density-ratios without going through separate approximation of numerator and denominator densities have been successfully applied to machine learning tasks that involve distribution comparison such as outlier detection, transfer learning, and two-sample homogeneity…
Posterior inference with an intractable likelihood is becoming an increasingly common task in scientific domains which rely on sophisticated computer simulations. Typically, these forward models do not admit tractable densities forcing practitioners to make use of approximations. This work introduces a novel approach t…
Logistic regression is a widely used method in several fields. When applying logistic regression to imbalanced data, for which majority classes dominate over minority classes, all class labels are estimated as `majority class.' In this article, we use an F-measure optimization method to improve the performance of logis…
In Peña (2007), MCMC sampling is applied to approximately calculate the ratio of essential graphs (EGs) to directed acyclic graphs (DAGs) for up to 20 nodes. In the present paper, we extend that work from 20 to 31 nodes. We also extend that work by computing the approximate ratio of connected EGs to connected DAGs, of …
Efficiently private clustering algorithms with tight approximation ratios.
problem Differentially private clustering of various types.
method Efficient algorithms achieving tight approximation ratios for clustering problems.
result Achieves approximation ratios similar to non-private algorithms with small additive errors.
FORE evaluates occupancy ratios without requiring Bellman completeness.
problem Offline reinforcement learning occupancy ratio estimation.
method Fitted occupancy-ratio evaluation (FORE) using adjoint Bellman recursion.
result FORE achieves convergence in KL without Bellman completeness.
Paper presents a randomized algorithm for SPCA with high probability approximation.
problem Sparse Principal Component Analysis (SPCA) is NP-hard.
method Based on basic SDP relaxation, the algorithm constructs deterministic and randomized solutions.
result The algorithm achieves an approximation ratio of at most the sparsity constant with high probability.
New guarantees for adaptive combinatorial maximization with various objectives.
problem Maximizing under cardinality constraints and minimum cost coverage in adaptive settings.
method Bayesian approach with comprehensive approximation guarantees for various utility functions.
result Maximal gain ratio is a new parameter that provides stronger approximation guarantees than greedy policies.
The paper describes a method to infer the signal-to-noise ratio in portfolio optimization.
problem Estimating the signal-to-noise ratio in portfolio optimization problems.
method A statistic similar to the Sharpe Ratio Information Criterion is used for inference.
result The method works well for reasonable sample and asset universe sizes.
This work extends balancing to various simulation-based inference algorithms for more conservative posterior approximations.
problem Overconfident posterior approximations in simulation-based inference.
method Introduces a balanced version of neural posterior estimation and contrastive neural ratio estimation.
result Balanced versions tend to produce conservative posterior approximations on various benchmarks.
Gaussian graphical models are relevant tools to learn conditional independence structure between variables. In this class of models, Bayesian structure learning is often done by search algorithms over the graph space. The conjugate prior for the precision matrix satisfying graphical constraints is the well-known G-Wish…
Study bond market making with hit-ratio target using optimal control and HJB equations.
problem Optimizing bond market making with hit-ratio target in OTC markets.
method Stochastic optimal control approach, dualizing hit-ratio target, HJB equation, Riccati equation, linearization.
result Explicit quote decompositions into riskless spread, inventory-risk correction, and hit-ratio correction.
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems in practice, its theoretical properties have been analyzed only for a limited class of p…
The problem of biclustering consists of the simultaneous clustering of rows and columns of a matrix such that each of the submatrices induced by a pair of row and column clusters is as uniform as possible. In this paper we approximate the optimal biclustering by applying one-way clustering algorithms independently on t…
In many fields of science, generalized likelihood ratio tests are established tools for statistical inference. At the same time, it has become increasingly common that a simulator (or generative model) is used to describe complex processes that tie parameters θ of an underlying theory and measurement apparatus to hig…
We introduce a model-independent approximation for the branching ratio of Hawkes self-exciting point processes. Our estimator requires knowing only the mean and variance of the event count in a sufficiently large time window, statistics that are readily obtained from empirical data. The method we propose greatly simpli…
Faster algorithm for generalized mean densest subgraph problem.
problem Finding subgraphs with highest average p-th-power degree. method GENPEEL++ algorithm, which yields (2(p+1))1/p-approximation for p∈[1,+∞) with time complexity O(m(logn)). result GENPEEL++ algorithm provides faster and more efficient solution for generalized mean densest subgraph problem.
We study the low rank approximation problem of any given matrix A over Rn×m and Cn×m in entry-wise ℓp loss, that is, finding a rank-k matrix X such that ∥A−X∥p is minimized. Unlike the traditional ℓ2 setting, this particular variant is NP-Hard. We show that…
This paper improves bond market making by adjusting hit-ratios for client flow quality.
problem Economic misleading of raw hit-ratios in corporate bond market making.
method Stochastic-control framework with residual-quality-adjusted hit-ratio.
result Optimal quotes decompose into various components, improving service/economics frontier.
Rank-statistic method approximates f-divergences without density-ratio estimation.
problem Approximating f-divergences without explicit density-ratio estimation. method Mapping distribution rank histograms to discrete f-divergence and averaging over random projections. result The rank-statistic estimator is a lower bound of the true f-divergence and converges under mild conditions. A new method improves density ratio estimation efficiency and accuracy.
problem Density ratio estimation trade-off between quality and efficiency.
method One-step Score-based Density Ratio Estimation (OS-DRE) combining analytic and solver-free approach.
result OS-DRE offers a favorable balance between estimation quality and inference efficiency.
New method improves submodular maximization for machine learning applications.
problem Inexact monotonicity in submodular functions limits traditional algorithms' performance.
method Introduces monotonicity ratio as a continuous version of monotonicity, leading to improved approximation guarantees.
result Improved approximation ratios for movie recommendation, quadratic programming, and image summarization.
Fast algorithms developed for adaptive and fully adaptive submodular maximization problems.
problem Maximizing submodular functions subject to constraints in linear time.
method Developed linear-time algorithms for two submodular maximization problems: adaptive and fully adaptive.
result Achieved (1−1/e−ε) approximation ratio for adaptive submodular maximization and $ rac{1-1/e-ε}{4-2/e-2ε}$ for fully adaptive submodular maximization. New MC simulation methods use classifiers to estimate pdf ratios without explicit pdfs.
problem Estimating ratios of probability density functions (pdfs) without explicit pdfs.
method Proposes classifier-based pdf-free versions of MC simulation algorithms.
result Enables pdf-free simulation algorithms using surrogate functions computed by classifiers.
Given a similarity graph between items, correlation clustering (CC) groups similar items together and dissimilar ones apart. One of the most popular CC algorithms is KwikCluster: an algorithm that serially clusters neighborhoods of vertices, and obtains a 3-approximation ratio. Unfortunately, KwikCluster in practice re…
Estimates the ratio of posterior distributions of latent variables.
problem Comparing posterior distributions of latent variables inferred from observations.
method Parametric model approximation and estimation using observed and prior samples.
result Consistent and asymptotically normal estimation of posterior ratio parameters.
We study the finite horizon Merton portfolio optimization problem in a general local-stochastic volatility setting. Using model coefficient expansion techniques, we derive approximations for the both the value function and the optimal investment strategy. We also analyze the `implied Sharpe ratio' and derive a series a…
We study the problem of selecting a subset of k random variables from a large set, in order to obtain the best linear prediction of another variable of interest. This problem can be viewed in the context of both feature selection and sparse approximation. We analyze the performance of widely used greedy heuristics, usi…
New algorithm maximizes non-monotone adaptive submodular functions in linear time.
problem Maximizing non-monotone adaptive submodular functions subject to a cardinality constraint.
method Developed a linear-time algorithm for non-monotone adaptive submodular maximization.
result Achieved a 1/e−ε approximation ratio with O(nε−2logε−1) value oracle queries. We introduce a general constructive setting of the density ratio estimation problem as a solution of a (multidimensional) integral equation. In this equation, not only its right hand side is known approximately, but also the integral operator is defined approximately. We show that this ill-posed problem has a rigorous …
Improves bandits with knapsacks guarantees for partially stochastic workloads.
problem Improves guarantees for Bandits with Knapsacks (BwK) with partially stochastic workloads.
method Defines Approximately Stationary BwK, explores algorithms with smooth competitive ratios transitioning between stochastic and adversarial cases.
result Offers competitive ratios that smoothly transition between the best possible guarantees in stochastic and adversarial cases, especially beneficial when budget is small.
Paper proposes a fast method for approximate data deletion in generative models.
problem Efficient data deletion in unsupervised learning models is an open problem.
method Density-ratio-based framework for generative models, fast method for approximate data deletion, statistical test.
result Theoretical guarantees and empirical demonstrations of the proposed methods across various generative models.
Paper analyzes holdout cross-validation for large non-Gaussian covariance estimation.
problem Estimating large covariance matrices for non-Gaussian data.
method Use of Weingarten calculus and Ledoit-Péché formula for theoretical error derivation.
result Optimal train-test split ratio is proportional to square root of matrix dimension.
Study the impact of overfitting on linear predictive models' performance.
problem Overfitting reduces the out-of-sample performance of linear predictive trading strategies.
method Computed in- and out-of-sample means and variances of PnLs to derive replication ratios.
result Replication ratio diminishes for complex strategies with many assets.
We apply the procedure of Lee et al. to the problem of performing inference on the signal-noise ratio of the asset which displays maximum sample Sharpe ratio over a set of possibly correlated assets. We find a multivariate analogue of the commonly used approximate standard error of the Sharpe ratio to use in this condi…
Efficient algorithms for online learning with changing action sets, achieving no-approximate-regret guarantees.
problem Online learning with sleeping experts/bandits, where only a subset of actions are available each time.
method Developed computationally efficient algorithms providing no-approximate-regret guarantees for the general problem and better approximation ratios for special cases.
result Achieved no-approximate-regret guarantees for the general sleeping expert/bandit problems and better approximation ratios for specific cases.
Paper proposes a novel approach to density ratio estimation using projection pursuit.
problem Density ratio estimation challenges in high dimensions and model misspecification.
method The approach uses projection pursuit to approximate density ratios, addressing high dimensionality and model flexibility issues.
result The proposed estimator is consistent and converges at a certain rate, outperforming existing methods in experiments.
Improved predictive posterior density estimation through optimized importance sampling.
problem Low signal-to-noise ratio in posterior predictive densities.
method Optimized importance sampling using a test-time variational proxy.
result Significantly improved estimates of predictive posterior densities.
Unified framework for robust, stable, and efficient density ratio estimation.
problem Density-chasm and support-chasm problems in density ratio estimation.
method Dequantified diffusion-Schrödinger bridge (D3RE) framework with DDBI and DSBI.
result Offers uniform approximation and bounded time scores in theory and empirical performance.
The paper defines fair profit sharing ratios in Islamic PL contracts.
problem Determining fair profit sharing ratios in Islamic PL contracts.
method Introduces c-fair profit sharing ratios and uses econometrics models to compute or approximate them. result Elucidates the relation between profit sharing ratios and economic factors.
Theoretical analysis of entropy approximation for Gaussian mixtures.
problem Lack of theoretical guarantees for entropy approximation of Gaussian mixtures.
method Theoretical analysis of the error between true and approximate entropy.
result The error converges to zero as the ratios of means to variances tend to infinity, providing a guarantee for high-dimensional problems.
Proposes CLUB for reliable MI minimization in high dimensions.
problem Estimating and minimizing mutual information in high-dimensional spaces.
method Contrastive Log-ratio Upper Bound (CLUB) for MI minimization.
result CLUB provides reliable estimation of mutual information.
This research solves Plateau's problem for CRPC surfaces.
problem Constructing surfaces with constant ratio of principal curvatures.
method Proposed a family of surfaces containing a given minimal surface without flat points.
result Obtained a partial solution to Plateau's problem for CRPC surfaces.
wd1 improves reasoning in dLLMs by optimizing policies without policy ratios.
problem Improving reasoning in diffusion-based large language models through RL.
method wd1: ratio-free policy optimization using weighted log-likelihood.
result wd1 outperforms diffusion-based GRPO while requiring lower computational cost.
Noise increases the Rashomon ratio, leading simpler models to perform similarly to complex ones.
problem Why simpler models perform similarly to complex models on noisy datasets.
method Analyzed the data generation process and model training choices, introduced pattern diversity.
result Noisier datasets lead to larger Rashomon ratios, explaining simpler models' performance.