The reparameterization trick enables optimizing large scale stochastic computation graphs via gradient descent. The essence of the trick is to refactor each stochastic node into a differentiable function of its parameters and a random variable with fixed distribution. After refactoring, the gradients of the loss propag…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,978 papers · 148 categories
Trend · papers per month
48 results for “Concrete relaxations”
Switching linear dynamics improves model-based reinforcement learning and system identification.
problem Complex and nonlinear systems can be approximated by linear dynamical systems.
method Bayesian inference, Variational Autoencoders, Concrete relaxations.
result Improved accuracy in learning dynamics from partial and high-dimensional observations.
Improved clustering speed for 20 clusters on CIFAR-100 dataset.
problem Training time complexity for VAEs with discrete latent variables is linear in the number of clusters.
method Applied a continuous relaxation to discrete variables in Gaussian Mixture VAE, reducing training time complexity to constant.
result Reduced training time from 47 hours to 6 hours for 20 clusters on CIFAR-100.
On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examplesmath.OC
Geometric technique determines exactness of SDP robustness certificate.
problem Certifying robustness of neural networks to adversarial examples.
method Geometric projection onto hyperbola, SDP relaxation of ReLU activation.
result SDP certificate is exact for a single hidden layer under mild assumptions.
Rank minimization (RM) is a wildly investigated task of finding solutions by exploiting low-rank structure of parameter matrices. Recently, solving RM problem by leveraging non-convex relaxations has received significant attention. It has been demonstrated by some theoretical and experimental work that non-convex relax…
Framework improves GCNs for graphless and adversarial settings.
problem Improving GCNs without graph data and making them robust to adversarial attacks.
method Joint probabilistic model with variational inference and Concrete distributions.
result Framework outperforms state-of-the-art algorithms on semi-supervised classification.
CMDNet simplifies MAP detection for large systems with probabilistic relaxation.
problem High complexity of MAP detection in large systems.
method Probabilistic Continuous relaxation of discrete variables, iterative CMD algorithm, CMDNet with online optimization.
result CMDNet achieves a promising accuracy-complexity trade-off in MIMO systems.
Concrete Dropoutstat.ML
Dropout is used as a practical tool to obtain uncertainty estimates in large vision models and reinforcement learning (RL) tasks. But to obtain well-calibrated uncertainty estimates, a grid-search over the dropout probabilities is necessary - a prohibitive operation with large models, and an impossible one with RL. We …
Unified framework for learning with indirect supervision signals.
problem Learning from indirect supervision signals when gold labels are missing or costly.
method Developed a unified theoretical framework for multi-class classification with variable supervision.
result Introduced the concept of separation to characterize learnability and generalization bounds.
Concrete distribution properties examined on simplex.
problem Properties of Concrete distribution on simplex.
method Reflection and location-scale transformation of uniform distribution; explicit parameterization to Poincaré half-space.
result Fisher information and information metric are hyperbolic space; Fisher-Rao geodesic distance computed.
We compute Khovanov homology for tangles using TQFT.
problem Khovanov homology for tangles is not well studied or computed.
method Topological Quantum Field Theory (TQFT) construction.
result A comprehensive method for computing Khovanov homology of tangles.
We relax demographic parity in regression by enforcing parity at quantile levels and score thresholds.
problem Enforcing full distributional fairness in regression can lead to substantial accuracy loss.
method Introduce (, Z)-fair predictor, derive closed-form solutions, and develop post-processing algorithm.
result The risk gap to the continuous optimum vanishes as the grid is refined, and we enable targeted fairness corrections.
The paper tackles robust domain generalization by accounting for unobserved confounders.
problem Learning robust, generalizable models from multiple datasets in the presence of unobserved confounders.
method Defines a new invariance property for causal solutions, connects it to distributionally robust optimization, and incorporates regularization to encourage partial equality of error derivatives.
result Demonstrates the empirical effectiveness of the approach on healthcare data from various modalities.
Recognition of defects in concrete infrastructure, especially in bridges, is a costly and time consuming crucial first step in the assessment of the structural integrity. Large variation in appearance of the concrete material, changing illumination and weather conditions, a variety of possible surface markings as well …
We introduce the concrete autoencoder, an end-to-end differentiable method for global feature selection, which efficiently identifies a subset of the most informative features and simultaneously learns a neural network to reconstruct the input data from the selected features. Our method is unsupervised, and is based on…
New method improves neural network verification by considering multivariate input space of ReLU neurons.
problem Improving the effectiveness of neural network verification algorithms.
method A new tightened convex relaxation for ReLU neurons considering multivariate input space.
result Our convex relaxation is significantly stronger than the commonly used univariate-input relaxation.
Non-property (t) for SO(n,1)math.GT
Concrete proof that SO(n,1) is not a T-group.
problem Proving SO(n,1) is not a T-group.
method Constructed a concrete model for hyperbolic space and measure, proving hyperbolic distance equals measure up to a constant.
result Concrete proof that SO(n,1) is not a T-group.
Improving the Tightness of Convex Relaxation Bounds for Training Certifiably Robust Classifierscs.LG
New regularizers tighten convex relaxation bounds for neural networks.
problem Large gap between certifiable and empirical robustness in neural networks.
method Two regularizers to train neural networks yielding tighter convex relaxation bounds.
result Higher certified accuracy with proposed regularizers.
This work improves certifiably robust models by distilling knowledge from adversarially robust teachers.
problem Certifiably robust models suffer from poor standard performance.
method Knowledge distillation from adversarially robust teachers to improve standard performance.
result Distillation from adversarially robust teachers consistently improves certified training performance.
Improved neural network robustness certification through tighter convex relaxations.
problem Certifying neural network robustness to perturbed and adversarial inputs.
method Exploiting ReLU network structure, novel partition-based certification procedure.
result Tightens existing linear programming relaxations to achieve zero relaxation error asymptotically.
Paper introduces a new framework to improve sample efficiency in POMDPs learning.
problem Challenges in off-policy evaluation for POMDPs, especially with hidden states.
method Exploits the metric structure of belief space to relax coverage assumptions.
result Unified analysis technique yields tighter error bounds and sample efficiency improvements.
In this note we compare two recently proposed semidefinite relaxations for the sparse linear regression problem by Pilanci, Wainwright and El Ghaoui (Sparse learning via boolean relaxations, 2015) and Dong, Chen and Linderoth (Relaxation vs. Regularization A conic optimization perspective of statistical variable select…
Improves generative models by using heavy-tailed noise in score matching.
problem High-dimensional limitations of Gaussian noise in generative models.
method Extended DSM to generalised normal distribution, relaxed key assumptions, developed iterative noise scaling algorithm.
result Heavy-tailed DSM leads to improved generative performance.
Despite their impressive performance on diverse tasks, neural networks fail catastrophically in the presence of adversarial inputs---imperceptibly but adversarially perturbed versions of natural inputs. We have witnessed an arms race between defenders who attempt to train robust networks and attackers who try to constr…
We propose convex relaxations for convolutional neural nets with one hidden layer where the output weights are fixed. For convex activation functions such as rectified linear units, the relaxations are convex second order cone programs which can be solved very efficiently. We prove that the relaxation recovers the glob…
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite programming. In this paper, we study the statistical limits of convex relaxations. Particularly, we con…
Concrete example of 2-sphere with constant curvature 1 and closed geodesics.
problem Constructing a 2-sphere with constant curvature 1 and closed geodesics.
method Constructing a concrete example of a Finsler metric on the 2-sphere.
result A 2-sphere with constant Gauss curvature 1 and all geodesics closed.
In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong disadvantage that they lift the original -dimensional variable to an -d…
Statistical image reconstruction (SIR) methods are studied extensively for X-ray computed tomography (CT) due to the potential of acquiring CT scans with reduced X-ray dose while maintaining image quality. However, the longer reconstruction time of SIR methods hinders their use in X-ray CT in practice. To accelerate st…
The relaxed maximum entropy problem is concerned with finding a probability distribution on a finite set that minimizes the relative entropy to a given prior distribution, while satisfying relaxed max-norm constraints with respect to a third observed multinomial distribution. We study the entire relaxation path for thi…
Bayesian learning is often hampered by large computational expense. As a powerful generalization of popular belief propagation, expectation propagation (EP) efficiently approximates the exact Bayesian computation. Nevertheless, EP can be sensitive to outliers and suffer from divergence for difficult cases. To address t…
Regularization vs. Relaxation: A conic optimization perspective of statistical variable selectioncs.LG
Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an l0-norm penalty. Exactly enforcing the l0-no…
MAP inference for general energy functions remains a challenging problem. While most efforts are channeled towards improving the linear programming (LP) based relaxation, this work is motivated by the quadratic programming (QP) relaxation. We propose a novel MAP relaxation that penalizes the Kullback-Leibler divergence…
In this paper, we study a nonconvex continuous relaxation of MAP inference in discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this relaxation is tight, and a discrete stationary point of it can be easily reached by a simple block coordinate descent algorithm. In addition, we study the resolution …
Paper relaxes optimal transport using convex functions for data science.
problem Optimal transport problem on finite spaces.
method Relaxation via strictly convex functions (Kullback-Leibler divergence, Bregman divergences). Gradient descent iterative process.
result Mathematical foundations and iterative process for the relaxed optimal transport problem.
Modified EAT method improves Poisson gradient estimation.
problem Challenging differentiation through Poisson-distributed latent variables.
method Exponential Arrival Time (EAT) simulation with modifications and Gumbel-SoftMax relaxation.
result Modified EAT method provides unbiased first moment and reduced second-moment bias.
Sufficient conditions for the absence of relaxation gaps in state-constrained optimal controlmath.OC
New conditions prevent gaps in optimal control problems.
problem Preventing gaps in optimal control problems with state constraints.
method Developed new sufficient conditions not relying on convexity.
result Derived bounds for the size of the relaxation gap.
Study on proper learning under relaxed worst-case robust loss for VC classes.
problem Proper adversarially robust PAC learning under relaxed worst-case robust loss.
method Introduced a family of robust loss relaxations and showed their effectiveness for proper learnability.
result VC classes are properly PAC learnable with sample complexity close to standard PAC learning setup.
RELAX provides first attribution-based explanations for representations.
problem Lack of methods to explain what influences learned representations.
method RELAX, a first approach for attribution-based explanations of representations, measuring similarities in representation space.
result Significantly outperforms gradient-based baseline and models uncertainty in explanations.
A simple continuous relaxation for argsort improves performance and is easy to implement.
problem Discrete nature of argsort operator makes it unsuitable for gradient-based learning.
method Proposed a continuous relaxation for argsort operator that is simple, fast, and achieves state-of-the-art performance.
result The proposed relaxation achieves state-of-the-art performance and is faster than competing approaches.
This work proposes a method to integrate algorithms into neural networks using continuous relaxation.
problem Training neural networks with new forms of supervision like ordering constraints.
method Relaxing discrete conditions in control structures like conditional statements, loops, and indexing to make them differentiable.
result The proposed method can keep up with relaxations designed for specific tasks, showing general applicability.
Unified framework for gradient estimation in combinatorial spaces.
problem Scaling relaxed gradient estimators to large combinatorial distributions.
method Introducing stochastic softmax tricks within the perturbation model framework.
result Stochastic softmax tricks improve model performance and discover more latent structure.
Concrete description of infinite order cork automorphism.
problem Describing the infinite order loose-cork automorphism.
method Concatenating the defining ribbon disk by an infinite order isotopy.
result Concrete description of the infinite order cork automorphism.
New framework formalizes RLHF trilemma: improving safety, fairness, and robustness is computationally infeasible.
problem Aligning large language models with diverse human values while maintaining computational feasibility and robustness.
method Complexity-theoretic analysis integrating statistical learning theory and robust optimization.
result Achieving both representativeness (epsilon <= 0.01) and robustness (delta <= 0.001) for global-scale populations requires super-polynomial operations.
Spectral Clustering as a relaxation of the normalized/ratio cut has become one of the standard graph-based clustering methods. Existing methods for the computation of multiple clusters, corresponding to a balanced -cut of the graph, are either based on greedy techniques or heuristics which have weak connection to th…
Proves a simplified version of Hitchin's theorem.
problem Constructing hyper-Kähler structures.
method Concrete variant of Hitchin's theorem.
result Applies to real manifolds without constructing hyper-Kähler structures.
A number of recent work studied the effectiveness of feature selection using Lasso. It is known that under the restricted isometry properties (RIP), Lasso does not generally lead to the exact recovery of the set of nonzero coefficients, due to the looseness of convex relaxation. This paper considers the feature selecti…
We look at the meaning of 'relaxation' in the wealth exchange models that are recently proposed in Econophysics to interpret the wealth distributions. To quantify and characterise the process of relaxation, we define an appropriate quantity and evaluate that numerically for the systems of many agents. Also, the numeric…