Optimization

Graph Neural Networks (GNNs) learn optimal approximation algorithms for combinatorial optimization problems, achieving high-quality solutions for Max-Cut, Min-Vertex-Cover, and Max-3-SAT, while also p…

Approximation-Aware Bayesian Optimization (AABO) boosts high-dimensional Bayesian optimization by jointly optimizing model approximation and data acquisition, achieving superior efficiency and perform…

Random-order stream data necessitates efficient top eigenvector approximation; this paper presents novel algorithms with improved space complexity, achieving near-optimal bounds.

Improved Empirical Fisher (iEF) approximation significantly boosts the performance of Natural Gradient Descent (NGD) optimizers, offering superior convergence and generalization.

Dynamic regret minimization equals static regret in an extended space; this equivalence reveals a trade-off between loss variance and comparator variability, leading to a new algorithm achieving impro…

New unbiased gradient estimator for high-dimensional SDEs drastically reduces computation time without sacrificing estimation accuracy.

Elo rating system’s convergence rigorously analyzed via Markov chains under the Bradley-Terry-Luce model, demonstrating competitive learning rates and informing efficient tournament design.

Accelerated Gradient Method for Bilevel Optimization (AGM-BiO) achieves state-of-the-art convergence rates for simple bilevel optimization problems, requiring fewer iterations than existing methods to…

Accelerate neural network training using ‘amortized eigendecomposition’ – a novel method replacing expensive eigendecomposition with faster QR decomposition while preserving accuracy.

Generalized linear bandits with subexponential reward distributions are self-concordant, enabling second-order regret bounds free of exponential dependence on problem parameters.

This paper introduces Quantitative Relative Judgment Aggregation (QRJA), a novel social choice model, and applies it to ranking prediction, yielding effective and interpretable results on various real…

Researchers refine Pearson’s correlation coefficient to precisely measure arbitrary monotone dependence, expanding its applicability beyond linear relationships.

This paper introduces efficient algorithms for online selection with a budget constraint when comparing candidates from different groups has a cost, improving fairness and efficiency.

Adaptive STORM achieves optimal convergence rates for stochastic optimization of non-convex functions under weaker assumptions, eliminating the need for bounded gradients or function values and removi…

AdaptiveSoftmax: Achieve 10x+ speedup in softmax computation via adaptive sampling!

Adaptive gradient descent methods are improved by leveraging local curvature information for entirely adaptive algorithms without added computational cost, proving convergence with only local Lipschit…

New adaptive second-order optimistic methods for minimax optimization achieve optimal convergence without line search, simplifying updates and improving efficiency.

Clipped Adam with EMA achieves optimal convergence rates for smooth and non-smooth nonconvex optimization, particularly when scales vary across different coordinates.

A novel parameter-free decentralized optimization algorithm achieves linear convergence for strongly convex, smooth objectives, eliminating the need for hyperparameter tuning and improving scalability…

Accelerated gradient-free optimization is achieved using only function value comparisons, significantly improving black-box optimization.