Study connects spectral clustering to maximum margin and level set estimation.
problem Connecting spectral clustering to maximum margin and level set estimation.
method Obtained bounds on eigenvectors of graph Laplacian matrices in terms of cluster separation and connectivity. Showed sensitivity mitigation by removing outliers and estimating level sets.
result Spectral clustering converges to maximum margin clustering as scaling parameter approaches zero.
A new classifier updates sequentially using maximum margin principles.
problem Sequential data collection and partial labeling.
method Maximum margin classifier with Maximum Entropy Discrimination principle, kernel representation, and regularization.
result Improved performance compared to non-sequential classifiers.
The paper analyzes the maximum margin algorithm's performance on noisy data.
problem Analyzing the performance of maximum margin algorithm on noisy data.
method Finite-sample analysis of maximum margin algorithm applied to noisy data.
result The maximum margin algorithm can achieve nearly optimal population risk with sufficient over-parameterization.
Study shows how over-parameterized classifiers can still perform well on noisy data.
problem Understanding how maximum margin classifiers perform in over-parameterized settings with noisy data.
method Analyzes maximum margin classifiers on sub-Gaussian mixtures, providing risk bounds.
result Characterizes conditions for 'benign overfitting' in linear classification problems.
This work analyzes the maximum-margin bias in quasi-homogeneous neural networks.
problem Analyzing the maximum-margin bias in quasi-homogeneous neural networks.
method Geometric analysis of gradient dynamics for quasi-homogeneous models.
result Gradient flow implicitly favors a subset of parameters, leading to asymmetric norm minimization.
A new method improves maximum margin criterion for better pattern analysis.
problem Handling high dimensionality and large data in pattern analysis.
method Introducing an improved maximum margin criterion (MMC) and its variants.
result Experimental results show the MMC methods are effective in complex scenarios.
Gradient descent in logistic regression converges to the maximum margin predictor.
problem Convergence and risk of logistic regression parameters.
method Gradient descent applied to logistic regression.
result Gradient descent iterates converge to the maximum margin predictor at a rate of O(lnlnt/lnt). Gradient descent on logistic loss converges to the maximum-margin separator for separable data.
problem Understanding the convergence of gradient descent on separable datasets with specific loss functions.
method Analysis of gradient descent on linear models with super-polynomially tailed losses.
result For separable datasets, gradient descent converges to the maximum-margin separator for losses with super-polynomial tails, but not for heavier tails.
Mirror flow optimizes separable data problems, converging to a maximum margin classifier.
problem Optimizing classification problems with separable data using mirror flow.
method Examine mirror flow on linearly separable classification problems, focusing on the horizon function of the mirror potential.
result Mirror flow converges to a maximum margin classifier for separable data under certain conditions.
We consider the problem of learning Bayesian network classifiers that maximize the marginover a set of classification variables. We find that this problem is harder for Bayesian networks than for undirected graphical models like maximum margin Markov networks. The main difficulty is that the parameters in a Bayesian ne…
Deep neural networks can generalize well even with perfect fits to noisy data.
problem Understanding the conditions under which deep neural networks generalize well in the presence of noise.
method Comprehensive study of linear maximum margin classifiers, focusing on noisy and noiseless cases.
result Discovery of a phase transition in test error bounds for the noisy model.
A cutting-plane method learns data manifolds efficiently.
problem Classifying data manifolds with continuous parameters.
method Iterative algorithm M_{CP} based on cutting-plane approach solving a quadratic semi-infinite programming problem.
result M_{CP} provides superior generalization performance compared to conventional methods.
Combines RL and MML to learn programs from indirect supervision.
problem Learning programs from indirect supervision without spurious solutions.
method Connects RL and MML, uses systematic search and randomized exploration.
result Significant gains over state-of-the-art semantic parsers.
New algorithm improves latent variable model estimation.
problem Estimating parameters in latent variable models.
method Jarzynski-adjusted Langevin algorithm (JALA) for SMC methods.
result JALA-EM provides maximum marginal likelihood estimate.
The paper explores how benign overfitting occurs in heavy-tailed input distributions.
problem Understanding overfitting in heavy-tailed input distributions.
method Analysis of maximum margin classifiers on unregularized logistic loss with gradient descent.
result Linear classifiers trained under certain conditions can asymptotically achieve the noise level as misclassification error.
New method learns latent energy models using particle algorithms.
problem Learning latent variable models with energy priors.
method Continuous-time SDEs for MMLE, particle-based discretization.
result Practical algorithm converges to solve MMLE problem.
Solves indirect supervision problems with linear methods.
problem Structured prediction with indirect supervision.
method Solves linear system to estimate sufficient statistics, then uses convex optimization for parameter estimation.
result Effective in learning with privacy constraints and from count-based annotations.
New SMC samplers improve stochastic optimisation efficiency.
problem Optimizing functions with intractable gradients in machine learning and statistics.
method Sequential Monte Carlo (SMC) samplers for stochastic optimisation.
result Significant computational gains achieved with SMC approximations.
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.
Accelerates MMLE using SVGD with Nesterov acceleration.
problem Maximum Marginal Likelihood Estimation optimization.
method Stein variational gradient descent with Nesterov acceleration.
result Consistently accelerates convergence across various tasks.
Associating distinct groups of objects (clusters) with contiguous regions of high probability density (high-density clusters), is central to many statistical and machine learning approaches to the classification of unlabelled data. We propose a novel hyperplane classifier for clustering and semi-supervised classificati…
Study improves adversarial classification using distributionally robust models.
problem Improving robustness against adversarial attacks in classification models.
method Distributionally robust chance constraints with Wasserstein ambiguity, reformulated as a regularized ramp loss minimization problem.
result Standard descent methods can converge to the global minimizer for the distributionally robust adversarial classification model.
Develops a new algorithm for estimating model parameters using interacting particle systems.
problem Estimating parameters of latent variable models.
method Interacting Particle Langevin Algorithm (IPLA) based on Langevin diffusion.
result Nonasymptotic optimisation error bounds for the estimator.
This research improves neural network representation identifiability through task structures.
problem Improving neural network representation identifiability in multi-task settings.
method Analyzing the effects of task distributions and causal structures on latent factors, leading to simpler optimization.
result A straightforward optimization procedure enables better representation recovery in both synthetic and real-world data.
We give polynomial-time algorithms for the exact computation of lowest-energy (ground) states, worst margin violators, log partition functions, and marginal edge probabilities in certain binary undirected graphical models. Our approach provides an interesting alternative to the well-known graph cut paradigm in that it …
The support vector machine (SVM) is an important class of learning machines for function approach, pattern recognition, and time-serious prediction, etc. It maps samples into the feature space by so-called support vectors of selected samples, and then feature vectors are separated by maximum margin hyperplane. The pres…
Gradient descent aligns weights in deep linear networks for binary classification.
problem Aligning weights in deep linear networks for binary classification.
method Gradient descent applied to strictly decreasing loss functions.
result Normalized weight matrices align across layers, converging to the maximum margin solution.
Gaffke's bound is optimal for a specific parameter ordering in independent random vectors.
problem Finding optimal lower confidence bounds for a scalar parameter in independent random vectors.
method Revisiting classical work on lower confidence bounds, specializing to independent components, and proving optimality with respect to a specific parameter ordering.
result Gaffke's bound is Buehler optimal for the maximum marginal mean parameter.
A new framework for training structured prediction models using smoothing.
problem Training smooth structured prediction models with non-smooth objectives.
method Smoothing over the maximum margin structured prediction objective to enable fast optimization.
result The proposed framework enables the use of efficient optimization algorithms for structured prediction.
We define a generalized likelihood function based on uncertainty measures and show that maximizing such a likelihood function for different measures induces different types of classifiers. In the probabilistic framework, we obtain classifiers that optimize the cross-entropy function. In the possibilistic framework, we …
Multithreshold Entropy Linear Classifier (MELC) is a recent classifier idea which employs information theoretic concept in order to create a multithreshold maximum margin model. In this paper we analyze its consistency over multithreshold linear models and show that its objective function upper bounds the amount of mis…
Ultrahigh-dimensional variable selection plays an increasingly important role in contemporary scientific discoveries and statistical research. Among others, Fan and Lv [J. R. Stat. Soc. Ser. B Stat. Methodol. 70 (2008) 849-911] propose an independent screening framework by ranking the marginal correlations. They showed…
In this paper, we present a novel and general framework called {\it Maximum Entropy Discrimination Markov Networks} (MaxEnDNet), which integrates the max-margin structured learning and Bayesian-style estimation and combines and extends their merits. Major innovations of this model include: 1) It generalizes the extant …
Proposes a new stochastic graphlet embedding method for graph-based machine learning.
problem Graph-based data lacks direct compatibility with machine learning algorithms.
method Introduces high-order stochastic graphlet embedding (SGE) to map graphs into vector spaces.
result SGE efficiently parses graphs to extract high-order graphlets and measures their distribution.
This manuscript shows that AdaBoost and its immediate variants can produce approximate maximum margin classifiers simply by scaling step size choices with a fixed small constant. In this way, when the unscaled step size is an optimal choice, these results provide guarantees for Friedman's empirically successful "shrink…
This paper extends performative prediction to nonlinear cases.
problem Performative prediction's effectiveness is limited by linear assumptions in real-world applications.
method Formulated a maximum margin approach loss function and extended it to nonlinear spaces using kernel methods.
result Derived conditions for performative stability in both linear and nonlinear cases.
In binary classification problems, mainly two approaches have been proposed; one is loss function approach and the other is uncertainty set approach. The loss function approach is applied to major learning algorithms such as support vector machine (SVM) and boosting methods. The loss function represents the penalty of …
Adam optimizes linear classifiers with separable data.
problem Understanding Adam's implicit bias in linear logistic regression.
method Study of Adam's behavior on linearly separable data.
result Adam converges to a linear classifier with maximum ℓ∞-margin. The matrix-completion problem has attracted a lot of attention, largely as a result of the celebrated Netflix competition. Two popular approaches for solving the problem are nuclear-norm-regularized matrix approximation (Candes and Tao, 2009, Mazumder, Hastie and Tibshirani, 2010), and maximum-margin matrix factorizati…
Develops novel techniques for collaborative filtering and multi-label classification.
problem Information overload and categorization of data objects.
method Hierarchical bi-level maximum margin matrix factorization and piecewise-linear embedding method.
result Effective multi-label classification and collaborative filtering techniques developed.
We introduce a conceptually novel structured prediction model, GPstruct, which is kernelized, non-parametric and Bayesian, by design. We motivate the model with respect to existing approaches, among others, conditional random fields (CRFs), maximum margin Markov networks (M3N), and structured support vector machines (S…
New insights into Gamma-Poisson model for count data.
problem Estimating topic/dictionary matrix robustness to rank over-specification.
method Rewriting GaP model free of score/activation matrix, leading to new MME algorithm.
result Automatic pruning of irrelevant dictionary columns observed empirically.
Recently, there has been much interest in finding globally optimal Bayesian network structures. These techniques were developed for generative scores and can not be directly extended to discriminative scores, as desired for classification. In this paper, we propose an exact method for finding network structures maximiz…
Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, categorical, ordinal, and other data types. This framework encompasses many well known techniques in da…
The paper proposes a tree model for interval-valued regression.
problem Learning a real-valued function from interval-valued data.
method Minimizing a margin-based discriminative objective function using a tree structure and dynamic programming.
result The proposed algorithm achieves state-of-the-art speed and accuracy.
We introduce a useful tool for analyzing boosting algorithms called the ``smooth margin function,'' a differentiable approximation of the usual margin for boosting algorithms. We present two boosting algorithms based on this smooth margin, ``coordinate ascent boosting'' and ``approximate coordinate ascent boosting,'' w…
Develops particle-based optimisation for intractable gradient problems.
problem Optimisation of loss functions with intractable gradients.
method Mean-field dynamics and interacting-particle approximations.
result Exponential convergence and non-asymptotic error bound proved.
Supervised topic models utilize document's side information for discovering predictive low dimensional representations of documents. Existing models apply the likelihood-based estimation. In this paper, we present a general framework of max-margin supervised topic models for both continuous and categorical response var…