Optimizes binary regression models with gradient ascent-descent methods.
problem Regression problems with binary weights in quantized learning and digital communication.
method Maximin optimization using gradient ascent-descent methods.
result The approach is optimal in linear regression with low noise and robust regression with few outliers.
In statistical learning theory, convex surrogates of the 0-1 loss are highly preferred because of the computational and theoretical virtues that convexity brings in. This is of more importance if we consider smooth surrogates as witnessed by the fact that the smoothness is further beneficial both computationally- by at…
New binary AA methods improve on existing techniques.
problem Binary data limitations in AA methods.
method Proposed two optimization frameworks for binary AA.
result Superior performance on synthetic and real binary data.
Novel BSG method for efficient stochastic optimization.
problem Efficient optimization of non-convex surfaces in stochastic settings.
method Binary search combined with first order gradient optimization.
result BSG produces more promising results and better generalization than other methods.
Sharp bounds on binary model inference performance.
problem High-dimensional inference in binary models.
method Convex empirical risk minimization, sharp asymptotics, optimal performance bounds.
result Sharp predictions and optimal performance bounds for binary models.
Binary perceptron's instability linked to replica symmetry breaking.
problem Understanding the relationship between algorithmic instability and replica symmetry breaking in binary perceptron learning.
method Established the connection between algorithmic instability and replica symmetry breaking by comparing the instability condition around the fixed point to the instability for breaking the replica symmetric solution of the free energy function.
result The instability condition around the algorithmic fixed point is identical to the instability for breaking the replica symmetric saddle point solution of the free energy function.
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…
A new framework for sparse regression models with slow variations.
problem Parameter estimation for sparse regression models with slow variations.
method Formulated as a mixed-integer optimization problem, then reformulated as a binary convex optimization problem with a novel relaxation technique.
result Efficiently solves the problem to provable optimality using a cutting plane-type algorithm.
We formulate learning of a binary autoencoder as a biconvex optimization problem which learns from the pairwise correlations between encoded and decoded bits. Among all possible algorithms that use this information, ours finds the autoencoder that reconstructs its inputs with worst-case optimal loss. The optimal decode…
New method turns optimization algorithms into uniformly stable learning algorithms for non-Euclidean norms.
problem Non-Euclidean norms in binary classification problems.
method Black-box reduction method using uniformly convex regularizers.
result Achieves optimal statistical risk bounds on excess risk for non-Euclidean norms.
Novel approximation hierarchy for sparse quadratic programs.
problem Sparse Quadratic Programs with Cardinality Constraints.
method Exploits rank-dominating eigenvectors for min-max optimization over binary variables.
result Efficient screening of nonzero elements with scalable optimization algorithms.
A new convex loss function optimizes set predictions with balanced size and coverage.
problem Optimizing set predictions with balanced size and coverage.
method Proposes a convex loss function using Choquet integrals for nondecreasing subset-valued functions.
result Optimal trade-offs between conditional probabilistic coverage and set size.
There has been much recent interest in application of the pool-adjacent-violators (PAV) algorithm for the purpose of calibrating the probabilistic outputs of automatic pattern recognition and machine learning algorithms. Special cost functions, known as proper scoring rules form natural objective functions to judge the…
Paper introduces fair GLMs with convex penalty for equalizing GLM outcomes.
problem Achieving fairness in GLMs for practical use.
method Two fairness criteria based on GLM outcomes/log-likelihoods, achieved via a convex penalty on linear components.
result The fair GLM estimator is efficient and can handle various response variables.
Paper develops compact formulations for optimization problems with rank-one convex functions and indicator variables.
problem Optimization problems involving rank-one convex functions with support constraints.
method Perspective reformulation techniques to exploit conic structure and establish convex hull results.
result Systematic perspective formulations for convex hull descriptions of sets with nonlinear separable or non-separable objective functions and combinatorial constraints.
This paper develops convex surrogates for optimizing the multi-label F-measure.
problem Optimizing the F-measure for multi-label classification is computationally hard.
method Designing convex surrogate losses calibrated for the F-measure.
result The F-measure for multi-label problems has a rank of at most s2+1. New optimization method improves AUC for binary classification and changepoint detection.
problem Non-convex AUC and sub-optimal points in ROC curves.
method AUM (Area Under Min(FP, FN)) surrogate loss function based on sorting and summing ROC curve points.
result AUM minimization learning algorithm improves AUC and speeds up compared to previous methods.
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 O(n−1) for different function classes. 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…
This work examines uncertainty sampling in binary classification using equivalent loss.
problem Lack of consensus on proper uncertainty definition and theoretical guarantees for active learning.
method Systematically examines uncertainty sampling via equivalent loss, proving its optimality.
result Established that uncertainty sampling optimizes against equivalent loss, providing theoretical guarantees.
The paper explores how to select data points for optimal learning performance.
problem Optimizing data selection for empirical risk minimizers.
method Fixing a learning rule and focusing on optimizing the training data selection.
result Achieving performance comparable to training on the entire population with a small subset of data points.
Unhinged loss minimization fails to improve classifier accuracy for simple data.
problem Accuracy of classifiers minimizing the unhinged loss.
method Minimizing the unhinged loss function.
result Minimizing the unhinged loss yields classifiers with accuracy no better than random guessing for simple data.
New approach to convex hulls for low-rank problems.
problem Characterizing convex hulls for low-rank sets.
method Matrix perspective function and orthogonal projection matrices.
result Strong relaxations for various low-rank problems.
Study improves learning algorithms for convex polyhedra in Hilbert spaces.
problem Learning convex polyhedra in Hilbert spaces.
method Proposes an algorithm for learning a polyhedron in a Hilbert space.
result Correctly classifies at least 1-ε of the distribution with high probability.
Proposes a framework for balancing fairness and accuracy in data-restricted binary classification.
problem Balancing fairness and accuracy in applications with data restrictions.
method Directly analyzes the optimal Bayesian classifier's behavior under different data-restricting scenarios, formulating convex optimization problems.
result Demonstrates how accuracy of a Bayesian classifier is affected by fairness constraints in various data-restricting scenarios.
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
Convolutional neural network (CNN)-based feature learning has become state of the art, since given sufficient training data, CNN can significantly outperform traditional methods for various classification tasks. However, feature learning becomes more difficult if some training labels are noisy. With traditional regular…
New method approximates neural network training for robustness.
problem Training robust neural networks with adversarial input perturbations.
method Stochastic convex optimization approach to adversarial training.
result Method achieves better adversarial robustness and performance.
The paper addresses learner privacy in convex optimization with feedback.
problem Privacy risks from eavesdropping adversaries observing learner's queries.
method Optimally obfuscating learner's queries to make their learned optimal value hard to estimate.
result Query complexity overhead is additive in L in the minimax formulation, multiplicative in L in the Bayesian formulation. Multivariate binary data is becoming abundant in current biological research. Logistic principal component analysis (PCA) is one of the commonly used tools to explore the relationships inside a multivariate binary data set by exploiting the underlying low rank structure. We re-expressed the logistic PCA model based on …
Improved Frank-Wolfe method reduces dependence on data size for empirical risk minimization.
problem Reducing dependence on number of data observations in Frank-Wolfe methods.
method Taylor-series approximated gradients applied to Frank-Wolfe method.
result Significant speed-ups over existing methods on real-world datasets.
Let $\cF$ be a set of M classification procedures with values in [−1,1]. Given a loss function, we want to construct a procedure which mimics at the best possible rate the best procedure in $\cF$. This fastest rate is called optimal rate of aggregation. Considering a continuous scale of loss functions with various …
A scalable gradient-based framework for sparse portfolio selection.
problem Sparse minimum-variance portfolio selection with cardinality constraint.
method Gradient-based optimization with Boolean relaxation and tunable parameter.
result Matches commercial solvers in most instances, differing by a few assets with negligible error in portfolio variance.
We introduce a minorization-maximization approach to optimizing common measures of discovery significance in high energy physics. The approach alternates between solving a weighted binary classification problem and updating class weights in a simple, closed-form manner. Moreover, an argument based on convex duality sho…
A wide variety of machine learning algorithms such as support vector machine (SVM), minimax probability machine (MPM), and Fisher discriminant analysis (FDA), exist for binary classification. The purpose of this paper is to provide a unified classification model that includes the above models through a robust optimizat…
SIGTRON improves classification accuracy for imbalanced datasets.
problem Improving classification accuracy for imbalanced datasets.
method SIGTRON is a new sigmoid function with a convex loss function for imbalanced classification.
result SIGTRON models outperform existing methods in balanced and imbalanced datasets.
The optimal binning is the optimal discretization of a variable into bins given a discrete or continuous numeric target. We present a rigorous and extensible mathematical programming formulation for solving the optimal binning problem for a binary, continuous and multi-class target type, incorporating constraints not p…
Develops a new method for statistical optimal allocation problems.
problem Statistical optimal allocation problems with constraints.
method Functional differentiability approach and Hadamard differentiability of value functions.
result Validates margin assumption for fast convergence rate of plug-in methods.
Study on double descent behavior in two-layer neural networks for binary classification.
problem Understanding the double descent phenomenon in model test error.
method Two-layer neural network with ReLU activation for binary classification. Quantified model size by sample-to-dimension ratio. Empirical risk minimization using Convex Gaussian Min Max Theorem.
result Observed and investigated the double descent behavior of model test error.
Many practical problems involve the recovery of a binary matrix from partial information, which makes the binary matrix completion (BMC) technique received increasing attention in machine learning. In particular, we consider a special case of BMC problem, in which only a subset of positive elements can be observed. In …
New method solves subspace optimization problems efficiently.
problem Finding a k-dimensional subspace in high dimensions.
method Local linear convergence of gradient methods under strict complementarity.
result Gradient method converges linearly in high dimensions.
Defines diversification as a binary relationship between financial portfolios.
problem Defines diversification in a new binary relationship for financial portfolios.
method Proposes a new definition of diversification based on convex linear combinations and second order stochastic dominance.
result The proposed definition coincides with second order stochastic dominance.
Motivated by problems of anomaly detection, this paper implements the Neyman-Pearson paradigm to deal with asymmetric errors in binary classification with a convex loss. Given a finite collection of classifiers, we combine them and obtain a new classifier that satisfies simultaneously the two following properties with …
An attractive approach for fast search in image databases is binary hashing, where each high-dimensional, real-valued image is mapped onto a low-dimensional, binary vector and the search is done in this binary space. Finding the optimal hash function is difficult because it involves binary constraints, and most approac…
Zeroth-order methods favor flat minima in machine learning.
problem Finding solutions with small Hessian trace in optimization.
method Zeroth-order optimization with two-point estimator.
result Zeroth-order optimization converges to flat minima.
Robust SVM optimization in Banach spaces tackles classification uncertainty.
problem Binary classification in Banach spaces with uncertainty.
method Generalization of SVM results to Banach spaces, Representer Theorem, strong duality, Nash equilibrium formulation.
result Generalization of SVM results to Banach spaces, including Representer Theorem and strong duality.
Paper tackles 1-bit compressed sensing, presenting efficient algorithm for sparse signal estimation.
problem Estimating sparse signals from binary measurements.
method Non-convex sparsity-constrained program with one-shot hard thresholding.
result Simple algorithm produces accurate signal approximation with high probability.
Proposes a fair classification model using Wasserstein ambiguity sets.
problem Ensuring fairness in classification models.
method Distributionally robust optimization with Wasserstein ambiguity sets and equal opportunity fairness constraint.
result Improves fairness without significant loss in predictive accuracy.