Related papers: Randomized multi-class classification under system constraints: a unified approach via post-processing

Randomized multi-class classification under system constraints: a unified approach via post-processing

URL: http://arxiv.org/abs/2512.14246v1
Date: Tue, 16 Dec 2025 09:53:22 GMT
Title: Randomized multi-class classification under system constraints: a unified approach via post-processing
Authors: Evgenii Chzhen, Mohamed Hebiri, Gayane Taturyan,
Abstract summary: We study the problem of multi-class classification under system-level constraints expressible as linear functionals over randomized classifiers.<n>We propose a post-processing approach that adjusts a given base classifier to satisfy general constraints without retraining.
Score: 8.354034992258482
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of multi-class classification under system-level constraints expressible as linear functionals over randomized classifiers. We propose a post-processing approach that adjusts a given base classifier to satisfy general constraints without retraining. Our method formulates the problem as a linearly constrained stochastic program over randomized classifiers, and leverages entropic regularization and dual optimization techniques to construct a feasible solution. We provide finite-sample guarantees for the risk and constraint satisfaction for the final output of our algorithm under minimal assumptions. The framework accommodates a broad class of constraints, including fairness, abstention, and churn requirements.

Related papers

Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
arXiv Detail & Related papers (2025-11-27T06:16:17Z)
Online Multi-Class Selection with Group Fairness Guarantee [3.8723467409682617]
We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents.<n>We introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution.<n>We also propose a learning-augmented variant that incorporates untrusted machine-learned predictions to better balance fairness and efficiency.
arXiv Detail & Related papers (2025-10-23T23:59:49Z)
Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees [34.164821598251315]
In sparse optimization, enforcing hard constraints using the $ell_$ pseudo-norm offers advantages like controlled sparsity.<n>Many real-world applications demand not only sparsity constraints but also some extra constraints.<n>We present a new variant of hard-preserving iterative algorithm equipped with a two-step projection operator customized for these mixed constraints.
arXiv Detail & Related papers (2025-06-10T08:27:01Z)
Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
arXiv Detail & Related papers (2025-04-21T17:15:48Z)
Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
Deep unrolling is an emerging learning-to-optimize method that unrolls a truncated iterative algorithm in the layers of a trainable neural network.<n>We show that convergence guarantees and generalizability of the unrolled networks are still open theoretical problems.<n>We numerically assess unrolled architectures trained under the proposed constraints in two different applications.
arXiv Detail & Related papers (2023-12-25T18:51:23Z)
Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
arXiv Detail & Related papers (2023-11-08T00:10:21Z)
Self-adaptive algorithms for quasiconvex programming and applications to machine learning [0.0]
We provide a self-adaptive step-size strategy that does not include convex line-search techniques and a generic approach under mild assumptions. The proposed method is verified by preliminary results from some computational examples. To demonstrate the effectiveness of the proposed technique for large-scale problems, we apply it to some experiments on machine learning.
arXiv Detail & Related papers (2022-12-13T05:30:29Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
arXiv Detail & Related papers (2020-07-07T21:26:35Z)
An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
arXiv Detail & Related papers (2020-06-18T20:09:53Z)
Submodular Bandit Problem Under Multiple Constraints [8.100450025624443]
We introduce a submodular bandit problem under the intersection of $l$ knapsacks and a $k$-system constraint. To solve this problem, we propose a non-greedy algorithm that adaptively focuses on a standard or modified upper-confidence bound. We provide a high-probability upper bound of an approximation regret, where the approximation ratio matches that of a fast algorithm.
arXiv Detail & Related papers (2020-06-01T01:28:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.