Cover Image

An efficient, provably optimal algorithm for the 0-1 loss linear classification problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	He, Xi, Little, Max A.
Format:	Preprint
Published:	2023
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules
by: He, Xi, et al.
Published: (2025)

Unrolled denoising networks provably learn optimal Bayesian inference
by: Karan, Aayush, et al.
Published: (2024)

Dynamic programming by polymorphic semiring algebraic shortcut fusion
by: Little, Max A., et al.
Published: (2021)

Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
by: He, Xi
Published: (2025)

The graph alignment problem: fundamental limits and efficient algorithms
by: Ganassali, Luca
Published: (2024)

Functional design of efficient and parallelizable combinatorial generators using convolution
by: He, Xi, et al.
Published: (2025)

MNL-Bandit with Knapsacks: a near-optimal algorithm
by: Aznag, Abdellah, et al.
Published: (2021)

Phase transition of the Sinkhorn-Knopp algorithm
by: He, Kun
Published: (2025)

Dynamic algorithms for k-center on graphs
by: Cruciani, Emilio, et al.
Published: (2023)

On efficient robust regression with subquadratic samples
by: Adil, Deeksha, et al.
Published: (2026)

Subset verification and search algorithms for causal DAGs
by: Choo, Davin, et al.
Published: (2023)

Competitive strategies to use "warm start" algorithms with predictions
by: Srinivas, Vaidehi, et al.
Published: (2024)

Improved sampling algorithms and functional inequalities for non-log-concave distributions
by: He, Yuchen, et al.
Published: (2025)

Learning general Gaussian mixtures with efficient score matching
by: Chen, Sitan, et al.
Published: (2024)

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)

Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
by: Gayen, Sutanu, et al.
Published: (2024)

Optimal hypersurface decision trees
by: He, Xi
Published: (2025)

Sample-efficient Multiclass Calibration under $\ell_{p}$ Error
by: Bairaktari, Konstantina, et al.
Published: (2025)

OPTWIN: Drift identification with optimal sub-windows
by: Tosi, Mauro Dalle Lucca, et al.
Published: (2023)

Accelerating ERM for data-driven algorithm design using output-sensitive techniques
by: Balcan, Maria-Florina, et al.
Published: (2022)

Near-optimal Swap Regret Minimization for Convex Losses
by: Hu, Lunjia, et al.
Published: (2026)

Near-optimal Active Regression of Single-Index Models
by: Li, Yi, et al.
Published: (2025)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

Efficient distributional regression trees learning algorithms for calibrated non-parametric probabilistic forecasts
by: Duchemin, Quentin, et al.
Published: (2025)

Agnostic learning in (almost) optimal time via Gaussian surface area
by: Pesenti, Lucas, et al.
Published: (2026)

Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
by: Lee, Russell, et al.
Published: (2022)

Polynomial-time derivation of optimal k-tree topology from Markov networks
by: Dastjerdi, Fereshteh R., et al.
Published: (2024)

Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
by: Sharman, Bharat, et al.
Published: (2025)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
by: Amanatidis, Georgios, et al.
Published: (2021)

Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling
by: Qin, Hao, et al.
Published: (2025)

Learning $\mathsf{AC}^0$ Under Graphical Models
by: Chandrasekaran, Gautam, et al.
Published: (2026)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
by: Assadi, Sepehr, et al.
Published: (2023)

On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport
by: He, Kun
Published: (2026)

Combinatorial optimization of the coefficient of determination
by: Harary, Marc
Published: (2024)

Dynamic Spectral Clustering with Provable Approximation Guarantee
by: Laenen, Steinar, et al.
Published: (2024)

On the query complexity of sampling from non-log-concave distributions
by: He, Yuchen, et al.
Published: (2025)

Dynamic Similarity Graph Construction with Kernel Density Estimation
by: Laenen, Steinar, et al.
Published: (2025)

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
by: He, Yuchen, et al.
Published: (2024)

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
by: He, Kaiwen, et al.
Published: (2025)