Statistical Inference in Tensor Completion: Optimal Uncertainty Quantification and Statistical-to-Computational Gaps

Dong Xia, Wanteng Ma

Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity

Jie Peng, Qing Ling, Qiankun Shi et al.

In this paper, we establish tight lower bounds for Byzantine-robust distributed first-order stochastic methods in both strongly convex and non-convex ...

Fast Computation of Superquantile-Constrained Optimization Through Implicit Scenario Reduction

Ying Cui, Jake Roth

Superquantiles have recently gained significant interest as a risk-aware metric for addressing fairness and distribution shifts in statistical learnin...

VFOSA: Variance-Reduced Fast Operator Splitting Algorithms for Generalized Equations

Quoc Tran-Dinh

We develop two Variance-reduced Fast Operator Splitting Algorithms (VFOSA) to approximate solutions for a class of generalized equations, covering fun...

An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models

Tong Xu, Armeen Taeb, Simge Küçükyavuz et al.

This paper studies the problem of learning Bayesian networks from continuous observational data, generated according to a linear Gaussian structural e...

Decentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity

Xinmeng Huang, Kun Yuan, Boao Kong et al.

Stochastic bilevel optimization (SBO) is becoming increasingly essential in machine learning due to its versatility in handling nested structures. To ...

Stochastic Interior-Point Methods for Smooth Conic Optimization with Applications

Chuan He, Zhanwang Deng

Conic optimization plays a crucial role in many machine learning (ML) problems. However, practical algorithms for conic constrained ML problems with l...

Graph-accelerated Markov Chain Monte Carlo using Approximate Samples

Leo L. Duan, Anirban Bhattacharya

It has become increasingly easy nowadays to collect approximate posterior samples via fast algorithms such as variational Bayes, but concerns exist ab...

Algorithms for ridge estimation with convergence guarantees

Wanli Qiao, Wolfgang Polonik

The extraction of filamentary structure from a point cloud is discussed. The filaments are modeled as ridge lines or higher dimensional ridges of an u...

Lexicographic Lipschitz Bandits: New Algorithms and a Lower Bound

Lijun Zhang, Bo Xue, Ji Cheng et al.

This paper studies a multiobjective bandit problem under lexicographic ordering, wherein the learner aims to maximize $m$ objectives, each with differ...

Decentralized Asynchronous Optimization with DADAO allows Decoupling and Acceleration

Adel Nabli, Edouard Oyallon

DADAO is the first decentralized, accelerated, asynchronous, primal, first-order algorithm to minimize a sum of $L$-smooth and $\mu$-strongly convex ...

BoFire: Bayesian Optimization Framework Intended for Real Experiments

Johannes P. Dürholt, Thomas S. Asche, Johanna Kleinekorte et al.

Our open-source Python package BoFire combines Bayesian Optimization (BO) with other design of experiments (DoE) strategies focusing on developing and...

An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition

Qihang Lin, Negar Soheili, Runchao Ma et al.

Recent efforts to accelerate first-order methods have focused on convex optimization problems that satisfy a geometric property known as error-bound c...

Relaxed Gaussian Process Interpolation: a Goal-Oriented Approach to Bayesian Optimization

Sébastien J. Petit, Julien Bect, Emmanuel Vazquez

This work presents a new procedure for obtaining predictive distributions in the context of Gaussian process (GP) modeling, with a relaxation of the i...

Uncertainty quantification for iterative algorithms in linear models with application to early stopping

Kai Tan, Pierre C Bellec

Statistical-Computational Trade-offs for Recursive Adaptive Partitioning Estimators

Yan Shuo Tan, Jason M. Klusowski, Krishnakumar Balasubramanian

Efficient Optimization of Plasma Radiation Detector Configurations using Imperfect Inference Models

Difan Song, William E. Lewis, Patrick F. Knapp et al.

Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret

Dong Xia, Jingyang Li, Yang Chen et al.

On the Algorithmic Bias of Aligning Large Language Models with RLHF: Preference Collapse and Matching Regularization

Cong Fang, Weijie J. Su, Jiancong Xiao et al.

Differentially Private Sliced Inverse Regression: Minimax Optimality and Algorithm

Linjun Zhang, Zhanrui Cai, Xintao Xia

A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization

Junwen Qiu, Xiao Li, Andre Milzarek

Random reshuffling techniques are prevalent in large-scale applications, such as training neural networks. While the convergence and acceleration effe...

EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback

Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov et al.

First proposed by Seide (2014) as a heuristic, error feedback (EF) is a very popular mechanism for enforcing convergence of distributed gradient-based...

Fast Algorithm for Constrained Linear Inverse Problems

Mohammed Rayyan Sheriff, Floor Fenne Redel, Peyman Mohajerin Esfahani

We consider the constrained Linear Inverse Problem (LIP), where a certain atomic norm (like the $\ell_1 $ norm) is minimized subject to a quadratic co...

Simplex Constrained Sparse Optimization via Tail Screening

Xueqin Wang, Peng Chen, Jin Zhu et al.

We consider the probabilistic simplex-constrained sparse recovery problem. The commonly used Lasso-type penalty for promoting sparsity is ineffective ...

Regularized Rényi Divergence Minimization through Bregman Proximal Gradient Algorithms

Thomas Guilmeau, Emilie Chouzenoux, Víctor Elvira

We study the variational inference problem of minimizing a regularized Rényi divergence over an exponential family. We propose to solve this problem w...

Universal Online Convex Optimization Meets Second-order Bounds

Yibo Wang, Lijun Zhang, Guanghui Wang et al.

Recently, several universal methods have been proposed for online convex optimization, and attain minimax rates for multiple types of convex function...

Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems

Michal Dereziński, Daniel LeJeune, Deanna Needell et al.

Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify due to prob...

Optimal and Efficient Algorithms for Decentralized Online Convex Optimization

Lijun Zhang, Yuanyu Wan, Tong Wei et al.

We investigate decentralized online convex optimization (D-OCO), in which a set of local learners are required to minimize a sequence of global loss f...

Quantifying the Effectiveness of Linear Preconditioning in Markov Chain Monte Carlo

Max Hird, Samuel Livingstone

We study linear preconditioning in Markov chain Monte Carlo. We consider the class of well-conditioned distributions, for which several mixing time bo...

Online multivariate changepoint detection: leveraging links with computational geometryGet access

Liudmila Pishchaginaand others

Fast convergence of the Expectation-Maximization algorithm under a logarithmic Sobolev inequality

R CaprioandA M Johansen

A Computational Transition for Detecting Correlated Stochastic Block Models by Low-Degree Polynomials

Jian Ding, Zhangsong Li, Guanyi Chen et al.

Algorithmic Stability Implies Training-Conditional Coverage for Distribution-Free Prediction Methods

Ruiting Liang, Rina Foygel Barber

Prominent Roles of Conditionally Invariant Components in Domain Adaptation: Theory and Algorithms

Keru Wu, Yuansi Chen, Wooseok Ha et al.

Domain adaptation (DA) is a statistical learning problem that arises when the distribution of the source data used to train a model differs from that ...

Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles

Lesi Chen, Yaohua Ma, Jingzhao Zhang

In this work, we consider bilevel optimization when the lower-level problem is strongly convex. Recent works show that with a Hessian-vector product (...

On Global and Local Convergence of Iterative Linear Quadratic Optimization Algorithms for Discrete Time Nonlinear Control

Vincent Roulet, Siddhartha Srinivasa, Maryam Fazel et al.

A classical approach for solving discrete time nonlinear control on a finite horizon consists in repeatedly minimizing linear quadratic approximations...

A Decentralized Proximal Gradient Tracking Algorithm for Composite Optimization on Riemannian Manifolds

Lei Wang, Le Bao, Xin Liu

This paper focuses on minimizing a smooth function combined with a nonsmooth regularization term on a compact Riemannian submanifold embedded in the E...

Distributed Stochastic Bilevel Optimization: Improved Complexity and Heterogeneity Analysis

Youcheng Niu, Jinming Xu, Ying Sun et al.

This paper considers solving a class of nonconvex-strongly-convex distributed stochastic bilevel optimization (DSBO) problems with personalized inner-...

Optimization Over a Probability Simplex

James Chok, Geoffrey M. Vasil

We propose a new iteration scheme, the Cauchy-Simplex, to optimize convex problems over the probability simplex $\{w\in\mathbb{R}^n\ |\ \sum_i w_i=1\ ...

Instability, Computational Efficiency and Statistical Accuracy

Raaz Dwivedi, Koulik Khamaru, Martin J. Wainwright et al.

Many statistical estimators are defined as the fixed point of a data-dependent operator, with estimators based on minimizing a cost function being an ...

On Adaptive Stochastic Optimization for Streaming Data: A Newton's Method with O(dN) Operations

Antoine Godichon-Baggioni, Nicklas Werge

Stochastic optimization methods face new challenges in the realm of streaming data, characterized by a continuous flow of large, high-dimensional data...

Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization

Shouri Hu, Haowei Wang, Zhongxiang Dai et al.

The expected improvement (EI) is one of the most popular acquisition functions for Bayesian optimization (BO) and has demonstrated good empirical perf...

Extremal graphical modeling with latent variables via convex optimization

Sebastian Engelke, Armeen Taeb

Extremal graphical models encode the conditional independence structure of multivariate extremes and provide a powerful tool for quantifying the risk ...

Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming

Sen Na, Michael Mahoney

We consider online statistical inference of constrained stochastic nonlinear optimization problems. We apply the Stochastic Sequential Quadratic Progr...

Accelerating optimization over the space of probability measures

Shi Chen, Qin Li, Oliver Tse et al.

The acceleration of gradient-based optimization methods is a subject of significant practical and theoretical importance, particularly within machine ...

Riemannian Bilevel Optimization

Jiaxiang Li, Shiqian Ma

In this work, we consider the bilevel optimization problem on Riemannian manifolds. We inspect the calculation of the hypergradient of such problems o...

Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization

Michael I. Jordan, Tianyi Lin, Chi Jin

We provide a unified analysis of two-timescale gradient descent ascent (TTGDA) for solving structured nonconvex minimax optimization problems in the f...

Efficiently Escaping Saddle Points in Bilevel Optimization

Shiqian Ma, Minhui Huang, Xuxing Chen et al.

Bilevel optimization is one of the fundamental problems in machine learning and optimization. Recent theoretical developments in bilevel optimization ...

Estimation of Out-of-Sample Sharpe Ratio for High Dimensional Portfolio Optimization

Xuran Meng, Yuan Cao, Weichen Wang

Optimal clustering by Lloyd’s algorithm for low-rank mixture model

Dong Xia, Zhongyuan Lyu

Unbiased and consistent nested sampling via sequential Monte Carlo

Robert Salomone, others

Towards a turnkey approach for unbiased Monte Carlo estimation of smooth functions of expectations

Nicolas Chopin, others

Abstract

Sequential Monte Carlo testing by betting

Lasse Fischer, Aaditya Ramdas

Bayesian penalized empirical likelihood and Markov Chain Monte Carlo sampling

Jinyuan Chang, others

U-Statistic Reduction: Higher-Order Accurate Risk Control and Statistical-Computational Trade-Off

Dong Xia, Meijia Shao, Yuan Zhang

Simulation-Based, Finite-Sample Inference for Privatized Data

Jordan Awan, Zhanyu Wang

Geometric Ergodicity of Trans-Dimensional Markov Chain Monte Carlo Algorithms

Qian Qin

Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations

Chanwoo Lee, Miaoyan Wang