Cover Image

The Space Complexity of Approximating Logistic Loss

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dexter, Gregory, Drineas, Petros, Khanna, Rajiv
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Stochastic Rounding 2.0, with a View towards Complexity Analysis
by: Drineas, Petros, et al.
Published: (2024)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
by: Chowdhury, Agniva, et al.
Published: (2024)

Language Generation in the Limit: Noise, Loss, and Feedback
by: Bai, Yannan, et al.
Published: (2025)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

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

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

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

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

Reweighted Solutions for Weighted Low Rank Approximation
by: Woodruff, David P., et al.
Published: (2024)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

Incremental Approximate Single-Source Shortest Paths with Predictions
by: McCauley, Samuel, et al.
Published: (2025)

Optimal Approximate Matrix Multiplication over Sliding Windows
by: Yao, Ziqi, et al.
Published: (2025)

A Simple Approximation Algorithm for Optimal Decision Tree
by: Zhuo, Zhengjia, et al.
Published: (2025)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions
by: Epasto, Alessandro, et al.
Published: (2020)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

Approximating splits for decision trees quickly in sparse data streams
by: Tatti, Nikolaj
Published: (2026)

A Faster Generalized Two-Stage Approximate Top-K
by: Samaga, Yashas, et al.
Published: (2025)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
by: Blum, Avrim, et al.
Published: (2024)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
by: Maity, Binita, et al.
Published: (2024)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases
by: Wolfson, Daniel, et al.
Published: (2026)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
by: Garg, Sachin, et al.
Published: (2025)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
by: Yang, Yichun, et al.
Published: (2024)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

Space of Data through the Lens of Multilevel Graph
by: Caputo, Marco, et al.
Published: (2025)

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
by: Joshi, Nirmit, et al.
Published: (2024)

Faster and Space Efficient Indexing for Locality Sensitive Hashing
by: Verma, Bhisham Dev, et al.
Published: (2025)

Coreset Spectral Clustering
by: Jourdan, Ben, et al.
Published: (2025)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
by: Kannan, Ravindran, et al.
Published: (2024)

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2022)