Tighter Bounds for Structured Estimation
Large-margin structured estimation methods work by minimizing a convex upper bound of loss functions. While they allow for efficient optimization algorithms, these convex formulations are not tight and sacrifice the ability to accurately model the true loss. We present tighter non-convex bounds based on generalizing the notion of a ramp loss from binary classification to structured estimation. We show that a small modification of existing optimization algorithms suffices to solve this modified problem. On structured prediction tasks such as protein sequence alignment and web page ranking, our algorithm leads to improved accuracy.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationGeneral ClassificationStructured PredictionSimilar Papers 제목 키워드 기반
A strong converse bound for multiple hypothesis testing, with applications to high-dimensional estimation
In statistical inference problems, we wish to obtain lower bounds on the minimax risk, that is to bound the performance of any possible estimator. A standard technique to obtain risk lower bounds involves the use of Fano…
Active Learningcompressed sensingDensity EstimationTwo-sample testingThe Structured Weighted Violations Perceptron Algorithm
We present the Structured Weighted Violations Perceptron (SWVP) algorithm, a new structured prediction algorithm that generalizes the Collins Structured Perceptron (CSP). Unlike CSP, the update rule of SWVP explicitly ex…
Dependency ParsingGeneralization BoundsStructured PredictionPrior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits
We study the problem of Bayesian fixed-budget best-arm identification (BAI) in structured bandits. We propose an algorithm that uses fixed allocations based on the prior information and the structure of the environment. …
Tight lower bounds for Dynamic Time Warping
Dynamic Time Warping (DTW) is a popular similarity measure for aligning and comparing time series. Due to DTW's high computation time, lower bounds are often employed to screen poor matches. Many alternative lower bounds…
Computational EfficiencyDynamic Time WarpingTime SeriesTime Series AnalysisOn the Upper Bounds for the Matrix Spectral Norm
We consider the problem of estimating the spectral norm of a matrix using only matrix-vector products. We propose a new Counterbalance estimator that provides upper bounds on the norm and derive probabilistic guarantees …