We study compositional generalization, viz., the problem of zero-shot generalization to novel compositions of concepts in a domain. Standard neural networks fail to a large extent on compositional learning. We propose Tree Stack Memory Units (Tree-SMU) to enable strong compositional generalization. Tree-SMU is a recurs…
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,742 papers · 148 categories
Trend · papers per month
48 results for “compositional function trees”
This paper shows that scientific discovery can be efficiently learned via compositional function trees, reducing the sample complexity.
problem Statistical and computational intractability of scientific discovery via symbolic regression.
method PAC learning approach focusing on compositional function trees built from a finite vocabulary of smooth operators.
result The Rademacher complexity and excess risk are controlled by depth and Lipschitz constants of the base operators, leading to finite-union bounds and high-probability risk bounds.
PolyILR: A Tree-Structured Orthonormal Decomposition of Compositional Data
problem Representing compositional data with hierarchical structure
method PolyILR: A canonical orthonormal decomposition of the Aitchison tangent space aligned with any tree topology
result PolyILR yields stable, interpretable features and enables inference at multiscale tree resolution
Deep networks learn sparse hierarchical features without CoD.
problem Overparameterized deep networks struggle with the curse of dimensionality.
method Norm-constrained neural networks for sparse compositional functions.
result Deep networks can learn sparse hierarchical features efficiently.
In this paper, we propose a compositional nonparametric method in which a model is expressed as a labeled binary tree of nodes, where each node is either a summation, a multiplication, or the application of one of the basis functions to one of the covariates. We show that in order to recover a labeled bi…
Any function can be constructed using a hierarchy of simpler functions through compositions. Such a hierarchy can be characterized by a binary rooted tree. Each node of this tree is associated with a function which takes as inputs two numbers from its children and produces one output. Since thinking about functions in …
Tree-AMP simplifies inference in complex tree-structured models.
problem Inference in high-dimensional tree-structured models.
method Approximate Message Passing algorithms for various machine learning tasks.
result Theoretical performance predictions and automated entropy estimation.
We construct a small regular cellular decomposition of the Fulton MacPherson operad that is compatible with the operad composition. The cells are indexed by trees with edges of two colors and vertices labelled by cells of the cacti operad. We compute the generating functions counting the cells, that are algebrai…
New model identifies microbial subcommunities robustly, accounting for cross-sample heterogeneity.
problem Inference in LDA is sensitive to the number of subcommunities and often creates artificial ones.
method Incorporates logistic-tree normal (LTN) model into LDA to account for cross-sample heterogeneity.
result Restores robustness of inference and identifies meaningful subcommunities.
New method wraps black-box classifiers to reduce bias.
problem Reduction of bias in black-box predictions.
method Post-processing with α-trees and boosting algorithms.
result Demonstrated effectiveness in reducing bias across multiple fairness metrics.
Compositional structures between parts and objects are inherent in natural scenes. Modeling such compositional hierarchies via unsupervised learning can bring various benefits such as interpretability and transferability, which are important in many downstream tasks. In this paper, we propose the first deep latent vari…
End-to-end learning framework for tree-structured data.
problem Learning models struggle with tree-structured data due to lack of fixed-length vectors.
method Developed a novel framework for generic semantic tree-structured data of arbitrary topology.
result Framework yields comparable performance to standard models with dedicated feature-vectors and outperforms in compositional data.
Develops new optimization techniques for decision-making under uncertainty.
problem Decision-making under uncertainty with complex cost functions and nested expectations.
method Introduces Multistage Conditional Compositional Optimization (MCCO) and develops multilevel Monte Carlo techniques.
result New optimization techniques reduce scenario complexity from exponential to polynomial growth.
Decision trees perform well in complex interactions, even when interactions are not fully accounted for.
problem Interpreting complex interactions in machine learning models.
method Experiments on datasets and two methods for robust GLMs.
result Tree depth compensates for model misspecification, enhancing performance in complex scenarios.
Algorithm infers sampling distribution from i.i.d. samples without supervision.
problem Learning probability distributions from unlabeled data.
method Unsupervised tree boosting using additive tree ensembles and new distributional operations.
result Algorithm outperforms deep learning in multivariate density estimation.
Estimates density ratio for two-sample comparison using tree models.
problem Comparing two distributions given i.i.d. observations.
method Additive tree models with balancing loss for density ratio estimation.
result Bayesian inference provides uncertainty quantification for density ratio.
Multistage Defer Trees improve model accuracy while maintaining interpretability.
problem Balancing model accuracy and interpretability, especially in noisy domains.
method A sequence of sparse decision trees that defer predictions to the next tree or a black box.
result Matches the performance of complex tree-based ensembles while using only one or a few sparse trees.
A new decision tree induction method using MIP for faster optimization.
problem Optimizing decision tree split rules for better classification performance.
method Mixed-integer programming (MIP) for Gini reduction maximization, efficient search algorithm.
result bsnsing trees outperform other tree models in new case discrimination.
Composition of Fractalsmath.MG
This work is an analytical and numerical study of the composition of several fractals into one and of the relation between the composite dimension and the dimensions of the component fractals. In the case of composition of standard IFS with segments of equal size, the composite dimension can be expressed as a function …
Diffusion models learn hierarchical composition rules from data.
problem How many samples do generative models need to learn hierarchical composition rules?
method Theoretical and empirical investigation of diffusion models on probabilistic context-free grammars.
result Diffusion models learn hierarchical composition rules with sample complexity scaling polynomially with context size.
Study on deep neural networks using branching processes and Mehler's formula.
problem Understanding the mathematical role of activation functions in compositional neural networks.
method Connection between compositional kernels and branching processes via Mehler's formula; new random features algorithm.
result Explicit formulas for eigenvalues of compositional kernels quantify complexity.
Deviance-style normalization for sparse, jointly overdispersed count matrices
problem Jointly overdispersed count matrices
method Dirichlet-multinomial deviance residualization
result Preserves exact sparsity, evaluates in constant time, recovers multinomial residual
The stochastic gradient descent has been widely used for solving composite optimization problems in big data analyses. Many algorithms and convergence properties have been developed. The composite functions were convex primarily and gradually nonconvex composite functions have been adopted to obtain more desirable prop…
This paper explores optimising acquisition functions in Bayesian optimisation.
problem Optimising acquisition functions in Bayesian optimisation is challenging due to their non-convex nature.
method The authors derive compositional forms for acquisition functions and use them to recast maximisation as a compositional optimisation problem.
result The compositional approach to maximising acquisition functions shows empirical advantages across various tasks.
PDEs constrain smooth functions in neural networks.
problem Understanding functions computable by neural networks.
method Analyzing smooth hierarchical functions via PDEs.
result Established algebraic PDEs for smooth functions.
Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimizationstat.ML
Stochastic compositional optimization arises in many important machine learning tasks such as value function evaluation in reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic functions, and is more challenging to optimize than vanilla stochastic o…
Improved subgradient method tackles ill-conditioned composite optimization problems.
problem Slow convergence of subgradient method for composite optimization problems.
method Preconditioned subgradient method with Levenberg-Marquardt approach.
result Linear convergence rate for composite optimization problems under mild conditions.
Gaussian processes struggle with compositional functions, but deep Gaussian processes can outperform.
problem Gaussian process regression struggles with compositional functions.
method We study information-theoretic lower bounds for posterior contraction rates in Gaussian process regression for a continuous regression model.
result Posterior based on any mean-zero Gaussian process can only recover the truth at a rate strictly slower than the minimax rate for generalized additive functions.
Many machine learning, statistical inference, and portfolio optimization problems require minimization of a composition of expected value functions (CEVF). Of particular interest is the finite-sum versions of such compositional optimization problems (FS-CEVF). Compositional stochastic variance reduced gradient (C-SVRG)…
C-ADAM is a new adaptive solver for complex nested problems.
problem Solving compositional problems involving nested expected values.
method Adaptive solver for non-linear functional nesting of expected values.
result C-ADAM converges to a stationary point in .
In the past few years, off-policy reinforcement learning methods have shown promising results in their application for robot control. Deep Q-learning, however, still suffers from poor data-efficiency and is susceptible to stochasticity in the environment or reward functions which is limiting with regard to real-world a…
Composition operators on reproducing kernel Hilbert spaces with analytic positive definite functionsmath.FA
In this paper, we specify what functions induce the bounded composition operators on a reproducing kernel Hilbert space (RKHS) associated with an analytic positive definite function defined on . We prove that only affine transforms can do so in a pretty large class of RKHS. Our result covers not only the …
Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problemmath.OC
In this paper, we consider the convex and non-convex composition problem with the structure , where is the inner function, and is the outer function. We explore the variance reduction based met…
Deep neural networks can approximate complex functions through repeated compositions of a fixed-size ReLU network.
problem Understanding the expressive power of deep neural networks through function compositions.
method Demonstrated the surprising expressive power of repeated compositions of a single fixed-size ReLU network.
result Repeated compositions of a single fixed-size ReLU network can approximate 1-Lipschitz continuous functions on with an error .
Capsule networks improve at detecting changes in compositionality with routing.
problem Capsule networks struggle with detecting changes in compositionality.
method Introduced a loss function based on routing entropy to improve compositionality.
result Capsule networks with the new loss function better detect changes in compositionality.
We consider composite loss functions for multiclass prediction comprising a proper (i.e., Fisher-consistent) loss over probability distributions and an inverse link function. We establish conditions for their (strong) convexity and explore the implications. We also show how the separation of concerns afforded by using …
Composite Binary Lossesstat.ML
We study losses for binary classification and class probability estimation and extend the understanding of them from margin losses to general composite losses which are the composition of a proper loss with a link function. We characterise when margin losses can be proper composite losses, explicitly show how to determ…
An inexact LPA for DC composite optimization and application to matrix completions with outliersmath.OC
Paper proposes iLPA for solving DC composite optimization problems, with applications to matrix completion with outliers.
problem Solving nonconvex and nonsmooth DC composite optimization problems.
method Inexact linearized proximal algorithm (iLPA) for DC composite optimization problems.
result The iLPA achieves local R-linear convergence rate under the Kurdyka-Łöjasiewicz property.
New framework infers multiple classes per image for one-shot learning.
problem Inferring multiple classes per image in one-shot learning.
method Compositional embedding framework with joint training of embedding and composition/query functions.
result Compositional embedding models outperform existing methods on various datasets.
We consider the problem of minimizing the composition of a smooth (nonconvex) function and a smooth vector mapping, where the inner mapping is in the form of an expectation over some random variable or a finite sum. We propose a stochastic composite gradient method that employs an incremental variance-reduced estimator…
We consider the composition optimization with two expected-value functions in the form of , { which formulates many important problems in statistical learning and machine learning such as solving Bellman equations in reinforcement l…
Deep learning can learn compositional functions more efficiently by breaking them into stages.
problem Understanding why deep learning performs better than shallow models in learning compositional functions.
method Analyzed learnability of compositional target functions using a three-layer fitting model trained with layer-wise spectral estimators.
result Learning compositional functions can be simplified by breaking them into stages, reducing the complexity of the learning problem.
BoostForest combines multiple BoostTree models for improved accuracy.
problem Improving ensemble learning performance.
method BoostTree uses gradient boosting and random cut-points. BoostForest bootstraps training data and randomly samples parameters.
result BoostForest outperforms classical ensemble methods on 35 datasets.
BARK optimizes black-box functions using Bayesian Additive Regression Trees.
problem Bayesian optimization of complex, black-box functions with uncertainty quantification.
method BART Kernel using tree agreement for posterior over piecewise-constant functions, explored using MCMC.
result BARK obtains samples of Gaussian processes for function distributions, enabling acquisition functions for optimization.
Sublinearly structured DNNs achieve feature learning consistency for compositional functions.
problem Achieving feature-learning and prediction consistency in deep neural networks.
method Sublinearly structured DNNs
result Sublinearly structured DNNs match or surpass wide DNNs in prediction.
A new variational method speeds up Bayesian phylogenetic inference.
problem Slow and inefficient MCMC methods in Bayesian phylogenetic inference.
method Combining subsplit Bayesian networks with variational inference for efficient tree topology and branch length estimation.
result Variational approach provides competitive performance with significantly fewer iterations.
Defines 'nowhere coexpanding functions' and studies their fixed points.
problem Understanding fixed points of nowhere coexpanding functions.
method Defines and studies nowhere coexpanding functions, including functions with non-positive Schwarzian derivative.
result Establishes results on the number and nature of fixed points, generalizing Singer's result.
Choosing the most adequate kernel is crucial in many Machine Learning applications. Gaussian Process is a state-of-the-art technique for regression and classification that heavily relies on a kernel function. However, in the Gaussian Process literature, kernels have usually been either ad hoc designed, selected from a …