Minimizing a function over an intersection of convex sets is an important task in optimization that is often much more challenging than minimizing it over each individual constraint set. While traditional methods such as Frank-Wolfe (FW) or proximal gradient descent assume access to a linear or quadratic oracle on the …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “linear minimization oracles”
Improved Frank-Wolfe algorithm for constrained convex optimization with nearest extreme point oracle.
problem Constrained smooth convex minimization with limited linear optimization oracle access.
method Frank-Wolfe algorithm with nearest extreme point oracle.
result Improved complexity bounds for specific feasible sets, including linear convergence for polytopes.
New method solves constrained self-concordant minimization problems efficiently.
problem Constrained self-concordant minimization problems.
method Newton Frank-Wolfe method using linear minimization oracles.
result The method uses nearly the same number of linear minimization calls as the Frank-Wolfe method.
We consider the problem of minimizing the sum of submodular set functions assuming minimization oracles of each summand function. Most existing approaches reformulate the problem as the convex minimization of the sum of the corresponding Lovász extensions and the squared Euclidean norm, leading to algorithms requiring …
Oracle-efficient algorithm for offline RL with partial data coverage.
problem Offline reinforcement learning with partial data coverage and constraints.
method PDOCRL, a primal-dual algorithm with decomposed linear-programming formulation.
result Near-optimal, near-feasible policy with \(\widetilde{\mathcal O}(ε^{-2})\) sample guarantee.
New algorithm reduces ERM problem size while maintaining accuracy.
problem Empirical risk minimization problem size reduction.
method Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm.
result Uniform relative-error approximation for ERM objective.
Local LMO optimizes constrained problems using local linear minimization.
problem Constrained optimization problems with complex feasible sets.
method Designs a new projection-free gradient method using local linear minimization.
result Transfers convergence rates of Projected Gradient Descent to the projection-free world.
We discuss the problem of adaptive discrete-time signal denoising in the situation where the signal to be recovered admits a "linear oracle" -- an unknown linear estimate that takes the form of convolution of observations with a time-invariant filter. It was shown by Juditsky and Nemirovski (2009) that when the $\ell_2…
ERM performs well in feature learning with minimal feature maps.
problem Empirical risk minimization in feature learning with square loss.
method Asymptotic and non-asymptotic analysis of ERM performance.
result Excess risk quantiles of ERM match those of oracle procedure under certain conditions.
This paper consider penalized empirical loss minimization of convex loss functions with unknown non-linear target functions. Using the elastic net penalty we establish a finite sample oracle inequality which bounds the loss of our estimator from above with high probability. If the unknown target is linear this inequali…
Unified framework for shrinkage, thresholding, and regularization in normal mean estimation and linear regression.
problem Estimation of normal mean in multivariate settings with correlated observations.
method Approximate risk minimization over a functional class of shrinkage-thresholding rules.
result Unified estimator NOMAD for shrinkage, thresholding, and regularization.
Non-linear shrinkage isn't optimal for portfolio optimization, especially when asset dependence is non-stationary.
problem Optimizing portfolios with non-stationary asset dependence structures.
method Derived and compared non-linear shrinkage with an optimal target for covariance matrix estimation.
result Non-linear shrinkage can be significantly improved for portfolio optimization.
A new algorithm for solving constrained convex optimization problems efficiently.
problem Constrained convex optimization problems requiring high accuracy solutions.
method Second-Order Conditional Gradient Sliding (SOCGS) algorithm, using projection-free methods to solve quadratic subproblems inexactly.
result Converges quadratically in primal gap after a finite number of linearly convergent iterations.
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved regret with oracle queries for worst-case linear rewards.
The paper analyzes prediction error in nonstationary settings using weighted risk minimization.
problem Prediction under distribution drift and nonstationary conditions.
method General decomposition of excess risk into learning and drift terms, proving oracle inequalities under mixing conditions.
result Oracle inequalities for the learning error, providing bounds that hold uniformly over arbitrary weight classes.
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of ``2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization'' by V. Koltchinskii [arXiv:0708.0083]
Discussion of "2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization" by V. Koltchinskii [arXiv:0708.0083]
Algorithm minimizes regret while adhering to unknown safety constraints.
problem Online learning with unknown safety constraints.
method General meta-algorithm leveraging online regression and learning oracles.
result Concrete algorithm with regret for linear constraints.
Folded concave penalization methods have been shown to enjoy the strong oracle property for high-dimensional sparse estimation. However, a folded concave penalization problem usually has multiple local solutions and the oracle property is established only for one of the unknown local solutions. A challenging fundamenta…
Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Stepmath.OC
New algorithm tackles complex optimization problems with inexact and stochastic methods.
problem Solving complex optimization problems with inexact and stochastic methods.
method Developed ICGALP algorithm for composite minimization problems with inexact computations.
result Convergence of Lagrangian to an optimum and asymptotic feasibility of the affine constraint.
Develops algorithms for CCBs with non-linear costs, improving safety and performance.
problem Safety constraints in sequential decision making with non-linear arm costs.
method Innovative algorithms using Inverse Gap Weighting (IGW) and online regression oracle.
result Sub-linear regret bounds for C-SquareCB and first-order regret for C-FastCB.
Paper introduces structured sparsity estimators for Generalized Linear Models.
problem Estimating structured sparsity in GLMs with debiased estimators.
method Extends Stucky and van de Geer's results to GLMs with structured sparsity.
result Proves oracle inequalities for structured sparsity estimators in GLMs.
Gradient descent is efficient for solving feasibility problems with minimal memory and queries.
problem Finding a point in a given set using a memory-constrained algorithm with a separation oracle.
method Oracle complexity lower bounds for gradient descent and other algorithms.
result Gradient descent is Pareto-optimal in the oracle complexity/memory tradeoff for feasibility problems.
We introduce an efficient algorithmic framework for model selection in online learning, also known as parameter-free online learning. Departing from previous work, which has focused on highly structured function classes such as nested balls in Hilbert space, we propose a generic meta-algorithm framework that achieves o…
Paper addresses online alignment of large language models under uncertain preference feedback.
problem Online alignment of large language models with misspecified preference feedback.
method Formulates an oracle-robust objective as a worst-case optimization problem for log-linear policies, and develops projected stochastic composite updates.
result Shows that the robust objective admits an exact closed-form decomposition and achieves oracle complexity.
Algorithm reduces regret in SSP problems with LFA.
problem Finding shortest paths in stochastic environments with linear approximations.
method Uses linear function approximation and stationary policies to minimize regret.
result Achieves sublinear regret under minimal assumptions.
This paper tackles the problem of selecting among several linear estimators in non-parametric regression; this includes model selection for linear regression, the choice of a regularization parameter in kernel ridge regression, spline smoothing or locally weighted regression, and the choice of a kernel in multiple kern…
New data-dependent priors improve PAC-Bayes bounds.
problem Improving PAC-Bayes bounds for nonconvex learning.
method Using data to learn a conditional expectation of the posterior, given a subset of training data.
result Data-dependent oracle priors lead to stronger PAC-Bayes bounds.
New algorithm reduces contextual bandit identification to argmax calls.
problem Best-arm identification in stochastic contextual bandits.
method Instance-optimal PAC algorithm using argmax oracle calls.
result First instance-dependent PAC sample complexity for contextual bandits.
New algorithms optimize actions under time-varying constraints without projecting.
problem Optimizing actions under time-varying constraints without projecting.
method Projection-free algorithms using linear optimization oracle.
result Guaranteed regret and constraints violation.
Average Oracle outperforms DCC+NLS in portfolio optimization.
problem Optimizing portfolio performance in volatile markets.
method Comparing the Average Oracle to various DCC+NLS variants.
result The Average Oracle consistently yields higher Sharpe ratios.
New algorithm learns efficiently with a simple 'yes/no' oracle.
problem Can efficient learning be achieved with a simpler oracle than ERM?
method Developed an oracle that returns 'yes' or 'no' for realizable datasets.
result Learnability is possible with a polynomial price in VC dimension.
We analyze two novel randomized variants of the Frank-Wolfe (FW) or conditional gradient algorithm. While classical FW algorithms require solving a linear minimization problem over the domain at each iteration, the proposed method only requires to solve a linear minimization problem over a small \emph{subset} of the or…
Unified federated learning via GTV minimization.
problem Training local models for decentralized datasets with network structure.
method Formulated federated learning as GTV minimization, developed a decentralized algorithm.
result Upper bound on local model parameters deviation, revealing conditions for pooling homogeneous datasets.
New algorithm learns FMDP structure while minimizing regret.
problem Regret minimization in FMDPs with unknown structure.
method Optimism in face of uncertainty principle combined with statistical structure learning.
result First algorithm to learn FMDP structure while minimizing regret.
Optimizes bilevel empirical risk minimization with improved oracle calls.
problem Optimizing bilevel empirical risk minimization problems.
method Proposes a bilevel extension of the SARAH algorithm.
result Demonstrates improved oracle calls to achieve stationarity.
Piecewise polynomial interpolation-based gradient descent reduces oracle complexity for smooth loss functions.
problem Optimizing empirical risk minimization loss functions
method Piecewise polynomial interpolation-based gradient descent
result Oracle complexity is reduced for smooth loss functions
Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcs.LG
New algorithms ensure reproducibility and optimal convergence in convex optimization.
problem Trade-off between reproducibility and convergence rate in convex optimization.
method Regularization-based algorithms for smooth convex minimization and minimax optimization.
result Achieves optimal reproducibility and near-optimal gradient complexity for various oracle settings.
The paper studies the benefits of curriculum learning in linear regression tasks.
problem Theoretical understanding of curriculum learning's benefits in machine learning.
method Theoretical analysis of curriculum learning in structured and unstructured multitask linear regression problems.
result Adaptive learning in the unstructured setting is fundamentally harder than oracle learning, but not in the structured setting.
Study on tradeoffs between mistakes and ERM oracle calls in online and transductive learning.
problem Analyzing online and transductive learning with limited ERM and weak consistency oracle access.
method Proves lower bounds and upper bounds on mistakes and oracle calls, considering realizable and agnostic cases.
result Achieves optimal mistake bounds with weak consistency queries for certain concept classes.
Extends covariance estimation with multiple targets for better performance.
problem Improving covariance estimation for multiple targets.
method Combines multiple constant matrices with sample covariance matrix, derives estimators and proves convergence.
result The multi-target linear shrinkage estimator outperforms other estimators in various situations.
We investigate properties of estimators obtained by minimization of U-processes with the Lasso penalty in high-dimensional settings. Our attention is focused on the ranking problem that is popular in machine learning. It is related to guessing the ordering between objects on the basis of their observed predictors. We p…
-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, approximating -functions with linear functions, it is still an open problem on how to design a pr…
A successful approach to structured learning is to write the learning objective as a joint function of linear parameters and inference messages, and iterate between updates to each. This paper observes that if the inference problem is "smoothed" through the addition of entropy terms, for fixed messages, the learning ob…
We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model that allows access to the data via a matrix-vector product oracle. We show that for polynomial accuracy, calls to the oracle are nece…