Generalization Bounds for Learning with Linear, Polygonal, Quadratic and Conic Side Knowledge
In this paper, we consider a supervised learning setting where side knowledge is provided about the labels of unlabeled examples. The side knowledge has the effect of reducing the hypothesis space, leading to tighter generalization bounds, and thus possibly better generalization. We consider several types of side knowledge, the first leading to linear and polygonal constraints on the hypothesis space, the second leading to quadratic constraints, and the last leading to conic constraints. We show how different types of domain knowledge can lead directly to these kinds of side knowledge. We prove bounds on complexity measures of the hypothesis space for quadratic and conic side knowledge, and show that these bounds are tight in a specific sense for the quadratic case.
Code (1)
Tasks
Generalization BoundsSimilar Papers 제목 키워드 기반
Supermodularity and valid inequalities for quadratic optimization with indicators
We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in g…
validDual Lagrangian Learning for Conic Optimization
This paper presents Dual Lagrangian Learning (DLL), a principled learning methodology for dual conic optimization proxies. DLL leverages conic duality and the representation power of ML models to provide high-duality, du…
Self-Supervised LearningvalidGeometric primitive feature extraction - concepts, algorithms, and applications
This thesis presents important insights and concepts related to the topic of the extraction of geometric primitives from the edge contours of digital images. Three specific problems related to this topic have been studie…
Outlier detection in regression: conic quadratic formulations
In many applications, when building linear regression models, it is important to account for the presence of outliers, i.e., corrupted input data points. Such problems can be formulated as mixed-integer optimization prob…
Outlier DetectionregressionLinear-Quadratic Problems in Systems and Controls via Covariance Representations and Linear-Conic Duality: Finite-Horizon Case
Linear-Quadratic (LQ) problems that arise in systems and controls include the classical optimal control problems of the Linear Quadratic Regulator (LQR) in both its deterministic and stochastic forms, as well as $H^\inft…
LEMMA