PARC uses piecewise linear predictors for regression and classification.
problem Multivariate regression and classification problems.
method Alternates between ridge and softmax regression, and cluster assignment based on accuracy and separability.
result Converges to a local minimum in a finite number of steps.
New GP model estimates piecewise continuous functions.
problem Piecewise continuous regression functions in scientific and engineering applications.
method Local Gaussian process model with partitioned local data and joint estimation of boundaries.
result Superior performance over conventional GP models in estimating piecewise regression functions.
New method uses DC functions for piecewise linear regression.
problem Regression with piecewise linear constraints.
method Estimates piecewise linear convex functions using a difference of convex functions.
result Method achieves close to minimax statistical risk and comparable performance to existing methods.
Proposes adaptive ridge regression for functional linear models with piecewise shapes.
problem Functional linear regression with unknown coefficient function.
method Adaptive piecewise function template with L2 penalization. result Improves predictive power and interpretability compared to standard methods.
We present a detailed analysis of the class of regression decision tree algorithms which employ a regulized piecewise-linear node-splitting criterion and have regularized linear models at the leaves. From a theoretic standpoint, based on Rademacher complexity framework, we present new high-probability upper bounds for …
Paper presents ABGD for efficient piecewise linear regression in high dimensions.
problem Efficiently solving piecewise linear regression in high-dimensional spaces.
method Parametrizes piecewise linear functions as difference of max-affine functions, using ABGD algorithm.
result ABGD converges linearly to an ε-accurate estimate with optimal sample complexity.
Efficiently recovers piecewise linear functions from noisy samples.
problem Recovering a piecewise linear function from noisy samples with unknown segmentation.
method Iterative merging approach for multidimensional segmented regression.
result First sample and computationally efficient algorithm in any fixed dimension.
The problem of subgroups is ubiquitous in scientific research (ex. disease heterogeneity, spatial distributions in ecology...), and piecewise regression is one way to deal with this phenomenon. Morse-Smale regression offers a way to partition the regression function based on level sets of a defined function and that fu…
XGBoost is often presented as the algorithm that wins every ML competition. Surprisingly, this is true even though predictions are piecewise constant. This might be justified in high dimensional input spaces, but when the number of features is low, a piecewise linear model is likely to perform better. XGBoost was exten…
BART and MOTR-BART improve tree-based predictions with local linear models.
problem Non-linearity and high-order interactions in data.
method Bayesian Additive Regression Trees (BART) and Model Trees BART (MOTR-BART) using piecewise linear functions.
result MOTR-BART achieves equal or better performance with fewer trees than BART.
We consider the generic regularized optimization problem β^(λ)=argminβL(y,Xβ)+λJ(β). Efron, Hastie, Johnstone and Tibshirani [Ann. Statist. 32 (2004) 407--499] have shown that for the LASSO--that is, if L is squared error loss and J(β)=∥β∥1 is the ℓ1 norm of β--the opti…
Paper introduces ℓ-DER for regression tasks using morphological operators and convex-concave procedure.
problem Developing a universal approximator for regression tasks.
method Introduces ℓ-DER model, trains it using a convex-concave procedure (CCP) to minimize least-squares. result Outperforms other hybrid morphological models and state-of-the-art approaches.
Efficiently finds sparse solutions to max-plus equations for convex regression.
problem Finding sparse solutions to max-plus equations for convex multivariate regression.
method Polynomial-time algorithm for sparse approximate solutions.
result Optimal piecewise-linear fitting with minimum number of regions.
The fused lasso is analyzed for high-dimensional piecewise-constant regression coefficients.
problem Estimation of high-dimensional piecewise-constant regression coefficients.
method Formulated a restricted isometry condition for the fused lasso estimator and derived estimation bounds.
result The estimation error can be dominated by either the lasso or the fused lasso rate, depending on the number of non-zero coefficients and piece-wise constant segments.
Max-affine regression method converges linearly using GD and SGD.
problem Regression of max-affine models in signal processing and statistics.
method Gradient descent and mini-batch stochastic gradient descent analysis.
result GD and SGD converge linearly to a neighborhood of the ground truth under sub-Gaussian assumptions.
Paper proposes a new method for selective inference in robust regression.
problem Statistical inference after removing outliers identified by robust methods.
method Conditional SI using piecewise-linear homotopy continuation.
result Proposed method is applicable to a wide class of robust regression and outlier detection methods.
The paper deals with regression problems, in which the nonsmooth target is assumed to switch between different operating modes. Specifically, piecewise smooth (PWS) regression considers target functions switching deterministically via a partition of the input space, while switching regression considers arbitrary switch…
In this paper, we investigate adaptive nonlinear regression and introduce tree based piecewise linear regression algorithms that are highly efficient and provide significantly improved performance with guaranteed upper bounds in an individual sequence manner. We use a tree notion in order to partition the space of regr…
This paper introduces a new method to better understand financial market causality.
problem Lack of comprehensive understanding of distributional causality in financial markets.
method Combines piecewise quantile regression with a piecewise linear embedding scheme.
result Uncovered significant tail-tail causal effects and substantial causal asymmetry in cryptocurrency return series.
Paper proposes algorithms to accurately identify breakpoints in piecewise regression.
problem Identifying accurate breakpoints in piecewise regression for better data fitting.
method Proposes novel greedy algorithms to minimize error and determine optimal breakpoints.
result The proposed algorithms outperform existing methods in accuracy and efficiency.
This technical note extends recent results on the computational complexity of globally minimizing the error of piecewise-affine models to the related problem of minimizing the error of switching linear regression models. In particular, we show that, on the one hand the problem is NP-hard, but on the other hand, it admi…
Exact LAD line fitting via PALB with linear scaling and speed.
problem Robust line fitting for data with outliers.
method Piecewise Affine Lower-Bounding (PALB) method using supporting lines and subdivision scheme.
result Empirical log-linear scaling and significantly faster than LP and IRLS methods.
SyMPLER improves time series forecasting in nonstationary environments with explainable models.
problem Nonstationary time series forecasting with limited interpretability.
method Dynamic piecewise-linear approximations based on Statistical Learning Theory generalization bounds.
result SyMPLER achieves comparable performance to black-box and explainable models while maintaining interpretability.
Tropical Geometry and Mathematical Morphology share the same max-plus and min-plus semiring arithmetic and matrix algebra. In this chapter we summarize some of their main ideas and common (geometric and algebraic) structure, generalize and extend both of them using weighted lattices and a max-⋆ algebra with an ar…
New algorithm predicts piecewise regular functions online.
problem Online prediction of piecewise regular functions.
method Modified sleeping experts aggregation algorithm.
result Oracle risk bounds for all local regions.
Modified ReLU networks improve regression estimation rates.
problem Regression estimation with smooth functions.
method Using modified ReLU neural networks with specific weight modifications.
result Empirical risk minimizers achieve minimax rate of prediction.
SGD trains ReLU networks to implement piecewise linear maps with at most 3 knot points.
problem Understanding the training dynamics of neural networks trained via SGD.
method Mean-field analysis of a two-layer ReLU network trained via SGD for a univariate regression problem.
result At convergence, SGD-trained ReLU networks implement piecewise linear maps with at most 3 knot points.
A method for identifying NPWARX models with arbitrary domains using probabilistic mixture models.
problem Identifying hybrid system models with discontinuous maps.
method Probabilistic mixture model with a neural network for nonlinear partitioning and Expectation Maximization for parameter estimation.
result Demonstrated on a nonlinear piece-wise problem with discontinuous maps.
New method samples from piecewise smooth distributions using Hamiltonian Monte Carlo.
problem Sampling from distributions with discontinuous gradients.
method Generalized Randomized Hamiltonian Monte Carlo (GRHMC) for piecewise smooth targets.
result GRHMC processes sample from piecewise smooth target distributions with the desired distribution as the invariant distribution.
The center of a quotient group of piecewise linear homeomorphisms is trivial.
problem Understanding the structure of a specific group of homeomorphisms.
method Analyzing a quotient of piecewise linear homeomorphisms of the real line.
result The center of the quotient group is trivial.
Convex regression is a promising area for bridging statistical estimation and deterministic convex optimization. New piecewise linear convex regression methods are fast and scalable, but can have instability when used to approximate constraints or objective functions for optimization. Ensemble methods, like bagging, sm…
This article provides an attempt to extend concepts from the theory of Riemannian manifolds to piecewise linear spaces. In particular we propose an analogue of the Ricci tensor, which we give the name of an Einstein vector field. On a given set of piecewise linear spaces we define and discuss (normalized) Ricci flows. …
Global approximation for piecewise linear paths via signatures.
problem Global approximation theorems for piecewise linear paths.
method Using signatures of piecewise linear paths and their density in Lp-norms. result Linear functionals of signatures are dense in Lp-norms under an integrability condition. This paper introduces a novel mixture model-based approach for simultaneous clustering and optimal segmentation of functional data which are curves presenting regime changes. The proposed model consists in a finite mixture of piecewise polynomial regression models. Each piecewise polynomial regression model is associat…
Investigates stability of piecewise flat Ricci flow using analysis and simulations.
problem Stability of piecewise flat Ricci flow.
method Linear stability analysis and numerical simulations.
result Adaptations avoided numerical instability and led to convergence to smooth solutions.
For various applications, the relations between the dependent and independent variables are highly nonlinear. Consequently, for large scale complex problems, neural networks and regression trees are commonly preferred over linear models such as Lasso. This work proposes learning the feature nonlinearities by binning fe…
We propose a new algorithm called PLUTO for building logistic regression trees to binary response data. PLUTO can capture the nonlinear and interaction patterns in messy data by recursively partitioning the sample space. It fits a simple or a multiple linear logistic regression model in each partition. PLUTO employs th…
CNR uses convex optimization to estimate conditional distributions.
problem Estimating uncertainty in predictions and posterior conditional distributions.
method Convex optimization of a posterior defined via non-linear transformations on Gaussians.
result CNR can fit arbitrary conditional distributions, including multimodal and non-symmetric ones.
We prove that every piecewise linear manifold of dimension up to four on which a finite group acts by piecewise linear homeomorphisms admits a compatible smooth structure with respect to which the group acts smoothly. This solves a challenge posed by Thurston in dimension three and confirms a conjecture by Kwasik and L…
Piecewise linear activations create many spurious local minima in neural networks.
problem Understanding the loss surface of neural networks with piecewise linear activations.
method Proved the existence of infinite spurious local minima and partitioned the loss surface into smooth cells.
result Piecewise linear activations create many spurious local minima that are invariant under a continuous path.
New analysis improves SGD for robust and quantile regression with sub-quadratic convergence.
problem Improving SGD for robust and quantile regression with sub-quadratic convergence.
method Piecewise Lyapunov function for first-order differentiable functions.
result First geometrical convergence result for sub-quadratic SGD.
Signature uniquely identifies piecewise linear surfaces up to thin homotopy.
problem Characterizing piecewise linear surfaces up to equivalence.
method Crossed module of piecewise linear surfaces and signature homomorphism.
result Signature uniquely characterizes surfaces up to translation and thin homotopy.
The paper extends a variance gamma model to quadratic functions, reducing arbitrage and computational costs.
problem Creating an arbitrage-free interpolation for option pricing models.
method Generalizing the local variance gamma model to a piecewise quadratic local variance function.
result The quadratic model results in an arbitrage-free interpolation of class C3, reducing knots and computational cost.
In this paper, we introduce a bordism category CdPL whose objects are bundles of closed (d−1)-dimensional piecewise linear manifolds and whose morphisms are bundles of d-dimensional piecewise linear cobordisms. In the main theorem of this article, we show that the classifying space $B\mathcal{C}_d^{…
First explicit isometric immersion of a flat Klein bottle in 3D space.
problem Finding an isometric embedding of a Klein bottle in 3D.
method Piecewise-linear map from a Klein bottle to Euclidean 3-space.
result Explicit numerical data for a flat Klein bottle isometrically immersed in 3D.
We propose learning deep models that are monotonic with respect to a user-specified set of inputs by alternating layers of linear embeddings, ensembles of lattices, and calibrators (piecewise linear functions), with appropriate constraints for monotonicity, and jointly training the resulting network. We implement the l…
GraN-GAN normalizes gradients for better GAN performance.
problem Improving image generation in GANs with piecewise linear discriminators.
method Piecewise Gradient Normalization (GraN) for input-dependent normalization.
result Significant performance gains in image generation across various datasets.
Paper proposes variational inference for piecewise-linear systems.
problem Intractability of switching dynamical systems.
method Variational approximation and expectation-maximization algorithms.
result Parameters can be estimated off-line, including the number of linear modes.