Optimization

A unified neural divide-and-conquer framework (UDC) achieves superior performance on large-scale combinatorial optimization problems by employing a novel Divide-Conquer-Reunion training method and a h…

Researchers developed Subsampled Smooth Calibration Error (SSCE), a new truthful calibration measure for sequential prediction, solving the problem of existing measures being easily gamed.

Supervised learning’s sample complexity is compact: a hypothesis class is learnable if and only if all its finite projections are learnable, simplifying complexity analysis.

Researchers achieve a balance between accuracy and efficiency in multiclass classification by introducing partially consistent surrogate losses and novel methods.

This paper examines the trade-offs between two popular diagonal Fisher Information Matrix (FIM) estimators in neural networks, deriving variance bounds and highlighting the importance of considering e…

Trace: Automating AI workflow design with LLMs.

Gradient EM for over-parameterized Gaussian Mixture Models globally converges with a sublinear rate, solving a longstanding open problem in machine learning.

Shallow ReLU neural networks face topological training obstructions due to gradient flow confinement on disconnected quadric hypersurfaces.

Shuffled SGD’s convergence is now better understood through a primal-dual analysis, yielding tighter bounds that align with its superior empirical performance.

This paper presents an algorithm achieving Õ(√T) optimal regret for bandit non-stochastic control with strongly-convex and smooth cost functions, overcoming prior limitations of suboptimal bounds.

Learning user preferences accurately from limited data is key; this paper shows that surprisingly small datasets suffice for precise prediction, and provides efficient algorithms to achieve this.

W-DBO efficiently tackles stale data in dynamic Bayesian Optimization by leveraging a novel Wasserstein distance-based criterion to remove irrelevant observations, maintaining high sampling frequency …

New theoretical bounds reveal how neural network architecture impacts the Gauss-Newton matrix’s conditioning, paving the way for improved optimization.

Partial preferences and noisy votes hinder accurate ranking recovery; this paper introduces scalable SP voting variants, empirically demonstrating superior performance in recovering ground truth ranki…

This paper proves fundamental space complexity lower bounds for approximating logistic loss, revealing that existing coreset constructions are surprisingly optimal.

Beat the 1/e barrier in the secretary problem using only an additive gap prediction!

Gradient descent’s sample complexity in non-smooth stochastic convex optimization is Õ(d/m+1/√m), matching worst-case ERMs and showing no advantage over naive methods.

Revolutionizing machine learning, Schedule-Free optimization achieves state-of-the-art results without needing learning rate schedules, simplifying training and improving efficiency.

OKRidge’s reliability for solving sparse ridge regression problems is rigorously proven through theoretical error analysis, enhancing its applicability in machine learning.

Researchers found the minimax optimal rate of HSIC estimation for translation-invariant kernels is O(n⁻¹/²), settling a two-decade-old open question and validating many existing HSIC estimators.