Proposes efficient stochastic algorithms for optimizing NDCG with provable convergence guarantees.
problem Efficient and provable stochastic methods for maximizing NDCG in deep learning models.
method Formulates novel compositional optimization problems, develops efficient stochastic algorithms with provable convergence guarantees, and proposes practical strategies.
result Stochastic algorithms with provable convergence guarantees for optimizing NDCG and its top-K variant. New algorithm finds near-optimal policies efficiently in zero-sum games.
problem Lack of provable efficiency guarantees for policy optimization in zero-sum games.
method Policy optimization algorithm with function approximation.
result Proves efficient convergence to near-optimal policies with polynomial samples and iterations.
POLICE enforces linear constraints on deep neural networks efficiently.
problem Enforcing constraints on deep neural networks without affecting optimization.
method Provably optimal affine constraint enforcement method that minimally modifies DNNs.
result POLICE ensures DNNs fulfill affine constraints during training and testing.
Framework for fair classification with noisy protected attributes and provable guarantees.
problem Fair classification with noisy protected attributes.
method Optimization framework for linear and linear-fractional fairness constraints, handling multiple non-binary attributes.
result Provably fair classifier with minimal accuracy loss, even with large noise.
This paper introduces a new scalarization method for multi-objective optimization.
problem Efficiently optimizing multiple conflicting objectives in black box settings.
method Introduces a novel hypervolume scalarization function and uses it to approximate the hypervolume indicator metric.
result Provable convergence to the entire Pareto frontier using random scalarizations and Bayesian optimization.
Framework combines adversarial training and provable robustness for neural networks.
problem Training certifiably robust neural networks with provable robustness guarantees.
method Formulates joint optimization problem with adversarial and provable robustness objectives; develops gradient-descent technique.
result Consistently matches or outperforms prior approaches for provable l infinity robustness on MNIST and CIFAR-10.
Efficient method for constrained optimization under partial observations with provable convergence.
problem Optimizing under partial and constrained data.
method Improved acquisition functions and Gaussian process embedding for partially observable constraints.
result Empirically validated method outperforms traditional approaches.
PARADE generates provably robust adversarial examples for deep networks.
problem Creating robust adversarial examples for deep neural networks.
method Iterative refinement of adversarial regions using optimization to ensure robustness under various perturbations.
result PARADE finds large, provably robust adversarial regions with high volume under various perturbations.
While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to design a provably efficient policy optimization algorithm that incorporates exploration. To bridge su…
OKRidge solves sparse ridge regression problems for nonlinear systems.
problem Identifying sparse governing equations for nonlinear dynamical systems.
method OKRidge algorithm using saddle point formulation and ADMM-based approach with efficient proximal operators.
result OKRidge achieves provable optimality with significantly faster run times than Gurobi.
Efficient poisoning attack converges to any target classifier with provable convergence.
problem Inducing a corrupted model that misbehaves in favor of an adversary.
method Online convex optimization to find poisoning points incrementally.
result Provably converges to any attainable target classifier.
Study calibrates high-dimensional binary classifiers using angle between estimator and true weights.
problem Calibrating high-dimensional binary classifiers with provable properties.
method Interpolates with a chance classifier to construct well-calibrated predictor based on angle between estimator and true weights.
result Angular calibration approach is provably well-calibrated in high dimensions, minimizing Bregman divergence.
RedEx improves neural network optimization with convex optimization guarantees.
problem Difficult optimization of neural networks.
method RedEx architecture using convex optimization with semi-definite constraints.
result RedEx can efficiently learn functions fixed methods cannot.
Although deep learning has shown its powerful performance in many applications, the mathematical principles behind neural networks are still mysterious. In this paper, we consider the problem of learning a one-hidden-layer neural network with quadratic activations. We focus on the under-parameterized regime where the n…
Improved heteroscedastic regression using neural networks with provably accurate mean estimates and calibrated variance.
problem Optimizing neural network parameters for heteroscedastic regression leads to suboptimal mean and variance estimates.
method Two simple modifications to optimization to retain accuracy of mean-only models and offer best-in-class variance calibration.
result Mean estimates from the proposed method are provably as accurate as those from a homoscedastic model.
New framework shows cross-attention improves multi-modal in-context learning.
problem Understanding multi-modal in-context learning in neural networks.
method Mathematical framework and linearized cross-attention mechanism.
result Cross-attention mechanism is provably optimal for multi-modal in-context learning.
Study improves understanding of why agentic theorem provers succeed.
problem Understanding which components of agentic theorem provers improve proof success.
method Statistical provability theory and finite-horizon reachability MDP model.
result Bounds provability gap and explains components' effectiveness.
Mean field inference in probabilistic models is generally a highly nonconvex problem. Existing optimization methods, e.g., coordinate ascent algorithms, can only generate local optima. In this work we propose provable mean filed methods for probabilistic log-submodular models and its posterior agreement (PA) with stron…
New algorithms reduce bilevel optimization complexity to ε^(-1.5).
problem Efficiently solving bilevel optimization problems in machine learning.
method Proposed two new algorithms: one using momentum-based recursive iterations, the other using recursive gradient estimations.
result Achieved computational complexity of ε^(-1.5), significantly faster than previous methods.
Extended analysis of Q-learning's efficiency, matching optimal regret.
problem Theoretical guarantees of Q-learning's efficiency and optimal regret.
method Survey of related research, detailed proof reasoning.
result Q-learning with UCB exploration achieves sample efficiency matching optimal regret.
Two commonly arising computational tasks in Bayesian learning are Optimization (Maximum A Posteriori estimation) and Sampling (from the posterior distribution). In the convex case these two problems are efficiently reducible to each other. Recent work (Ma et al. 2019) shows that in the non-convex case, sampling can som…
Black-box variational inference tries to approximate a complex target distribution though a gradient-based optimization of the parameters of a simpler distribution. Provable convergence guarantees require structural properties of the objective. This paper shows that for location-scale family approximations, if the targ…
Paper resolves bias in ALFT training using generalized alignment games.
problem Systematic bias in estimating logarithmic rewards from small batches.
method Generalized Distributional Alignment Games, U-statistics, minimax polynomial estimators, Variance-Optimal Augmented Polynomial Optimization Program (AQP) Estimator.
result Proves optimal bias and accelerated convergence in ALFT training.
The problem of finding overlapping communities in networks has gained much attention recently. Optimization-based approaches use non-negative matrix factorization (NMF) or variants, but the global optimum cannot be provably attained in general. Model-based approaches, such as the popular mixed-membership stochastic blo…
Paper proposes robust generative models using VAEs.
problem Lack of robustness in generative models.
method Formally defined robust lower bound, optimized during training.
result Generative models become more robust to adversarial attacks.
PAC-Bayesian theory applied to learning optimization algorithms with generalization guarantees.
problem Learning optimization algorithms with provable generalization guarantees and explicit trade-offs.
method PAC-Bayes theory applied to learning-to-optimize, reformulating the learning procedure into a one-dimensional minimization problem.
result Learned optimization algorithms outperform deterministic worst-case analysis algorithms, even in the limit case of guaranteed convergence.
Novel algorithm accelerates PnP methods for image deblurring and super-resolution.
problem Efficiently solving inverse problems and imaging with provable convergence guarantees.
method Incorporates quasi-Newton steps into provable PnP framework based on proximal denoisers.
result 2--8x faster convergence compared to other provable PnP methods with similar quality.
We study Imitation Learning (IL) from Observations alone (ILFO) in large-scale MDPs. While most IL algorithms rely on an expert to directly provide actions to the learner, in this setting the expert only supplies sequences of observations. We design a new model-free algorithm for ILFO, Forward Adversarial Imitation Lea…
Improves neural network verification by merging abstract domains and Lagrangian methods.
problem Prove provable bounds for neural network outputs given input ranges.
method Uses zonotopes within a Lagrangian decomposition to verify deep neural networks.
result Yields bounds that improve upon existing techniques in both time and tightness.
Layer-wise preconditioning methods improve neural network optimization and feature learning.
problem Suboptimal feature learning in standard optimization algorithms.
method Layer-wise preconditioning methods that introduce preconditioners per axis of each layer's weight tensors.
result Layer-wise preconditioning is necessary for provable feature learning in linear and single-index models.
We analyze stochastic algorithms for optimizing nonconvex, nonsmooth finite-sum problems, where the nonconvex part is smooth and the nonsmooth part is convex. Surprisingly, unlike the smooth case, our knowledge of this fundamental problem is very limited. For example, it is not known whether the proximal stochastic gra…
Bayesian optimization (BO) based on Gaussian process models is a powerful paradigm to optimize black-box functions that are expensive to evaluate. While several BO algorithms provably converge to the global optimum of the unknown function, they assume that the hyperparameters of the kernel are known in advance. This is…
Interest in derivative-free optimization (DFO) and "evolutionary strategies" (ES) has recently surged in the Reinforcement Learning (RL) community, with growing evidence that they can match state of the art methods for policy optimization problems in Robotics. However, it is well known that DFO methods suffer from proh…
We consider the dictionary learning problem, where the aim is to model the given data as a linear combination of a few columns of a matrix known as a dictionary, where the sparse weights forming the linear combination are known as coefficients. Since the dictionary and coefficients, parameterizing the linear model are …
Proposes a method for obtaining interval bounds in off-policy evaluation.
problem Provides provably correct upper and lower bounds for off-policy evaluation.
method Searches for the maximum and minimum values of the expected reward among Lipschitz Q-functions.
result Introduces a Lipschitz value iteration method to monotonically tighten interval bounds.
Gradient-free method solves infinite-dimensional optimization problems.
problem Optimizing functions in infinite-dimensional spaces.
method Uses directional derivatives and a pre-basis for Hilbert space.
result Proves convergence for solving PDEs using PINNs.
New algorithm provably converges to second-order stationary points in NMF.
problem Understanding convergence to local minima in NMF.
method Multiplicative weight update dynamics, concurrent updates, and simplex reduction.
result Provable convergence to second-order stationary points.
We study the design of computationally efficient algorithms with provable guarantees, that are robust to adversarial (test time) perturbations. While there has been an proliferation of recent work on this topic due to its connections to test time robustness of deep networks, there is limited theoretical understanding o…
Model shows screening for infectious disease is hard but Thompson sampling works well.
problem Optimal screening policy for infectious diseases is hard to find.
method Stochastic-control model with Thompson sampling for optimal performance.
result Thompson sampling provides optimal performance guarantees in screening for infectious diseases.
In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures -- arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithm…
PROPO tackles non-stationary MDPs with efficient policy optimization.
problem Non-stationary MDPs with varying reward and transition kernels.
method PROPO, a periodic restarted optimistic policy optimization algorithm with sliding-window-based policy evaluation and improvement.
result PROPO achieves near-optimal performance in non-stationary MDPs.
Paper improves communication in distributed optimization, reducing worker-to-server data exchanges.
problem Efficiency in server-to-worker communication in distributed optimization.
method MARINA-P, a novel downlink compression method using correlated compressors; M3, combining MARINA-P with uplink compression.
result MARINA-P achieves provably superior server-to-worker communication complexity with increasing number of workers.
Normalization techniques such as Batch Normalization have been applied successfully for training deep neural networks. Yet, despite its apparent empirical benefits, the reasons behind the success of Batch Normalization are mostly hypothetical. We here aim to provide a more thorough theoretical understanding from a clas…
New algorithm for online tensor factorization with provable guarantees.
problem Factorizing structured tensors with unknown factors and non-convex optimization.
method Online CP/PARAFAC decomposition via dictionary learning with incoherence and sparsity constraints.
result Exact recovery of tensor factors at a linear rate under mild conditions.
New offline RL algorithms tackle partial data coverage with optimal performance and practicality.
problem Partial data coverage in offline RL datasets.
method Augmented Lagrangian method applied to MIS formulation for optimal offline RL.
result Statistically optimal offline RL with practical performance, eliminating conservatism.
New framework for fair classification in adversarial settings with provable guarantees.
problem Fairness in classification with adversarial perturbations of protected attributes.
method Optimization framework for learning fair classifiers with provable guarantees.
result Near-tightness of accuracy and fairness guarantees for multiple protected attributes and various hypothesis classes.
GenFlow optimizes faster, avoiding saddle points in fixed time.
problem Designing efficient optimization algorithms for convex and non-convex functions.
method Introduces GenFlow and momentum variants with fixed-time convergence guarantees.
result GenFlow and momentum variants converge to optimal solutions in fixed time for PL functions and evade saddle points uniformly.
Machine-learning models for security-critical applications such as bot, malware, or spam detection, operate in constrained discrete domains. These applications would benefit from having provable guarantees against adversarial examples. The existing literature on provable adversarial robustness of models, however, exclu…