We analyze bias-variance of margin losses.
problem Understanding model overfitting/underfitting.
method Bias-variance decomposition for strictly convex margin losses.
result Expected risk decomposes into central model risk and data variation.
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,657 papers · 148 categories
Trend · papers per month
48 results for “convex margin”
Support vector regression (SVR) is one of the most popular machine learning algorithms aiming to generate the optimal regression curve through maximizing the minimal margin of selected training samples, i.e., support vectors. Recent researchers reveal that maximizing the margin distribution of whole training dataset ra…
We present an improved algorithm for {\em quasi-properly} learning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polyhedron as an intersection of about halfspaces with constant-size margins in time polynomial in (where is the nu…
Graphical models trained using maximum likelihood are a common tool for probabilistic inference of marginal distributions. However, this approach suffers difficulties when either the inference process or the model is approximate. In this paper, the inference process is first defined to be the minimization of a convex f…
Paper proposes a new classifier for hyperbolic spaces using horospherical boundaries.
problem Optimization of large margin classifiers in hyperbolic spaces.
method Horospherical decision boundaries for geodesically convex optimization.
result Geodesically convex optimization leads to globally optimal solutions.
Consider a classification problem where we have both labeled and unlabeled data available. We show that for linear classifiers defined by convex margin-based surrogate losses that are decreasing, it is impossible to construct any semi-supervised approach that is able to guarantee an improvement over the supervised clas…
New algorithms recover clusters with minimal queries, connecting margins to recoverability.
problem Active cluster recovery with oracle queries for minimal cost.
method Introducing margin-based clustering, designing algorithms for various spaces.
result Achieve queries for general pseudometric spaces and convex clusters.
Study minimax rates for binary classifier estimation with margin conditions.
problem Estimating binary classifiers with geometric margin conditions.
method Derive lower bounds for worst-case learning rates over various function classes.
result Identify optimal rates close to for different function classes.
This paper tackles multi-marginal optimal transport problems using DC programming.
problem Multi-marginal optimal transport problems in machine learning.
method Promoting structural information in MMOT leads to a DC programming problem.
result Solutions from DC optimization are as qualitative as current methods.
Existence proved for -Bass martingales with specific marginals.
problem Constructing martingales with prescribed marginals close to a reference measure.
method Geometric analysis of parametrized convex polygonal chains.
result Existence and uniqueness of -Bass martingales with finitely supported initial marginals.
Recent research has used margin theory to analyze the generalization performance for deep neural networks (DNNs). The existed results are almost based on the spectrally-normalized minimum margin. However, optimizing the minimum margin ignores a mass of information about the entire margin distribution, which is crucial …
We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of…
A scalable algorithm approximates Wasserstein Barycenters using neural networks.
problem Representing the weighted mean of probability distributions in high dimensions.
method Input Convex Neural Networks (ICNNs) for Kantorovich dual formulation of Wasserstein-2 distance.
result Generative model representation of the Barycenter with infinite samples.
Algorithm learns dynamics from past observations.
problem Learning a nonlinear dynamical system.
method Spectral filtering, online convex optimization.
result Vanishing prediction error for marginally stable systems.
Paper analyzes GMM for separable data with various parameter structures.
problem Classifying separable data with logistic models and their generalizations.
method Introduces and analyzes Generalized Margin Maximizer (GMM) for logistic models with specific parameter structures.
result GMM outperforms max-margin classifiers in various parameter settings and structures.
A new method for optimal transport using neural ODEs that preserves marginal constraints.
problem Optimal transport between two continuous distributions with specific cost functions.
method Iterative construction of neural ODEs to minimize transport cost while preserving marginal constraints.
result Monotonic interior approach that decreases transport cost efficiently.
The popular Lasso approach for sparse estimation can be derived via marginalization of a joint density associated with a particular stochastic model. A different marginalization of the same probabilistic model leads to a different non-convex estimator where hyperparameters are optimized. Extending these arguments to pr…
We address the problem of aggregating an ensemble of predictors with known loss bounds in a semi-supervised binary classification setting, to minimize prediction loss incurred on the unlabeled data. We find the minimax optimal predictions for a very general class of loss functions including all convex and many non-conv…
We propose in this paper a general framework for deriving loss functions for structured prediction. In our framework, the user chooses a convex set including the output space and provides an oracle for projecting onto that set. Given that oracle, our framework automatically generates a corresponding convex and smooth l…
It is well known that a random vector with given marginal distributions is comonotonic if and only if it has the largest sum with respect to the convex order [ Kaas, Dhaene, Vyncke, Goovaerts, Denuit (2002), A simple geometric proof that comonotonic risks have the convex-largest sum, ASTIN Bulletin 32, 71-80. Cheung (2…
Marginal MAP inference involves making MAP predictions in systems defined with latent variables or missing information. It is significantly more difficult than pure marginalization and MAP tasks, for which a large class of efficient and convergent variational algorithms, such as dual decomposition, exist. In this work,…
A new relaxed framework for pricing illiquid derivatives using bid-ask spreads.
problem Pricing illiquid derivatives with realistic bounds and hedging prices.
method Introducing Bid--Ask Martingale Optimal Transport (BAMOT) that relaxes the exact calibration of model marginals to mid-prices of vanilla options.
result BAMOT yields realistic price bounds and superhedging prices for illiquid derivatives.
This paper characterizes the equilibrium in a continuous time financial market populated by heterogeneous agents who differ in their rate of relative risk aversion and face convex portfolio constraints. The model is studied in an application to margin constraints and found to match real world observations about financi…
Proposes MGCE for improved classification performance.
problem Optimizing between robustness and optimization difficulty in classification.
method Minimax formulation of GCE leading to convex optimization over margins.
result MGCE achieves strong accuracy and better calibration, especially in noisy labels.
Researchers find a way to price American options without relying on specific asset price models.
problem Determining the upper bound on the price of American options under model uncertainty.
method Using martingale optimal transport problem to describe model uncertainty and proving that optimal exercise schemes must be nonrandomized under certain conditions.
result The price upper bound and its relaxed version coincide under suitable convexity conditions, removing the need for the model-free price upper bound to be nonrandomized.
We carefully study how well minimizing convex surrogate loss functions, corresponds to minimizing the misclassification error rate for the problem of binary classification with linear predictors. In particular, we show that amongst all convex surrogate losses, the hinge loss gives essentially the best possible bound, o…
The Skorokhod embedding problem aims to represent a given probability measure on the real line as the distribution of Brownian motion stopped at a chosen stopping time. In this paper, we consider an extension of the optimal Skorokhod embedding problem to the case of finitely-many marginal constraints. Using the classic…
A fast method for training linear classifiers maximizes margins.
problem Training linear classifiers with maximum margins.
method Momentum-based gradient method derived from convex dual with Nesterov acceleration.
result Exponentially faster convergence rate compared to standard methods.
New algorithm learns halfspaces with near-optimal sample complexity in noisy conditions.
problem Learning margin halfspaces with Massart noise.
method Computational efficient algorithm using online SGD on carefully selected convex losses.
result Sample complexity of , nearly matching lower bound.
Data augmentation (DA) is commonly used during model training, as it significantly improves test error and model robustness. DA artificially expands the training set by applying random noise, rotations, crops, or even adversarial perturbations to the input data. Although DA is widely used, its capacity to provably impr…
Non-convex SGD learns halfspaces with adversarial label noise efficiently.
problem Agnostically learning halfspaces in adversarial label noise settings.
method Non-convex SGD optimization for halfspace learning.
result Non-convex SGD achieves misclassification error close to optimal with adversarial noise.
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…
Worst-case bounds on the expected shortfall risk given only limited information on the distribution of the random variables has been studied extensively in the literature. In this paper, we develop a new worst-case bound on the expected shortfall when the univariate marginals are known exactly and additional expert inf…
Support vector machine (SVM) has attracted great attentions for the last two decades due to its extensive applications, and thus numerous optimization models have been proposed. To distinguish all of them, in this paper, we introduce a new model equipped with an soft-margin loss (dubbed as -SVM) whic…
GD at EoS edge minimizes logistic loss without monotonic convergence.
problem Understanding GD's implicit bias at the edge of stability.
method Theoretical analysis of logistic regression with constant stepsize GD.
result GD with any constant stepsize minimizes logistic loss over long time scales.
We solve the -marginal Skorokhod embedding problem for a continuous local martingale and a sequence of probability measures which are in convex order and satisfy an additional technical assumption. Our construction is explicit and is a multiple marginal generalisation of the Azema and Yor (1979) soluti…
Estimate Collapsibility of Causal Effects in Completed Partial DAGs via Strong d-Convex Hullsstat.ML
Estimate collapsibility of causal effects in CPDAGs via strong d-convex hulls.
problem Estimate causal effects in CPDAGs.
method Use strong d-convex hulls to characterize minimal collapsible sets.
result Efficient algorithm for obtaining collapsible sets in DAGs and CPDAGs.
We consider the problem of covariance matrix estimation in the presence of latent variables. Under suitable conditions, it is possible to learn the marginal covariance matrix of the observed variables via a tractable convex program, where the concentration matrix of the observed variables is decomposed into a sparse ma…
Learning Classifiers with Fenchel-Young Losses: Generalized Entropies, Margins, and Algorithmsstat.ML
This paper studies Fenchel-Young losses, a generic way to construct convex loss functions from a regularization function. We analyze their properties in depth, showing that they unify many well-known loss functions and allow to create useful new ones easily. Fenchel-Young losses constructed from a generalized entropy, …
We define a novel class of distances between statistical multivariate distributions by modeling an optimal transport problem on their marginals with respect to a ground distance defined on their conditionals. These new distances are metrics whenever the ground distance between the marginals is a metric, generalize both…
New study reveals a polynomial penalty for adapting to unknown margin parameters in batched nonparametric bandits.
problem Adapting to an unknown margin parameter in batched nonparametric bandits.
method Introduces the regret inflation criterion and develops RoBIN algorithm to achieve optimal regret inflation.
result The optimal regret inflation grows polynomially with the horizon T, characterized by a convex optimization problem.
Study shows uniform-time chaos propagation in mean field Langevin dynamics.
problem Understanding the convergence of marginal distributions in mean field dynamics.
method Assumed functional convexity of energy, used -convergence and Wasserstein metrics.
result Uniform-in-time propagation of chaos proved in both -Wasserstein and relative entropy.
This paper focuses on martingale optimal transport problems when the martingales are assumed to have bounded quadratic variation. First, we give a result that characterizes the existence of a probability measure satisfying some convex transport constraints in addition to having given initial and terminal marginals. Sev…
Recent research has made significant progress on the problem of bounding log partition functions for exponential family graphical models. Such bounds have associated dual parameters that are often used as heuristic estimates of the marginal probabilities required in inference and learning. However these variational est…
Gradient descent finds halfspaces with low error for agnostic learning.
problem Agnostic learning of linear halfspaces with convex surrogates.
method Gradient descent on convex surrogates for zero-one loss.
result Gradient descent finds halfspaces with error in poly time and sample complexity.
The aims of this study are twofold. First, we consider an optimal risk allocation problem with non-convex preferences. By establishing an infimal representation for distortion risk measures, we give some necessary and sufficient conditions for the existence of optimal and asymptotic optimal allocations. We will show th…
Learning with non-modular losses is an important problem when sets of predictions are made simultaneously. The main tools for constructing convex surrogate loss functions for set prediction are margin rescaling and slack rescaling. In this work, we show that these strategies lead to tight convex surrogates iff the unde…
New method controls linear systems with adversarial disturbances.
problem Controlling linear dynamical systems under adversarial conditions.
method Novel convex relaxation using spectral filters from Hankel matrix eigenvectors.
result Polylogarithmic running time improvement over prior methods.